スライスの比較の記事を読んでいて、ほーと思ったのでメモ。
BCEで最適化されるとスライスへのアクセスが少し速くなるよ、という話。
参考
ここに書いてあることを要約して書いただけなので元記事読んだほうが良い説があります
はじめに
2つのスライスの比較として、以下の3つの関数を考えます。
1つはDeepEqualを使った場合で、あとの2つは自作した関数です。
func CompareSlices_Reflect(a, b []int) bool {
return reflect.DeepEqual(a, b)
}
func CompareSlices_General(a, b []int) bool {
if len(a) != len(b) {
return false
}
if (a == nil) != (b == nil) {
return false
}
for i, v := range a {
if v != b[i] {
return false
}
}
return true
}
func CompareSlices_BCE(a, b []int) bool {
if len(a) != len(b) {
return false
}
if (a == nil) != (b == nil) {
return false
}
b = b[:len(a)]
for i, v := range a {
if v != b[i] {
return false
}
}
return true
}
これらを適当にベンチマーク取ってみます。
長さ1000ぐらいのスライスを2つ用意して渡しました（ダミーのスライスを適当に作ってくれるライブラリとかあるんですかね）。
結果は以下です。
Benchmark_Reflect-8 20000 70942 ns/op
Benchmark_General-8 3000000 500 ns/op
Benchmark_BCE-8 3000000 417 ns/op
DeepEqualが圧倒的に遅いですね。これはスライスだけに使える関数じゃないので最適化されていないのは仕方ないと思います。
問題は下の2つです。CompareSlices_BCEの方がCompareSlices_Generalより17%ほど速いです。
違いは以下の行だけです。
b = b[:len(a)]
これを書くとBCEにより最適化されるようになり、以下の行でのBounds Checkが走らなくなり結果として速くなる、ということのようです。
if v != b[i] {
これだけで10%以上改善されるのはすごいなーと驚いたので、僕のような無知な人が他にもいるかもなと思い筆を執った次第です。
Bounds Check Elimination (BCE)
Go 1.7から導入されたらしいです。golangのコンパイラがより最適化されたコードを生成してくれるということらしい。
これも元記事読んだほうが良さそうですが、簡単にまとめておきます。
Bounds Check Elimination (BCE) In Golang 1.7 * Blog - Tapir Games
要するにスライスにアクセスするときに、通常はout of rangeなどのpanicの確認のために境界のチェックをしてるけど、ある状況下では不要になる、ということだと思ってます（違ったらすみません）。
package main
func f1(s []int) {
_ = s[0] // line 5: bounds check
_ = s[1] // line 6: bounds check
_ = s[2] // line 7: bounds check
}
func f2(s []int) {
_ = s[2] // line 11: bounds check
_ = s[1] // line 12: bounds check eliminatd!
_ = s[0] // line 13: bounds check eliminatd!
}
func main() {}
ビルド時にフラグを指定すると、Bounds Checkが走っているかどうかを表示してくれます。
$ go build -gcflags="-d=ssa/check_bce/debug=1" example1.go
# command-line-arguments
./11.go:5: Found IsInBounds
./11.go:6: Found IsInBounds
./11.go:7: Found IsInBounds
./11.go:11: Found IsInBounds
./11.go:17: Found IsInBounds
これを見ると、まずf2では行12と行13は境界チェックが不要になっています。これは行11により行12,13が必ずout of rangeにならないことが保証されるからです。
しかし、f1では行5は行6,7に対して何の保障もしないので全ての行で境界チェックが行われてしまいます。
rangeやfor文では賢くやってくれるようですが、まだ完璧ではなさそうです。
package main
func f1(s []int) {
for i := range s {
_ = s[i]
_ = s[i:len(s)]
_ = s[:i+1]
}
}
func f2(s []int) {
for i := 0; i < len(s); i ++ {
_ = s[i]
_ = s[i:len(s)]
_ = s[:i+1]
}
}
func f3(s []int) {
for i := len(s) - 1; i >= 0; i -- {
_ = s[i] // line 22: bounds check
_ = s[i:len(s)]
}
}
func main(){}
上の例ではf1,f2では境界チェックが全く発生しません。
しかし、f3のfor文ではindexを減らしていっているだけですが、行22で境界チェックが行われてしまいます。
また、rangeで回しているスライスに関しては賢く最適化されますが、以下のように同時に回すスライスに関しては今のところうまくいかないようです。
func ff(s []int) []int {
s2 := make([]int, len(s))
for i := range s {
s2[i] = -s[i] // line 6: bounds check, not smart enough.
}
return s2
}
func main() {}
s2に関してはlen(s)の長さで作成したことが保証されているのに、行6で境界チェックされてしまうようです。
そこで、以下のように変更します。
package main
func ff2(s []int) []int {
s2 := make([]int, len(s))
s2 = s2[:len(s)] // line 5: bounds check. A hint for the compiler.
for i := range s {
s2[i] = -s[i] // line 7: bounds check eliminatd!
}
return s2
}
func main() {}
先に一度スライスにアクセスしてコンパイラにヒントを与えることで、行7では境界チェックされなくなるようです。
これが「はじめに」でやっていたことです。
まとめ
BCEとか全然知らなくて面白いなーと思ったので書きました。
もし本記事を読んで興味を持った方がいたら元記事を読んだほうが良いと思います。
例も豊富で非常にわかりやすく書いてあります。