Go GC 负责 90% 的 CPU 时间

Question

我正在为 Go 中一种简单的、虚构的编程语言编写一个虚拟机。我正在使用分析器 pprof 来提高性能。我正在用我编造的语言运行斐波那契函数来测试递归函数。

func fib(n) {

    if n < 2 {

        return n

    } else {

        return fib(n-1) + fib(n-2)

    }

}

print fib(34)

当我运行它需要 14 秒，在 Python 中需要 2 秒。这是来自 PProf 的图片。我用绿色突出显示了我的实际程序的函数调用。它们需要 2 秒，另外 12 秒似乎都是 Go 的垃圾收集器。

有没有办法弄清楚为什么垃圾收集器要花这么多时间？

Answer 1

是你的递归算法产生了组合爆炸。使用迭代算法。试试这个迭代算法：package mainimport "fmt"// fibonacci returns the Fibonacci number for 0 <= n <= 92.// OEIS: A000045: Fibonacci numbers:// F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.func fibonacci(n int) int64 {&nbsp; &nbsp; if n < 0 {&nbsp; &nbsp; &nbsp; &nbsp; panic("fibonacci: n < 0")&nbsp; &nbsp; }&nbsp; &nbsp; f := int64(0)&nbsp; &nbsp; a, b := int64(0), int64(1)&nbsp; &nbsp; for i := 0; i <= n; i++ {&nbsp; &nbsp; &nbsp; &nbsp; if a < 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; panic("fibonacci: overflow")&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; f, a, b = a, b, a+b&nbsp; &nbsp; }&nbsp; &nbsp; return f}func main() {&nbsp; &nbsp; for _, n := range []int{0, 1, 2, 3, 90, 91, 92} {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Printf("%-2d&nbsp; %d\n", n, fibonacci(n))&nbsp; &nbsp; }}游乐场： https: //play.golang.org/p/_5CMHZm3Hlo输出：0&nbsp; &nbsp;01&nbsp; &nbsp;12&nbsp; &nbsp;13&nbsp; &nbsp;290&nbsp; 288006719437081612091&nbsp; 466004661037553030992&nbsp; 7540113804746346429real&nbsp; &nbsp; 0m0.003suser&nbsp; &nbsp; 0m0.002ssys&nbsp; &nbsp; &nbsp;0m0.000s

Answer 2

正如icza 在评论中指出的那样，实际上将其编译并作为Go代码运行，它运行得非常快：package mainimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "time")func fib(n int) int {&nbsp; &nbsp; if n < 2 {&nbsp; &nbsp; &nbsp; &nbsp; return n&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; return fib(n-1) + fib(n-2)&nbsp; &nbsp; }}func main() {&nbsp; &nbsp; s := time.Now()&nbsp; &nbsp; fmt.Println(fib(34))&nbsp; &nbsp; d := time.Now().Sub(s)&nbsp; &nbsp; fmt.Println("took", d)}$ go run fib.go5702887took 49.244697ms（注意：以上是草率的：我们应该使用int64，我只是懒惰）。Python3 变体：import timedef fib(n):&nbsp; &nbsp; if n < 2:&nbsp; &nbsp; &nbsp; &nbsp; return n&nbsp; &nbsp; return fib(n-1) + fib(n-2)s = time.time()print(fib(34))print(f"took {time.time() - s}s")需要更长的时间：$ python3 fib.py5702887took 2.1027958393096924s正如peterSO 所指出的，递归算法进行了很多调用：package mainimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "time")var calls intfunc fib(n int) int {&nbsp; &nbsp; calls += 1&nbsp; &nbsp; if n < 2 {&nbsp; &nbsp; &nbsp; &nbsp; return n&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; return fib(n-1) + fib(n-2)&nbsp; &nbsp; }}func main() {&nbsp; &nbsp; s := time.Now()&nbsp; &nbsp; fmt.Println(fib(34))&nbsp; &nbsp; d := time.Now().Sub(s)&nbsp; &nbsp; fmt.Println("took", d, "to make", calls, "calls")}$ go run fib.go5702887took 53.328049ms to make 18454929 calls（额外的几毫秒是由于计算调用）。所以 Go 在大约 50 毫秒内运行了 1845 万次调用，而 Python 在大约 2.1 秒内运行了同样的 1845 万次调用。Go 每次调用大约需要 2.7 ns，Python 每次调用大约需要 114 ms。