差分指し手生成とメモリコピーの高速化の基礎
■ 差分指し手生成とメモリコピーの高速化の基礎
差分指し手生成などをしようと思うと、それぞれの駒についての指し手をシリアル化(ここでは一次元の配列にまとめるの意味)する必要があります。
このとき、細切れになっているメモリを一箇所に集める必要があり、この部分をいかに高速化できるかが差分指し手生成が成功するかどうかの鍵になります。
■ 高速なメモリコピーとは？
どのへんの読者を対象にしていいのかわからないので、今回は基礎ということでメモリコピーの基本事項だけ解説します。
差分gencap(駒を捕獲する手)の指し手生成では、駒を捕獲することのできることがわかっている駒を対象に処理します。よって、メモリをコピーするマクロを用意することを考えます。またコピーされるサイズは(指し手が存在することがわかっているところを対象とするので)4バイト以上であり、コピーサイズ0ということはありません。
// メモリを高速にコピーするマクロ #define FastMemoryCopy(src,dst,size) …
このFastMemoryCopyをどうやって書くかというのが今日の問題です。
■ memcpy , ::CopyMemory
memcpyや::CopyMemoryを使うのは論外です。これらは普通はinlinine化されません。
ただし、memcpyほうは組み込み関数ですから、組み込み関数をinline化するコンパイルオプションをつければ埋め込まれることがあります。「ことがあります」というのは、埋め込まれる条件は結構微妙で、コピーするサイズがコンパイル時に確定している場合は埋め込まれるのですが、そうでない場合は埋め込まれたり埋め込まれなかったりで私にはその条件はよくわかりません。
■ forでストレートに書く
for(u32 i=0;i<size;++i) dst[i] = src[i];
これだとsize == 0のチェックが最初に入ります。これも論外です。
このsize == 0のチェックを入れないコードを書くことが大切です。
■ do〜whileで書く
u32 i=0;
do { dst[i] = src[i]; } while (++i < n);これも論外です。コンパイラは普通、これを一般的なループ構造だと認識できません。少なくともVisual C++2008(以下VC++)ではループ構造だと認識しません。よってループ向きの最適化はされません。
もう少し具体的に言うと、forで書いた場合は、rep movsに変換されますが、do〜whileではrep movesに変換されず、非常に遅いコードになります。(forで書いた場合よりはるかにひどいコードになります。)
memcpyも組み込み関数をinline化するオプションをつけてコンパイルした場合、うまくすればrep movsにはなるのでその場合には、結局、forでストレートに書くのと同等のコードにはなります。
■ __assume
forで書けばrep movsに変換されることを理解できている人ならば、VC++であれば__assumeを書いて、0チェックを省略するコードが生成されるかどうか試してみたくなるかも知れません。
__assume(size !=0); for(u32 i=0;i<size;++i) dst[i] = src[i];
残念ながら__assumeまわりの最適化は、Visual C++ 6のころから進歩していません。switch〜caseのdefault以外のところで__assumeを書いてもまず無駄です。よってこれも駄目。
■ assert
assert(size !=0); for(u32 i=0;i<size;++i) dst[i] = src[i];
assertは、gccでは最適化に影響があることがあるらしいですが(私はgccでは試していません)、VC++では少なくとも無意味です。よって、これもあり得ません。
■ _asm
_asm
{
mov ecx,size
mov esi,offset src
mov edi,offset dsc
rep movs dword ptr es:[edi],dword ptr [esi]
}これはforで書くよりは良いコードです。「インラインアセンブラで書くとレジスタ割り当てが阻害されてかえって遅くなるじゃん」と思う人がいるかも知れませんがそれは間違いです。
rep movsはどうせレジスタ固定ですから、レジスタ割り当て自体は阻害されていません。
しかし、たかだか数バイト(4バイトとか8バイト)のコピーを行なうためにrep movsは論外です。よって、この選択もありません。
■ loopをunrollする
int i;
for(i=0;i<n;i+=4)
{
dst[i+0] = src[i+0];
dst[i+1] = src[i+1];
dst[i+2] = src[i+2];
dst[i+3] = src[i+3];
}
if (n & 1)
dst[i++] = src[i++];
if (n & 2)
{
dst[i+0] = src[i+0];
dst[i+1] = src[i+1];
}これはforでストレートに書いたコードより遅いでしょう。何故なら、大きいメモリに対しては、rep movsに変換されるforのほうが有利だし、小さいメモリに関しては、forループでの事前条件チェック、脱出チェック、2回のifと4回の条件分岐が存在するからです。
loopのunrollというのはこんなことをすることではありません。
■ switch〜caseでストレートに書く
switch (size)
{
case 1:
dst[0] = src[0]; break;
case 2:
dst[0] = src[0]; break;
dst[1] = src[1]; break;
case 3:
…
// 小さい数に対してはunroll
// ある程度大きな数に対してはforでrep movsに変換して実行
case 10: case 11: case 12: case 13: …
for(int i=0;i<size;++i)
dst[i] = src[i];
break;
}caseラベルの値が密集しているのでテーブルジャンプに変換されることは保証されます。しかしこのコードだと事前にcaseラベル範囲内かどうかのチェックが入ります。これでは正解とは言えません。
あと、大きなサイズに対しては、forで書くより、_asmでrep movsにしてサイズの0チェックを省略すべきなのは言うまでもありません。
■ switch + __assume
switch (size)
{
…
default: __assume(0);
}VC++ならば、defaultに__assumeを書くのは基本中の基本ですね。これでcaseラベルの範囲外であるかのチェックは省略されます。必ず書きましょう。
また、デバッグ時は、これでcaseラベルにない値を渡して変なアドレスにジャンプするとデバッグするのが困難になるので次のように書きます。
default: #if defined(DEBUG) assert(0); #else __assume(0); #endif
しかしこれはまだ最善ではありません。
■ switch + __assume + case 0
switch(size)
{
case 0 : break;
case 1 :
dst[0] = src[0]; break;
…
}ダミーのcase 0を入れることを忘れてはいけません。何故なら、case文は0から始まらないとテーブルジャンプに変換されるときに、引き算が必要になるからです。例えばcase 0がなく、case 1から始まると、VC++では、dec命令がひとつ余計に入ります。そこでダミーのcase 0が必要になるのです。
コンパイラの最適化が甘いと言えば甘いのですが、case 0を入れるのは(バッドノウハウ的な)常識なので、必ず守りましょう。
もちろんまだまだ最善ではありません。
■ switch + __assume + case 0 + 64bit化
メモリコピーは、64bit環境のことを考えて可能な限り64bitレジスタが使われるようにする必要があります。例えば次のように書きます。
case 2 : ((u64*)dst)[0] = ((u64*)src)[0]; break; … case 5 : ((u64*)dst)[0] = ((u64*)src)[0]; ((u64*)dst)[1] = ((u64*)src)[1]; dst[4] = src)[4]; break; …
しかしこれだけでは不十分です。rep movsのほうもqwordで書く必要があります。
■ switch + __assume + case 0 + 64bit化 + 偶奇分け
当然、偶数と奇数で場合分けします。
// 大きなサイズのコピー
case 11: case 13: case 15: … // 奇数
dst[size-1] = src[size-1]; // 1つコピーしたあとfall through
case 10: case 12: case 14: … // 偶数
size/=2;
_asm {
mov rcx,size
mov rsi,offset src
mov rdi,offset dsc
rep movs qword ptr es:[rdi],qword ptr [rsi]
} break;ずいぶんマシになってきましたが、まだ満足いくものではありません。
■ switch + __assume + case 0 + 64bit化 + 偶奇分け + 8バイトアライメントのassert
あとは64bitレジスタでコピーすることになるので8バイトのアライメントを守るようにコーディングする必要があります。このメモリコピーを行なう前提条件として、8バイトのアライメントが守れているということであれば、メモリコピー自体に次のようなassertを入れるべきです。
assert((src & 7) ==0); assert((dst & 7) ==0);
■ switch + __assume + case 0 + 64bit化 + 偶奇分け + 4バイトアライメントで場合分け
また、8バイトのアライメントが守れていないなら(4バイトのアライメントは守れていると仮定して)、それらの場合に関して最適になるように場合分けをします。
具体的には、2段のswitchにするとテーブルジャンプが2回になってすごくもったいないので、1回のswitchで済むように、例えば次のように分岐させます。
assert(size < 32);
switch ( ((src & 4) << 3) + ((dst & 4) << 8) + size )
{
ここまで書ければ、メモリコピーに関してはまずは脱初心者と言えるでしょう。まだ注意すべきことはたくさんあるのですが、今回の記事の趣旨を超えるので割愛します。
あと、rep movsでアライメント境界をまたぐときのlatencyなどについてはプロセッサごとに異なるので、今回見てきたコードが最善とは限りません。
rep movsの開始時のlatencyが下がったり、アライメント境界をまたぐコストが低下したりすれば、下手な小細工をせずに単にrep movsでdwordずつ転送するほうが速いかも知れません。また小さなメモリコピーが頻発する場合は、swtich〜caseでジャンプテーブルにしているコスト自体が無視できないかも知れません。このへんバランスが難しいですね。
是非、いろんな環境で計測してみてください。
それでは、みなさん、さらなる高速化の道を目指して頑張ってください！
■ まとめ
今回は差分指し手生成で必須となる高速メモリコピーの基本について解説しました。
今回の内容には私の勘違いなどが含まれているかも知れないので、是非ご自分の目でも確認してくださいね！
