ループカウンタを64bitにしたり、 バッファのサイズを定数にしたらパフォーマンス激落ちなんだけど何で？

c++ - Replacing 32bit loop count variable with 64bit introduces crazy performance deviations - Stack Overflow

stackoverflowで、興味深い質問が行われている。

簡単にまとめるとこうだ。std::uint64_t型の配列の各要素にx86-64のpopcnt(1になっているビット数を数える命令)を適用したい。

コードの肝心の部分を書くと、以下のようになる。

for (unsigned i=0;i<size/8;i+=4) {
    count+=_mm_popcnt_u64(buffer[i]);
    count+=_mm_popcnt_u64(buffer[i+1]);
    count+=_mm_popcnt_u64(buffer[i+2]);
    count+=_mm_popcnt_u64(buffer[i+3]);
}

ループの中で、バッファーの要素を4個づつ、Compiler Intrinsicに渡して、popcntを実行している。

さて、ここで奇妙な事実がある。Sandy/Ivy BridgeやHaswellで、ループカウンター用の変数であるiの型をunsigned int型とstd::uint64_t型とでベンチマークを取ってみると、質問者の環境で、unsigned int型の処理速度は26GB/sだが、std::uint64_t型では、13GB/sと、速度が激減するのだ。

これはGCCのバグなのだろうか。しかし、Clangで実験してみても、やはりunsigned intが26GB/sに対し、uint64_t型は15GB/sと、明らかに処理速度が違う。

更に良くわからないことがある。バッファーのサイズを保持するsize変数であるが、バッファーサイズは実行時の入力により決定されるため、定数ではない。しかし、バッファーサイズを決め打ちにしてsizeを定数にしてみると、なんと性能はunsignt intもuint64_tも共に20GB/sになる。Clangでは、どちらも15GB/sになる。

size変数をstaticにしてみると、uint64_t型でも、20GB/sにまで速度が改善する。

いったい何なのだ。

最も投票数の多い回答が興味深い。

この不思議なパフォーマンスの変化の理由は、IntelのSnady/Ivy Bridge, Haswellのpopcnt命令の、不必要なデータ依存によるものだという。

popcnt src, dest

とあったとき、なぜかIntelのCPUは、結果を出力する先のレジスターにデータ依存が発生するのだという。そのため、destに指定されたレジスターの値が定まるまで、後続のpopcntを並列実行できず、スループットが落ちるのだという。しかし、destはどうせ上書きしてしまい、直前の値は何の意味も持たないので、データ依存もクソもないはずなのだが。

現時点で、GCCはこのIntelのCPUの奇妙な挙動をまだ把握していない。コンパイラーはCPUごとのこのような特性を把握して、事前にxor reg, regなどしてデータ依存をそぎ落としておくべきなのだという。

AMDのCPUにはこのような不必要なデータ依存はないそうだ。

なぜループカウンター用の変数の型を64bitにしたり、バッファーサイズを保持する変数を定数にしたりするだけで結果が劇的に変わるかというと、コンパイラーのレジスタ割り当てが変わるためだという。

一体、何故こんな不必要なデータ依存が発生するのかという疑問であるが、回答者は、IntelのCPUはオペランドを二つ取る似通った命令を共通の方法で処理していて、popcntと何らかの命令を同じ枠組みで処理しているためではないかとしている。このようにすることで、プロセッサーの設計を簡単にできるのだとか。