これは何？
https://qiita.com/kankikou/items/311328b36ff5a60ab19a
の記事とコメントを読んで面白かったので試してみた。
C++ だと -O2 があればほぼ差がなくなるのに、普通最適化が有効な Go だと差がなくならないのが面白いなと思って。
試してみたら、試したいこととは違う面白いことが見つかったので、記事にした。
計算とコード
計算内容は
- 指定された長さのスライスの
i番目にi & 0xffを入れる - シャッフルしてから「スライス内の 128 以上の値の合計を求める」を1000回やる。
- 整列してから「スライス内の 128 以上の値の合計を求める」を1000回やる。
というもの。
シャッフル後だと分岐予測が外れまくって遅く、整列後だと分岐予測が成功しまくるので速い（面白い）。
分岐予測絡みの辺りの実装を５つ用意した。
試行錯誤の内容を https://github.com/nabetani/branpena/tree/dev/goso 辺りに置いている（ブランチ変わるかも）。
C言語っぽく素朴に
命名: simple。
for c := 0; c < size; c++ {
if 128 <= data[c] {
sum += int64(data[c])
}
}
data[c] が2回登場するのが好みではないけど、悪くはない。
DRY に
命名: dry
for c := 0; c < size; c++ {
v := data[c]
if 128 <= v {
sum += int64(v)
}
}
data[c] が1回になるように一旦変数で受ける。
こちらが好みだけど一行増えてちょっとくやしい。
range を使う
命名: range
for _, v := range data {
if 128 <= v {
sum += int64(v)
}
}
この計算なら、for...range を使うのが普通だと思う（個人の感想です）。
range+分岐回避
命名: opt-range
for _, v := range data {
sum += int64(v) & func() int64 {
if 128 <= v {
return 0xff
}
return 0
}()
}
条件分岐が回避されそうな感じにしてみた。
条件演算子があれば sum += int64(v) & (128<=v ? 0xff : 0) のように書きたいところだけど、条件演算子が無いので上記のように 4行必要になる。
この if 128 <= v は条件ジャンプ命令にならないんじゃないかと期待。
rangen無し+分岐回避
命名: opt-simple
for c := 0; c < size; c++ {
sum += int64(data[c]) & func() int64 {
if 128 <= data[c] {
return 0xff
}
return 0
}()
}
あんまり意味ないかなと思いつつ、条件分岐回避しつつ range をやめてみた。
実行結果
実行環境は、MacBook Pro with Apple M1 Pro(非MAX)。
実行してみると（実行結果が間違っていたので修正した）
$ go run . 10000000
shuffled
simple: duration=33.61s sum=957487744000
dry: duration= 6.30s sum=957487744000
range: duration= 6.27s sum=957487744000
opt-range: duration= 5.03s sum=957487744000
opt-simple: duration= 5.03s sum=957487744000
sorted
simple: duration= 3.16s sum=957487744000
dry: duration= 6.29s sum=957487744000
range: duration= 6.44s sum=957487744000
opt-range: duration= 5.18s sum=957487744000
opt-simple: duration= 5.18s sum=957487744000
$ GOARCH=amd64 go run . 10000000
shuffled
simple: duration=33.85s sum=957487744000
dry: duration= 6.46s sum=957487744000
range: duration= 6.45s sum=957487744000
opt-range: duration= 5.26s sum=957487744000
opt-simple: duration= 5.27s sum=957487744000
sorted
simple: duration= 3.30s sum=957487744000
dry: duration= 6.47s sum=957487744000
range: duration= 6.47s sum=957487744000
opt-range: duration= 5.27s sum=957487744000
opt-simple: duration= 5.27s sum=957487744000
まったく非常に予想外の結果となった。
上記は一例だが、数回実行したところいずれも
- simple(シャッフル) が 30秒超え
- dry(両方)・range(両方) が 6秒台
- opt-range(両方)・opt-simple(両方) が 5秒台
- simple(整列済) が 3秒台
という結果となった。
驚きポイントを挙げると：
- ロゼッタの有無でほとんど速さが変わらない。
- simple と dry で全然速さが違う。
- 整列済みだと、dry より simple が速い。
辺り。（実行結果のミスに合わせて修正した）
この実験結果からわかることは
- DRY にするために変数で受けると、かえって遅くなることがある。
- C言語風の for を for...range に変えると、速くなることもあるけど遅くなることもある。
ということ。
アセンブラを眺める
ARM のアセンブラは見慣れないので、AMD64 のアセンブラを見ることにする。
アセンブラへの変換はこんな方法にした。
$ go build -gcflags="-S" main.go 2> hoge.s
当然最適化は無効にしない。
simple
まずは simple。
00005 XORL CX, CX ; CX （ループカウンタ）をゼロにする
00007 XORL DX, DX ; 合計値をゼロにする
00009 JMP 14 ; 無条件ジャンプ
00011 INCQ CX ; ループカウンタ加算
00014 CMPQ BX, CX ; ループ終了条件の調査
00017 JLE 46 ; ループ終了の条件ジャンプ
00019 MOVQ (AX)(CX*8), SI ; データを SI にロード
00023 NOP ; 何もしない命令
00032 CMPQ SI, $128 ; ロードしたデータを 128 と比較
00039 JCS 11 ; 比較結果で条件ジャンプ
00041 ADDQ SI, DX ; ロードしたデータを合計値に加算
00044 JMP 11 ; ループ頭に条件ジャンプ
00046 MOVQ DX, AX ; リターンする値を整備
00049 RET ; リターン
わかりやすい。
128 との比較結果で条件ジャンプ。
ループ内は、 NOP を無視して 平均 7.5命令。
dry と range
つづいて dry と range。dry と range は全く同じだった。
全く同じだったのでミスに気づいたので修正した。すいません。
00005 XORL CX, CX ; CX （ループカウンタ）をゼロにする
00007 XORL DX, DX ; 合計値をゼロにする
00009 JMP 33 ; 無条件ジャンプ
00011 MOVQ (AX)(CX*8), SI ; SI にデータをロード
00015 LEAQ (DX)(SI*1), DI ; DI ← DX+SI
00019 CMPQ SI, $128 ; ロードしたデータを 128 と比較
00026 CMOVQCC DI, DX ; 比較結果によっては DI を DX にコピー
00030 INCQ CX ; ループカウンタ加算
00033 CMPQ BX, CX ; ループ終了条件の調査
00036 JGT 11 ; ループ終了の条件ジャンプ
00038 MOVQ DX, AX ; リターンする値を整備
00041 RET ; リターン
LEA で積和（今回は単なる加算だけど）という x86 の伝統芸。
条件 move 命令 CMOVQCC で条件ジャンプを回避。
ループ内は、7命令。特に遅い命令もない。なんでこれで simple に負けることがあるのかがわからない。
opt-simple と opt-range
opt-simple と opt-range も同じだった。
00005 XORL CX, CX ; CX （ループカウンタ）をゼロにする
00007 XORL DX, DX ; 合計値をゼロにする
00009 JMP 47 ; 無条件ジャンプ
00011 MOVQ (AX)(CX*8), SI ; SI にデータをロード
00015 CMPQ SI, $128 ; ロードしたデータを 128 と比較
00022 MOVL $0, DI ; マスク を ゼロ にする
00027 MOVL $255, R8 ; R8 を 255 にする
00033 CMOVQCC R8, DI ; 比較結果によっては R8 を マスクにコピー
00037 INCQ CX ; ループカウンタ加算
00040 ANDQ DI, SI ; ロードしたデータをマスク
00043 ADDQ SI, DX ; マスクした値を合計に加算
00046 XCHGL AX, AX ; NOP。なにもしない。
00047 CMPQ BX, CX ; ループ終了条件の調査
00050 JGT 11 ; ループ終了の条件ジャンプ
00052 MOVQ DX, AX ; リターンする値を整備
00055 RET ; リターン
ループ内は 11命令。
こちらも条件 move 命令 CMOVQCC で条件ジャンプを回避。
00027 MOVL $255, R8 はループ外にしたほうが速いように見えるけど、どうだろう。
00022 MOVL $0, DI もよくわからない。 XORL DI, DI の方が速いんじゃなかったっけ。
条件分岐は意図通り回避されているけど、演算がごちゃごちゃしていて遅そう。
遅そうだけど、これで dry・range より速い。不思議だね。
C++ でも試す
MacBookPro 上で、clang と gcc でも試してみた。
foreach は for (auto const &v : data)。
simple は for (size_t i = 0, size = data.size(); i < size; ++i) 。
頭に opt- がついているのは
sum += ((v < 128) - 1) & v; という方法で条件分岐を回避。opt- がついていないのは普通に if 文。
詳細は略。このさきのグラフのみ。
本物の AMD64 でも試す
ベンチマークなのに Rosetta でしか試してないのは良くないよねと思い、Windows PC を引っ張り出してみて、go と C++ (cl.exe、つまり Visual Studio) でも試してみた。
詳細は略。このさきのグラフのみ。
グラフにまとめる
たくさんデータが手に入ったので、グラフにしてみた。
それにしても pyplot 高機能で素晴らしいけど好きになれない。
以下、図に入れ忘れたけど赤が shuffle。青が整列済み。横軸は時間で、長いほうが遅いということ。
繰り返し回数が違うので、 c++ と go の比較とかは意味がない。
Go on MBP(M1)
mbpgo.png
simple のときだけ分岐ペナルティを食らう。
opt- シリーズは go の最適化器に勝っている。
グラフ内の amd64 となっているのは、amd64 バイナリを Apple M1 上で動かしたという意味。
C++ on MBP(M1)
mbpc++.png
なぜか clang の圧勝。
clang は私の手による小手先の最適化は見破っていて速度に差がない。
gcc は私の最適化が功を奏している。
いずれも分岐ペナルティっぽい時間の差はない。
Go on Thinkpad
thinkpadgo.png
ia32 とあるのは、go で 386用バイナリを作って、64bit Windows 10 上で WOW64 を使って動かした、という意味。
なぜか ia32 だと全例で分岐ペナルティを食らっている。opt- シリーズでも回避できなかったらしい。
C++ on Thinkpad
thinkpadc++.png
こちらは amd64 も含めて opt- が無いものは分岐ペナルティを食らっている。
コンパイルオプションは
cl /O2 /Ox /Ot /EHsc /arch:AVX512 /std:c++17 /utf-8 /Wall
なので、最適化は効いているはずなんだけどなぁ。
go と異なり、 ia32 と amd64 の挙動に大きな差はない。
まとめと感想
分岐ペナルティがこんなに簡単に見えるようになるとは思っていなかったので驚いた。
そして、最適化器はわりと苦しんでいる様子。
若い go はともかく、gcc や cl.exe (Visual Studio) でも手動最適化が功を奏していることに驚いた。