【Go】パフォーマンスチューニングについて調べてみる

 プログラムが遅くなる原因アルゴリズムが遅い（計算量が大きい）
メモリ割り当ての問題
I/O操作（ディスクI/O、ネットワークI/O）
その他ハードウェアの問題
など、いろいろあるらしい。

パフォーマンス改善のためのアプローチ

アルゴリズム最適化
データ構造の最適化
キャッシュの利用
並列実行の適用

nの階乗を計算する関数のパフォーマンス改善をしてみる

再帰による計算（遅い）

func factorialReursive(n int) int {
	if n == 0 {
		return 1
	}
	return n * factorialReursive(n-1)
}

関数呼び出しのオーバーヘッドが大きいため遅い

for文による計算

func factorialIterative(n int) int {
	result := 1
	for i := 1; i <= n; i++ {
		result *= i
	}
	return result
}

関数呼び出しのオーバーヘッドをなくすため、for文で階乗を計算する。

メモ化再帰

var memo = make(map[int]int)

func factorialMemo(n int) int {
	if n == 0 {
		return 1
	}
	if result, found := memo[n]; found {
		return result
	}
	result := n * factorialMemo(n-1)
	memo[n] = result
	return result
}

関数呼び出しのオーバーヘッドはあるが、メモ化によりキャッシュを利用できるため、何度も同じ計算をする場合はパフォーマンスが上がりそう。

Goのベンチマークツールで計測する

package main

import "testing"

func BenchmarkFactorialRecursive(b *testing.B) {
	for i := 0; i < b.N; i++ {
		factorialReursive(20)
	}
}

func BenchmarkFactorialIterative(b *testing.B) {
	for i := 0; i < b.N; i++ {
		factorialIterative(20)
	}
}

func BenchmarkFactorialMemo(b *testing.B) {
	for i := 0; i < b.N; i++ {
		factorialMemo(20)
	}
}

b.Nはあくまでも関数の実行回数を表すもので、を関数の引数にするのは不適切らしい。
ただ、引数を20しか試していないのは微妙な気もする。

------------------ benchmark-test % go test -bench=.
goos: darwin
goarch: amd64
pkg: benchmark-test
cpu: Intel(R) Core(TM) i7-1060NG7 CPU @ 1.20GHz
BenchmarkFactorialRecursive-8           21050463                56.58 ns/op
BenchmarkFactorialIterative-8           63727635                18.29 ns/op
BenchmarkFactorialMemo-8                100000000               14.02 ns/op
PASS
ok      benchmark-test  5.469s

計測結果は、再帰>>繰り返し>メモ化再帰の順に遅かった。
63727635みたいな数字は、関数の実行回数を表しているらしい。

プログラムが遅くなる原因