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

この記事は [Go Advent Calendar 2014](http://qiita.com/advent-calendar/2014/go) 17 日目の記事です。

Go におけるパフォーマンスチューニングの話をします。
これらは [Denco](https://github.com/naoina/denco) や [Kocha](https://github.com/naoina/kocha) などでのパフォーマンスチューニングの経験などから得た知見です。
処理系の話ではありませんのでご了承ください。

## 前提

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

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

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

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

* この記事の各ベンチマークは Go 1.4 （go version go1.4 linux/amd64）で下記のコマンドにて取っています

        go test -run NONE -bench . -benchmem

* ベンチマークの結果は環境に左右されるので、あくまで筆者の環境での結果です

## メモリのアロケーション回数を減らす

Go のコードの中で、パフォーマンス低下の割合が大きいのがメモリのアロケーションです。
つまり、メモリのアロケーション回数を減らすとパフォーマンスが大幅に改善します。

```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")
		}
	}
}
```

```text
BenchmarkMemAllocOndemand        1000000              1953 ns/op             496 B/op         5 allocs/op
BenchmarkMemAllocAllBeforeUsing  3000000               571 ns/op             160 B/op         1 allocs/op
```

## 要素数が事前にわかっている場合には append を使わない

スライスに要素を詰めていく場合、`append` で追加していくよりインデックスを使ってスライスに代入してくほうが速くなります。

```go
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
		}
	}
}
```

```text
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`](http://golang.org/pkg/sync/#Mutex) や [`sync.RWMutex`](http://golang.org/pkg/sync/#RWMutex) を使ったほうが速くなります。

```go
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()
	}
}
```

```text
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`](http://golang.org/pkg/sync/#WaitGroup) を使ったほうが速くなります。

```go
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()
	}
}
```

```text
BenchmarkSyncWithChannel          500000              3511 ns/op             160 B/op        10 allocs/op
BenchmarkSyncWithWaitGroup        500000              3086 ns/op             164 B/op        11 allocs/op
```

## 例えば、関数（メソッド）を呼ばない

Go は関数やメソッドの呼び出しが遅いです。数行程度のものであればコンパイラがインライン展開してくれるのですが、そうでないものが遅いです。
[Denco のコード](https://github.com/naoina/denco/blob/master/router.go#L167-L205) を例に上げると、再帰呼び出しにしたほうがすっきり書けるところを、敢えて `goto` を使うようにしてパフォーマンスを上げています。

## 正規表現はスイスアーミーナイフではない

Go の `regexp` パッケージは Ruby や Python などとは異なり、必ず線形時間で処理が完了するアルゴリズムを採用しています。

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

しかし、その代わりにとても遅くなってしまっているので、他の言語のように気軽に使ってしまうとかなりパフォーマンスが落ちてしまいます。
ですので、読みやすさなどとのトレードオフにはなりますが、本当に速度が必要な時には文字列のマッチングや置換などはできるだけ自前で書いたほうが懸命です。

```go
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)
	}
}
```

```text
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` を付ければ速くなるということはなく、軽い処理であればあるほどシーケンシャルに処理したほうが速くなります。

```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()
	}
}
```

```text
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()` を書いても、事前に変数に入れたものを使っても有意な差は出ません。

```go
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]
		}
	}
}
```

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