改变一个字符让Go程序快42%

22-11-17 banq

codeowners是一个 Go 程序,它根据GitHubCODEOWNERS文件中定义的一组规则打印出存储库中每个文件的所有者。

在考虑给定路径时,最后匹配的规则获胜:一个简单但幼稚的匹配算法通过每条路径的规则向后迭代,在找到匹配项时停止:

type Ruleset Rule

func (r Ruleset) Match(path string) (*Rule, error) {
  for i := len(r) - 1; i >= 0; i-- {
    rule := r
    match, err := rule.Match(path)
    if match || err != nil {
      return &rule, err
    }
  }
  return nil, nil
}


使用 pprof 和火焰图查找瓶颈
上述这个工具在针对中等大型存储库运行时有点慢,为了查看程序将时间花在哪里,我使用 pprof 记录了一个 CPU 配置文件。您可以通过将此代码段添加到main函数顶部来获取生成的 CPU 配置文件:

pprofFile, pprofErr := os.Create("cpu.pprof")
if pprofErr != nil {
  log.Fatal(pprofErr)
}
pprof.StartCPUProfile(pprofFile)
defer pprof.StopCPUProfile()


我经常使用 pprof,所以我将该代码保存为vscode 片段。我只需键入pprof,点击选项卡,就会出现该片段。

Go 带有一个方便的交互式配置文件可视化工具。我通过运行以下命令将配置文件可视化为火焰图,然后导航到页面顶部菜单中的火焰图视图。

$ go tool pprof -http=":8000" ./codeowners ./cpu.pprof

正如我所料,大部分时间都花在了那个Match功能上。CODEOWNERS 模式被编译为正则表达式,Match函数的大部分时间花在了 Go 的正则表达式引擎上。但我也注意到很多时间花在分配和回收内存上。

下面火焰图中的紫色块与模式匹配gc|malloc,您可以看到它们总体上代表了程序执行时间的重要部分。



使用逃逸分析跟踪寻找堆分配
那么就要看看是否有任何堆分配我们可以摆脱以减少 GC 压力和花费在malloc.

Go 编译器使用一种称为逃逸分析的技术来确定何时需要将一些内存驻留在堆上:
假设一个函数初始化一个结构然后返回一个指向它的指针。如果结构是在堆栈上分配的,那么一旦函数返回并且相应的堆栈帧失效,返回的指针就会失效。
在这种情况下,Go 编译器会确定指针已经“逃逸”了函数,并将结构移至堆中。

您可以在build构建时,通过传递-gcflags=-m来查看:

$ go build -gcflags=-m *.go 2>&1 | grep codeowners.go
./codeowners.go:82:18: inlining call to os.IsNotExist
./codeowners.go:71:28: inlining call to filepath.Join
./codeowners.go:52:19: inlining call to os.Open
./codeowners.go:131:6: can inline Rule.Match
./codeowners.go:108:27: inlining call to Rule.Match
./codeowners.go:126:6: can inline Rule.RawPattern
./codeowners.go:155:6: can inline Owner.String
./codeowners.go:92:29: ... argument does not escape
./codeowners.go:96:33: string(output) escapes to heap
./codeowners.go:80:17: leaking param: path
./codeowners.go:70:31: string{...} does not escape
./codeowners.go:71:28: ... argument does not escape
./codeowners.go:51:15: leaking param: path
./codeowners.go:105:7: leaking param content: r
./codeowners.go:105:24: leaking param: path
./codeowners.go:107:3: moved to heap: rule
./codeowners.go:126:7: leaking param: r to result ~r0 level=0
./codeowners.go:131:7: leaking param: r
./codeowners.go:131:21: leaking param: path
./codeowners.go:155:7: leaking param: o to result ~r0 level=0
./codeowners.go:159:13: "@" + o.Value escapes to heap



由于我们正在寻找heap堆分配,"moved to heap "是我们应该关注的短语。
回顾上面的Match代码,规则结构被存储在Ruleset片中,我们可以确信它已经在堆中了。由于返回的是一个指向规则的指针,因此不需要额外的分配。然后我看到了:通过分配 rule := 【i】,我们将堆heap中分配的 Rule 从堆片断中复制到栈stack中,然后再通过返回 &rule,我们创建了一个指向该结构副本的(逃避)指针。
幸运的是,解决这个问题很容易。我们只需要将“&”往上移一点,这样我们就可以在片断中获取一个结构的引用,而不是复制它:

func (r Ruleset) Match(path string) (*Rule, error) {
     for i := len(r) - 1; i >= 0; i-- {
-        rule := r
+        rule := &r
         match, err := rule.Match(path)
         if match || err != nil {
-            return &rule, err
+            return rule, err
         }
     }
     return nil, nil
 }


我确实考虑过另外两种方法:
  • 将Ruleset从Rule改为*Rule,这将意味着我们不再需要明确地获取对规则的引用。
    • 返回一个Rule而不是*Rule。这仍然会复制规则,但它应该留在堆栈stack中,而不是移动到堆heap中。



[然而,这两个方法都会导致一个破坏性的改变,因为这个方法是公共API的一部分。

总之,在做了这个改变之后,我们可以通过从编译器中得到一个新的跟踪,并与旧的跟踪进行比较,来看看它是否达到了预期效果。

$ diff trace-a trace-b
14a15
> ./codeowners.go:105:7: leaking param: r to result ~r0 level=0
16d16
< ./codeowners.go:107:3: moved to heap: rule

成功!分配没了。现在让我们看看删除一个堆分配如何影响性能:

$ hyperfine ./codeowners-a ./codeowners-b
Benchmark 1: ./codeowners-a
  Time (mean ± σ):      4.146 s ±  0.003 s    [User: 5.809 s, System: 0.249 s]
  Range (min … max):    4.139 s …  4.149 s    10 runs

Benchmark 2: ./codeowners-b
  Time (mean ± σ):      2.435 s ±  0.029 s    [User: 2.424 s, System: 0.026 s]
  Range (min … max):    2.413 s …  2.516 s    10 runs

Summary
  ./codeowners-b ran
    1.70 ± 0.02 times faster than ./codeowners-a

由于该分配是针对匹配的每条路径进行的,因此在这种情况下,删除它会使速度提高 1.7 倍(意味着它的运行速度提高了 42%)。