Go言語でのベンチマーク（補足）

はじめに

https://developers.eure.jp/tech/go-benchmark-evaluation/
弊社の社内ブログでGo言語によるベンチマークを書きましたが、あまり長々書けなかったのでここでフィボナッチ数（goroutine）の補足をします。

ベンチマークの導入やベンチマークの実行コマンドなどは上の記事を是非参照してください。

リポジトリ

今回のベンチマークで使用したリポジトリはこちらです。

書いたフィボナッチ数を求めるコード

フィボナッチ数とは

F_{n} = F_{n-1} + F_{n-2}\ \ (n \gt 2)\\
F_1 = 1, F_0 = 0

で求められる数列です。今回は4つの関数を用意しました。

For文でループする

FibonacciLoop

// FibonacciLoop returns a fibonacci value.
// The function is using loop to calculate.
func FibonacciLoop(n int) int {
	if n < 2 {
		return n
	}
	f1, f0 := 1, 0
	fn := f1 + f0
	for i := n; i >= 2; i-- {
		fn = f1 + f0
		f1, f0 = fn, f1
	}
	return fn
}

再帰式とはなんなのか、そういったものを考えずにFor文でループを回す形式です。
あまり綺麗なコードには見えないですが、実は一番効率が良いです。

Fibonacciといったら再帰式

FibonacciRecursive

// FibonacciRecursive returns a fibonacci value
// The function is recursively defined to calculate.
func FibonacciRecursive(n int) int {
	if n < 2 {
		return n
	}
	return FibonacciRecursive(n-1) + FibonacciRecursive(n-2)
}

すごく簡潔です。とても見やすいですが、関数オーバーヘッドに処理時間を食われている印象。

再帰式を並行処理する

goroutineの登場です。

FibonacciRecursiveGoRoutine

// FibonacciRecursiveGoRoutine returns a fibonacci value
// The function is recursively defined with go routine to calculate.
func FibonacciRecursiveGoRoutine(n int) int {
	if n < 2 {
		return n
	}

	chf1, chf0 := make(chan int), make(chan int)

	go func(f chan int) {
		f <- FibonacciRecursive(n - 1)
	}(chf1)
	go func(f chan int) {
		f <- FibonacciRecursive(n - 2)
	}(chf0)

	f1, f0 := <-chf1, <-chf0

	return f1 + f0
}

Fibonacciを求めるときに、2つの再帰式を用いるので、それぞれを並行で処理しています。
メモリ確保や無駄な処理が増えているので遅いです。

もっと再帰式を並行処理にしよう

FibonacciRecursiveContinuousGoRoutine

// FibonacciRecursiveContinuousGoRoutine returns a fibonacci value
// The function is recursively defined with go routine continuously
// to calculate.
func FibonacciRecursiveContinuousGoRoutine(n int) int {
	if n < 2 {
		return n
	}

	chf1, chf0 := make(chan int), make(chan int)

	go func(f chan int) {
		f <- FibonacciRecursiveContinuousGoRoutine(n - 1)
	}(chf1)
	go func(f chan int) {
		f <- FibonacciRecursiveContinuousGoRoutine(n - 2)
	}(chf0)

	f1, f0 := <-chf1, <-chf0

	return f1 + f0
}

再帰式を呼ぶ度に並行処理として実行しています。
一体、いくつのgoroutineを走らせれば気が済むのか、と言った感じです。そして、かなり遅いです。

何が言いたかったか

「推測するな、計測せよ」の通り、goroutineを実装して処理を並行化するのが速いとは限らないです。また、正当法な印象の強い再帰式もForループには勝てていません。

フィボナッチ数の計算という例題ではありふれたものですが、実際の実行速度を知らない方も居たでしょうから是非これを良い機会に「推測せず、計測」しましょう。

go test -bench . -benchmem の結果

$ go test -bench . -benchmem
PASS
BenchmarkFibonacciLoop                          100000000               12.2 ns/op             0 B/op          0 allocs/op
BenchmarkFibonacciRecursive                      3000000               436 ns/op               0 B/op          0 allocs/op
BenchmarkFibonacciRecursiveGoRoutine             1000000              1815 ns/op             192 B/op          2 allocs/op
BenchmarkFibonacciRecursiveContinuousGoRoutine           10000            130769 ns/op           16896 B/op        176 allocs/op
ok      github.com/eure/go-benchmark/fibonacci  6.255s