これは何？

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。

go1.20

	for c := 0; c < size; c++ {
		if 128 <= data[c] {
			sum += int64(data[c])
		}
	}

data[c] が2回登場するのが好みではないけど、悪くはない。

DRY に

命名: dry

go1.20

	for c := 0; c < size; c++ {
		v := data[c]
		if 128 <= v {
			sum += int64(v)
		}
	}

data[c] が1回になるように一旦変数で受ける。
こちらが好みだけど一行増えてちょっとくやしい。

range を使う

命名: range

go1.20

	for _, v := range data {
		if 128 <= v {
			sum += int64(v)
		}
	}

この計算なら、for...range を使うのが普通だと思う（個人の感想です）。

range+分岐回避

命名: opt-range

go1.20

	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

go1.20

	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) でも手動最適化が功を奏していることに驚いた。