[C++] 細かい手動最適化 （けど、結構効果あるのね）

Optimize Your Code: Matrix Multiplication より
結果を見て 「へぇ」 と思ったので紹介。

ところで、このブログの方、Microsoft の C++ Shanghai team のデベロッパと書いてあるけど、Shanghai チームって上海のことなのかな？それともそういうコード名のプロジェクトがある？

紹介してるのは n×n の正方行列の積を求めるコード。

Version 1 はごく普通にループ回して結果を求めるコード。
何の工夫もなし。

Version 2 は内側のループで一時変数を使うようにしたちょっとした改良。
最初これを見たとき 「これくらいはオプティマイザが勝手に最適化してくれるんじゃないかな？」 と思ったんですが、してくれないんですね。
ちゃんと解説が書いてあります。
「”result” が “m1” か “m2” の別名になってる （言い換えると “result” が “m1” か “m2” と同じところを参照している） かどうかをオプティマイザには判断付かないので result[i][j] に毎回バカ正直にメモリ書き込みすることになる」
なるほど、そりゃそうだ。

Version 3 は Version 2 に後ろの行列を計算前にひっくり返しておいて、計算後に元に戻すという処理を加えたもの。
これまた、「いったい何の意味が？」 と思ったんですが解説を読んで納得。
「この最適化はトリッキー。（Version 2 のコードの） プロファイルを取ってみれば、多数のキャッシュミスしてるのがわかるはず。行列をひっくり返してから計算すると m1[i] と m2[j] のシーケンシャルアクセスだけになる。これによってメモリリードのパフォーマンスがものすごく良くなる」
なるほど、先読みキャッシュの機構があるってことを前提にすればシーケンシャルアクセスの方が速くなるわけですね。

Version 4 は、、、なんだこりゃ？
float と double 用に SSE3 を使った実装か。
もう、こうなると C++ じゃないなｗ
つか、_mm_hadd_ps とかってのは Visual C++ の標準機能だったのか。こんなの知らんかったよ。

あとはそれぞれを Visual C++ 2010 CTP の Parallel ライブラリとラムダ式を使って並列化した実装。
へぇ、C++ でもラムダ式が使えるようになるのか。
これって C++0x ？
ラムダ式の頭についてる [&] は何だ？
検索してみた。。。変数のキャプチャ方法を指定。= でコピー、& で参照。[&, hoge] のように書くと hoge をコピーで、それ以外を参照で、といった指定もできる。
C++ もすごいことになっていくなぁ。

で、500×500の行列でやってみた表が載っています。
個人的には、Version 3 の改良がかなり効果があるのが意外でした。特に long long や double などサイズが大きくなるとかなり効果が出てますね。
500×500 の行列をひっくり返して、計算後にまた元にひっくり返して元に戻す、と処理量はだいぶ増えてるはずなのにメモリリードがシーケンシャルになるようにしただけでここまで明らかな効果があるとは。
あとは、2コアの Core2Duo だと Parallel の効果は微々たるものだけど、4コアの Xeon になるとかなりの効果があるっていうのも、まぁ、あたりまえだけれども、はっきりと数値に出てますね。