Go
golang
GoDay 17

Golang パフォーマンスチューニング

More than 3 years have passed since last update.

この記事は Go Advent Calendar 2014 17 日目の記事です。

Go におけるパフォーマンスチューニングの話をします。

これらは DencoKocha などでのパフォーマンスチューニングの経験などから得た知見です。

処理系の話ではありませんのでご了承ください。


前提



  • プロファイリングを取った後、じゃあどうやって最適化するかというところの話です

    「推測するな、計測せよ」




  • アルゴリズムやデータ構造は最適なものが選択されていると仮定します

    小手先の最適化を行うよりアルゴリズム自体を変えたほうが圧倒的に良くなります。




  • この記事の各ベンチマークは 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.Mutexsync.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 などとは異なり、必ず線形時間で処理が完了するアルゴリズムを採用しています。

https://groups.google.com/forum/#!msg/golang-nuts/6d1maef4jQ8/yg4NY5qRtsMJ

しかし、その代わりにとても遅くなってしまっているので、他の言語のように気軽に使ってしまうとかなりパフォーマンスが落ちてしまいます。

ですので、読みやすさなどとのトレードオフにはなりますが、本当に速度が必要な時には文字列のマッチングや置換などはできるだけ自前で書いたほうが懸命です。

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 にあります。