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 main

import "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 {

    if n < 0 {

        panic("fibonacci: n < 0")

    }

    f := int64(0)

    a, b := int64(0), int64(1)

    for i := 0; i <= n; i++ {

        if a < 0 {

            panic("fibonacci: overflow")

        }

        f, a, b = a, b, a+b

    }

    return f

}

func main() {

    for _, n := range []int{0, 1, 2, 3, 90, 91, 92} {

        fmt.Printf("%-2d  %d\n", n, fibonacci(n))

    }

}

游乐场： https: //play.golang.org/p/_5CMHZm3Hlo

输出：

0   0

1   1

2   1

3   2

90  2880067194370816120

91  4660046610375530309

92  7540113804746346429

real    0m0.003s

user    0m0.002s

sys     0m0.000s

Answer 2

正如icza 在评论中指出的那样，实际上将其编译并作为Go代码运行，它运行得非常快：

package main

import (

    "fmt"

    "time"

)

func fib(n int) int {

    if n < 2 {

        return n

    } else {

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

    }

}

func main() {

    s := time.Now()

    fmt.Println(fib(34))

    d := time.Now().Sub(s)

    fmt.Println("took", d)

}

$ go run fib.go

5702887

took 49.244697ms

（注意：以上是草率的：我们应该使用int64，我只是懒惰）。

Python3 变体：

import time

def fib(n):

    if n < 2:

        return n

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

s = time.time()

print(fib(34))

print(f"took {time.time() - s}s")

需要更长的时间：

$ python3 fib.py

5702887

took 2.1027958393096924s

正如peterSO 所指出的，递归算法进行了很多调用：

package main

import (

    "fmt"

    "time"

)

var calls int

func fib(n int) int {

    calls += 1

    if n < 2 {

        return n

    } else {

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

    }

}

func main() {

    s := time.Now()

    fmt.Println(fib(34))

    d := time.Now().Sub(s)

    fmt.Println("took", d, "to make", calls, "calls")

}

$ go run fib.go

5702887

took 53.328049ms to make 18454929 calls

（额外的几毫秒是由于计算调用）。所以 Go 在大约 50 毫秒内运行了 1845 万次调用，而 Python 在大约 2.1 秒内运行了同样的 1845 万次调用。Go 每次调用大约需要 2.7 ns，Python 每次调用大约需要 114 ms。