はじめに
こんにちは、Go界のうまい棒です。昼間にTwitter眺めてたら次のような記事を見かけました。
結果はあくまでフィボナッチ数列をナイーブに実装した場合なんで、まあ明らかに遅くなるよなあと予想通りの実行結果でした。
件のプログラム
ナイーブにフィボナッチ数列を実装してますね。
package main
import "fmt"
func fib(n int) int {
if n < 2 {
return n
}
return fib(n-2) + fib(n-1)
}
func main() {
fmt.Println(fib(42))
}
これを実際にビルドして実行するとどれくらいかかるかというと、だいたい手元で2.5秒以上かかってますね。
% time go run fib1.go
267914296
go run fib1.go 2.55s user 0.06s system 94% cpu 2.763 total
なんで遅いのか
先のコードは最後が末尾再帰でない再帰呼び出しなので、コールスタックがめっちゃ積まれそうです。Goが再帰呼び出しが得意でないのは、Goランタイムのスタックサイズがデフォルトが小さく、かつスタックサイズの大きさを最小にするような最適化を行わないからです。さらにいうと、Goでは末尾再帰ですら最適化されません。
困ったらgo toolを使ってアセンブリを見てみると良いです。
$ go tool 6g -S fib.go > fib.asm
再帰の場合、途中のいろいろは抜かして関係しそうなところだけ抜粋。
"".fib t=1 size=128 value=0 args=0x10 locals=0x18
0x0000 00000 (fib1.go:5) TEXT "".fib+0(SB),$24-16
...
0x000f 00015 (fib1.go:5) CALL ,runtime.morestack_noctxt(SB)
...
0x001f 00031 (fib1.go:6) CMPQ AX,$2
...
0x002e 00046 (fib1.go:7) RET ,
...
0x003a 00058 (fib1.go:9) CALL ,"".fib(SB)
...
0x0055 00085 (fib1.go:9) CALL ,"".fib(SB)
...
0x0070 00112 (fib1.go:9) RET ,
今回のコードは普通の再帰ですが、見ての通りfibがどんどん呼ばれてコールスタックが深くなっていきます。これは末尾再帰のコード書いても同様のアセンブリになります。階乗の計算をするコードを書いてみます。
package main
import "fmt"
func fact(n, p int) int {
p = p * n
if n == 1 {
return p
}
return fact(n-1, p)
}
func main() {
fmt.Println(fact(10, 1))
}
このアセンブリを見てみます。
"".fact t=1 size=96 value=0 args=0x18 locals=0x18
0x0000 00000 (tailrec.go:5) TEXT "".fact+0(SB),$24-24
...
0x000f 00015 (tailrec.go:5) CALL ,runtime.morestack_noctxt(SB)
...
0x0024 00036 (tailrec.go:6) IMULQ AX,CX
0x0028 00040 (tailrec.go:7) CMPQ AX,$1
...
0x0037 00055 (tailrec.go:8) RET ,
...
0x004c 00076 (tailrec.go:10) CALL ,"".fact(SB)
...
0x005f 00095 (tailrec.go:10) RET ,
fibと同様のアセンブリコードになってますね。
Goという言語
@mayahjp さんとも話してましたが、そもそも「Goが速い」というのが間違いで、たとえば「Goはビルドは遅くない」「普通にやってもまあ遅くないしLLよりは速く書けがち」「並行プログラミングが楽にできる」というところがいいのであって、システムプログラミングなどには向いてますが、数値計算などには向いてませんし、そういったものをするために開発された言語ではありません。（ただ先のエントリのベンチマークを見ても最適化を掛けないCよりは実行速度速くなってますよ。）
今回のフィボナッチ数列でのベンチマークはやってる処理自体はごくごく小さな演算で、パフォーマンスに寄与するのは
- 関数呼び出し自体のパフォーマンス
- コールスタックの最適化
です。そういった意味でGoは
- 関数呼び出し自体はgoroutineの管理などもあり、そもそもがgoroutineを大量に呼べるようにスタックサイズがデフォルトで小さく設定されていて、かつ自動で管理するようにランタイムで調整が入る。
- Goではスタックトレースで表示されることが大事なので、敢えて最適化していない*1 （2015.02.23 訂正。鵜飼さんご指摘ありがとうございます。）
という状況なので仕方ないかなと思います。
もし今回のプログラムをアルゴリズムで最適化するのであればメモ化をするのが手っ取り早いでしょう。O(n)になります。
package main
import "fmt"
var mem = make(map[int]int, 100)
func fib(n int) int {
if n < 2 {
return n
}
if m, ok := mem[n]; ok {
return m
}
m := fib(n-2) + fib(n-1)
mem[n] = m
return m
}
func main() {
fmt.Println(fib(42))
}
これを実行すると0.12秒になりました。
% time go run fib4.go
267914296
go run fib4.go 0.12s user 0.04s system 89% cpu 0.178 total
ちなみにPythonで適当に書いても速いです。
def fib(n, mem):
if n < 2:
return n
if n in mem:
return mem[n]
m = fib(n-2, mem) + fib(n-1, mem)
mem[n] = m
return m
if __name__ == "__main__":
print(fib(42,{}))
実行すると0.01秒ですよ。十分速い。
% time python fib.py
267914296
python fib.py 0.01s user 0.01s system 92% cpu 0.024 total
おわりに
先のエントリの最後にもちょろっと書いてますが、マイクロベンチマークはそのベンチマークに特化した結果しか出ないので、あくまでマイクロベンチマークはマイクロベンチマークです。何が言いたいかというと、Nim使いたくなるようにその言語が得意とする領域のもっと良いサンプルで比較してほしいな、ということでした。おわり。
参考
