この記事は Go Advent Calendar 2014 17 日目の記事です。
Go におけるパフォーマンスチューニングの話をします。
これらは Denco や Kocha などでのパフォーマンスチューニングの経験などから得た知見です。
処理系の話ではありませんのでご了承ください。
前提
-
プロファイリングを取った後、じゃあどうやって最適化するかというところの話です
「推測するな、計測せよ」
-
アルゴリズムやデータ構造は最適なものが選択されていると仮定します
小手先の最適化を行うよりアルゴリズム自体を変えたほうが圧倒的に良くなります。
-
この記事の各ベンチマークは Go 1.4 （go version go1.4 linux/amd64）で下記のコマンドにて取っています
go test -run NONE -bench . -benchmem -
ベンチマークの結果は環境に左右されるので、あくまで筆者の環境での結果です
メモリのアロケーション回数を減らす
Go のコードの中で、パフォーマンス低下の割合が大きいのがメモリのアロケーションです。
つまり、メモリのアロケーション回数を減らすとパフォーマンスが大幅に改善します。
package bench_test
import "testing"
func BenchmarkMemAllocOndemand(b *testing.B) {
n := 10
b.ResetTimer()
for i := 0; i < b.N; i++ {
s := make([]string, 0)
for j := 0; j < n; j++ {
s = append(s, "alice")
}
}
}
func BenchmarkMemAllocAllBeforeUsing(b *testing.B) {
n := 10
b.ResetTimer()
for i := 0; i < b.N; i++ {
s := make([]string, 0, n)
for j := 0; j < n; j++ {
s = append(s, "alice")
}
}
}
BenchmarkMemAllocOndemand 1000000 1953 ns/op 496 B/op 5 allocs/op
BenchmarkMemAllocAllBeforeUsing 3000000 571 ns/op 160 B/op 1 allocs/op
要素数が事前にわかっている場合には append を使わない
スライスに要素を詰めていく場合、append で追加していくよりインデックスを使ってスライスに代入してくほうが速くなります。
package bench_test
import "testing"
func BenchmarkFillSliceByAppend(b *testing.B) {
n := 100
b.ResetTimer()
for i := 0; i < b.N; i++ {
s := make([]int, 0, n)
for j := 0; j < n; j++ {
s = append(s, j)
}
}
}
func BenchmarkFillSliceByIndex(b *testing.B) {
n := 100
b.ResetTimer()
for i := 0; i < b.N; i++ {
s := make([]int, n)
for j := 0; j < n; j++ {
s[j] = j
}
}
}
BenchmarkFillSliceByAppend 500000 2694 ns/op 896 B/op 1 allocs/op
BenchmarkFillSliceByIndex 500000 2487 ns/op 896 B/op 1 allocs/op
例えば、channel を使わない
channel を使った排他制御より sync.Mutex や sync.RWMutex を使ったほうが速くなります。
package bench_test
import (
"sync"
"testing"
)
func BenchmarkExclusiveWithChannel(b *testing.B) {
c := make(chan struct{}, 1)
b.ResetTimer()
for i := 0; i < b.N; i++ {
c <- struct{}{}
// do something.
<-c
}
}
func BenchmarkExclusiveWithMutex(b *testing.B) {
mu := new(sync.Mutex)
b.ResetTimer()
for i := 0; i < b.N; i++ {
mu.Lock()
// do something.
mu.Unlock()
}
}
BenchmarkExclusiveWithChannel 20000000 70.2 ns/op 0 B/op 0 allocs/op
BenchmarkExclusiveWithMutex 100000000 21.1 ns/op 0 B/op 0 allocs/op
同様に同期処理も sync.WaitGroup を使ったほうが速くなります。
package bench_test
import (
"sync"
"testing"
)
func BenchmarkSyncWithChannel(b *testing.B) {
n := 10
c := make(chan struct{}, n)
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j := 0; j < n; j++ {
go func() {
// do something.
c <- struct{}{}
}()
}
for j := 0; j < n; j++ {
<-c
}
}
}
func BenchmarkSyncWithWaitGroup(b *testing.B) {
n := 10
var wg sync.WaitGroup
b.ResetTimer()
for i := 0; i < b.N; i++ {
wg.Add(n)
for j := 0; j < n; j++ {
go func() {
// do something.
wg.Done()
}()
}
wg.Wait()
}
}
BenchmarkSyncWithChannel 500000 3511 ns/op 160 B/op 10 allocs/op
BenchmarkSyncWithWaitGroup 500000 3086 ns/op 164 B/op 11 allocs/op
例えば、関数（メソッド）を呼ばない
Go は関数やメソッドの呼び出しが遅いです。数行程度のものであればコンパイラがインライン展開してくれるのですが、そうでないものが遅いです。
Denco のコード を例に上げると、再帰呼び出しにしたほうがすっきり書けるところを、敢えて goto を使うようにしてパフォーマンスを上げています。
正規表現はスイスアーミーナイフではない
Go の regexp パッケージは Ruby や Python などとは異なり、必ず線形時間で処理が完了するアルゴリズムを採用しています。
しかし、その代わりにとても遅くなってしまっているので、他の言語のように気軽に使ってしまうとかなりパフォーマンスが落ちてしまいます。
ですので、読みやすさなどとのトレードオフにはなりますが、本当に速度が必要な時には文字列のマッチングや置換などはできるだけ自前で書いたほうが懸命です。
package bench_test
import (
"regexp"
"testing"
)
func BenchmarkStringMatchWithRegexp(b *testing.B) {
s := "0xDeadBeef"
re := regexp.MustCompile(`^0[xX][0-9A-Fa-f]+$`)
b.ResetTimer()
for i := 0; i < b.N; i++ {
re.MatchString(s)
}
}
func BenchmarkStringMatchWithoutRegexp(b *testing.B) {
s := "0xDeadBeef"
isHexString := func(s string) bool {
if len(s) < 3 || s[0] != '0' || s[1] != 'x' && s[1] != 'X' {
return false
}
for _, c := range s[2:] {
if c < '0' || '9' < c && c < 'A' || 'F' < c && c < 'a' || 'f' < c {
return false
}
}
return true
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
isHexString(s)
}
}
BenchmarkStringMatchWithRegexp 2000000 643 ns/op 0 B/op 0 allocs/op
BenchmarkStringMatchWithoutRegexp 30000000 55.0 ns/op 0 B/op 0 allocs/op
番外編 1
パフォーマンスチューニングとは違いますが、goroutine を起動するにもコストがかかるので、何でも go を付ければ速くなるということはなく、軽い処理であればあるほどシーケンシャルに処理したほうが速くなります。
package bench_test
import (
"sync"
"testing"
)
func BenchmarkGoroutine(b *testing.B) {
n := 10
var wg sync.WaitGroup
b.ResetTimer()
for i := 0; i < b.N; i++ {
wg.Add(n)
for j := 0; j < n; j++ {
go func() {
wg.Done()
}()
}
wg.Wait()
}
}
func BenchmarkSequential(b *testing.B) {
n := 10
var wg sync.WaitGroup
b.ResetTimer()
for i := 0; i < b.N; i++ {
wg.Add(n)
for j := 0; j < n; j++ {
func() {
wg.Done()
}()
}
wg.Wait()
}
}
BenchmarkGoroutine 500000 3097 ns/op 164 B/op 11 allocs/op
BenchmarkSequential 10000000 224 ns/op 0 B/op 0 allocs/op
これがどの程度のしきい値で逆転するのかは興味があるところです。
番外編 2
for ループを回す際に条件式の部分に直接 len() を書いても、事前に変数に入れたものを使っても有意な差は出ません。
package bench_test
import "testing"
func BenchmarkLenDirect(b *testing.B) {
n := 1000
s := make([]string, n)
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j := 0; j < len(s); j++ {
_ = s[j]
}
}
}
func BenchmarkLenCached(b *testing.B) {
n := 1000
s := make([]string, n)
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j, length := 0, len(s); j < length; j++ {
_ = s[j]
}
}
}
BenchmarkLenDirect 1000000 1221 ns/op 0 B/op 0 allocs/op
BenchmarkLenCached 1000000 1221 ns/op 0 B/op 0 allocs/op
まとめ
こういう記事を鵜呑みにせず君だけのベンチマークを取ろう！
* この記事で使用したベンチマークは https://github.com/naoina/go-adventcalendar-2014-bench にあります。