Intel CPU の popcnt 命令で性能激落ちくんの話
Intel CPU で popcnt 命令を連発するとレジスタの割り当て方によって性能がめっさ変わる,という話.
本の虫: ループカウンタを64bitにしたり、 バッファのサイズを定数にしたらパフォーマンス激落ちなんだけど何で?
と,その元ページ
c++ - Replacing a 32-bit loop count variable with 64-bit introduces crazy performance deviations - Stack Overflow
なんかぱっと見ても一瞬よくわかんなかったので適当にまとめ.
ちなみにここに書いてるのは確信度はそれなりにあるけどそれが正解かはわからない点に注意.
どこを見ればいいのか
まず,質問者は 32bit とか 64bit とか constant とかを気にしているけど,その辺りは全然関係なかった.
で,どこを見ればよかったかというと,それぞれの popcnt に対して割り当てられたデスティネーション・レジスタが 32bit 版と 64bit 版で違うところだった,と.
前提知識
x86 は第2ソース・オペランド(src2)とデスティネーション・オペランド(dst)が同一である,という下のような形式.
opCode src1, src2 # dst は src2 と同じ
例えば,ソース・オペランドを2つとる add 命令は
add %r8, %r9
という形になる.これを C 風味に直すと
r9 = r8 + r9
になる.
popcnt はどうなっているか
で,popcnt はどうなっているかというと,src2 がないので,
popcnt %r8, %r9
は,
r9 = popcnt(r8)
みたいな挙動をするはずなんだけど,どうも Intel CPU は r9 を src2 とみなすらしく,
r9 = popcnt(r8, r9) // 実際には popcnt 内の r9 は何も作用しない
みたいになる.
で,何が問題なのか
これだけではいまいち何が問題かわからないと思うけど,2つ並べるとその問題点が明らかになる.
popcnt %r8, %r9 popcnt %r10, %r9
これは本来,
r9 = popcnt(r8) r9 = popcnt(r10)
となって,依存関係がない*1ので並列実行できる(実際 AMD の CPU ではできてるらしい).しかし,dst を src2 とみなすと,
r9 = popcnt(r8, r9) /*  ̄ こいつと */ r9 = popcnt(r10, r9) /*  ̄ こいつ */
となって,上の popcnt の dst の r9 と,下の popcnt の src2 の r9 に依存関係がある(ようにみえる)ので並列実行できなくなる.
これが,性能低下の原因となってるらしい.
これ,実はけっこうやっかいな問題で,CPU 的には「真の依存」に見えるため,「偽の依存」のように実行時にレジスタ・リネーミングによっては依存関係が解消されない.
どうやったら解消するのか
解消法はそんなに難しくない.dst を別のレジスタに割り当てればおk.
popcnt %r8, %r9 popcnt %r10, %r11
こうすると,
r9 = popcnt(r8, r9) r11 = popcnt(r10, r11)
で,依存関係がなくなって並列実行できるようになる.
これはコンパイラが見てあげれば解決できない問題でもないけど,こんなことコンパイラにさせるかなー最適化に労力を集中させてあげようよ,と個人的にはちょっともにょる.
ほんとかよ,という話
元記事ではループカウンタを 64bit にしたらこの問題に見事にヒットして,32bit にしたらたまたま dst の割り当てが変わったので大丈夫でした,という話.
ただ,これはソース・オペランドを1つしかとらない命令全部が直面する問題.
こんな「隠れた依存」をそこかしこで作ったら性能下がりすぎて話にならなくなっちゃうはず.
なので,ソース・オペランドが1つの場合には普通「隠れた依存」なんてできないようにしてると思う.
とすると,ほんとにこんな作り方するかなーという疑問が残らなくもない.
Intel 的には新参命令なのでとりあえず設計楽な方で作ってます,まぁそんな連続して使う人いないでしょ,というスタンスなのかもしれない.しらんけど.
ま,そもそもほんとにこれが原因かはもっとちゃんと見ないとわからないわけですが.