再帰フィボナッチでGoが比較的遅いように見える理由は何ですか？

Question

私はちょうどいくつかのコンパイルされ、翻訳された言語のための単純な再帰フィボナッチ関数を比較するこの素敵な小さなレポを見つけました：https://github.com/drujensen/fib。どこでも最適化の仕掛けをしないので、かなり公平なようです。私はGoの力を使う良い方法があることを知っていますが、なぜGoは他のコンパイルされ静的に型付けされた言語よりもずっと遅く見えるのでしょうか？私は私のマシンでGoと全く同じように見える11sで私のマシン上で確認することができます。

Answer 1

理由は、再帰的計算の組み合わせによる爆発です。アルゴリズム101では、彼らは通常、Dru Jensenの再帰アルゴリズムがフィボナッチ数を計算する恐ろしい方法である理由を説明します：http://www.cs.toronto.edu/~gfb/csc104/2016W/Lectures/CSC104.2016W.Week-7.Lecture.Fibonacci.I.pdf。 fibプロシージャは、呼び出されるたびに2回呼び出します。設計上、Goは末尾再帰を持たない：Tail call。設計上、Goは各ゴルーチンごとに非常に小さなスタックから始まり、爆発的に成長する必要があります。 No Goプログラマは、このアルゴリズムを使用したいと考えています。これは、次に最も遅いものより382,358,169倍遅く、最速よりも遅い18,593,103,127倍なので、パフォーマンスを犠牲にする最適化は無意味です。

$ go test fib_test.go -bench=. 
BenchmarkDruJensen-8    1 9482482595 ns/op 
BenchmarkPeterSO1-8  50000000   24.8 ns/op 
BenchmarkPeterSO2-8  2000000000    0.51 ns/op 

fib_test.go：ここ

は、いくつかのGoベンチマーク結果である

package main 

import (
    "fmt" 
    "testing" 
) 

// Dru Jensen: https://github.com/drujensen/fib 
func fib(n uint64) uint64 { 
    if n <= 1 { 
     return 1 
    } else { 
     return fib(n-1) + fib(n-2) 
    } 
} 

func BenchmarkDruJensen(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fib(46) 
    } 
} 

// PeterSO 
func fibonacci1(n int) uint64 { 
    f := uint64(0) 
    a, b := uint64(0), uint64(1) 
    for i := 0; i < n; i++ { 
     f, a, b = a, b, a+b 
     if a > b { 
      break 
     } 
    } 
    return f 
} 

func BenchmarkPeterSO1(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fibonacci1(46) 
    } 
} 

var fibonaccis = []uint64{ 
    0, 
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 
    2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 
    317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 
    14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 
    267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 
    4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 
    53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 
    591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 
    6557470319842, 10610209857723, 17167680177565, 27777890035288, 
    44945570212853, 72723460248141, 117669030460994, 190392490709135, 
    308061521170129, 498454011879264, 806515533049393, 1304969544928657, 
    2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 
    14472334024676221, 23416728348467685, 37889062373143906, 
    61305790721611591, 99194853094755497, 160500643816367088, 
    259695496911122585, 420196140727489673, 679891637638612258, 
    1100087778366101931, 1779979416004714189, 2880067194370816120, 
    4660046610375530309, 7540113804746346429, 12200160415121876738, 
} 

// PeterSO 
func fibonacci2(n int) uint64 { 
    return fibonaccis[n] 
} 

func BenchmarkPeterSO2(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fibonacci2(46) 
    } 
} 

Answer 2

TL; DR 私の結論今まで、我々はおそらく、反復の賛成で再帰を避けるべきであることアルゴリズムには主に、Goにテールコールの最適化がない限り、再帰を使用していない場合は、Goは好奇心からめちゃくちゃ速い:-)

のようです私はピーターのバージョンに別の（単純な）反復アルゴリズムを比較した（ところで、あなたは、46の正しいフィボナッチを取得するためにi <= nにi < nを変更する必要があります） 。興味深いことに、main.goで、コンパイルされたバリアントを使用していない場合は問題があります。 2番目の関数呼び出しは高速です。ランニングのコンパイルされていない変種、それは私の驚きに;-)少し速くなり、変数fを使用しますが、直接Xを使用していないことで

go test -bench . 
BenchmarkFibIt-4  100000000    18.5 ns/op 
BenchmarkFibP-4   50000000    29.1 ns/op 
BenchmarkFib-4     1  12008314197 ns/op 

：私たちはこのようなものです目的の結果を取得するためにベンチマークを使用する必要がありますmain.goは、コンパイルされたものとほぼ同じくらい速く、時にはさらに高速です！

私の結論は、Goにテールコールの最適化がない限り、主に反復アルゴリズムを優先して再帰を避けるべきであるということです。

main.go：

package main 

import (
    "fmt" 
    "log" 
    "time" 
) 

func fib(n int) uint64 { 
    if n <= 1 { 
     return 1 
    } 
    return fib(n-1) + fib(n-2) 
} 

func fibIt(n int) uint64 { 
    var x, y uint64 
    x, y = 0, 1 
    for i := 0; i < n; i++ { 
     // c <- x 
     x, y = y, x+y 
    } 
    return x 
} 

func fibP(n int) uint64 { 
    f := uint64(0) 
    a, b := uint64(0), uint64(1) 
    for i := 0; i <= n; i++ { 
     f, a, b = a, b, a+b 
     if a > b { 
      break 
     } 
    } 
    return f 
} 

func main() { 
    var start time.Time 
    var elapsed time.Duration 

    start = time.Now() 
    fibIt(46) 
    elapsed = time.Since(start) 
    fmt.Println("Iterative Fibonacci of 46 took", elapsed) 

    start = time.Now() 
    fibP(46) 
    elapsed = time.Since(start) 
    fmt.Println("Peter's Iterative Fibonacci of 46 took", elapsed) 

    start = time.Now() 
    fib(46) 
    elapsed = time.Since(start) 
    fmt.Println("Recursive Fibonacci of 46 took", elapsed) 
} 

main_test.go：

package main 

import (
    "testing" 
) 

func BenchmarkFibIt(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fibIt(46) 
    } 
} 

func BenchmarkFibP(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fibP(46) 
    } 
} 

func BenchmarkFib(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fib(46) 
    } 
}