リバーシとコンパイラ

 どーも、最近は就職活動もそこそこに、もっぱらプログラミングに打ち込んでおります。

主に題材はリバーシとコンパイラ。多分そのうちこのブログでもコンパイラ作成記、とかやります。
そういえばこの間大学の図書館で、適当に借りてきたコンパイラ作成の本があったんですが、コード生成に関する記述がほぼ皆無、レジスタ割付にいたってはゼロで、なめているのか、と。まぁドラゴンブック、お金ためて買いたいです。要る時に毎回図書館から借りてるんで。

リバーシのほうは今度プログラムコンテストをやろうと、友達といっているんで、ちょこちょこアイデアをまとめている感じです。

多分開発言語はc++かな。当初はdelphiで書こうと思ってたんですが、最適化機能が流石にdelphi弱いんでー。

ってなわけで、今日はリバーシのbit boardの話。

 bit boardっていうのは、要はボードゲームなんかで1マスを1bitに対応させるデータ構造のことです。

リバーシの場合、8×8マスで、64マス。ちょうど64bitになるので、色々都合がいいですよね。

で、今回紹介するのは着手可能マスを洗い出すビット演算です。現在のCPUの場合、一番コストが高いのは分岐です。分岐予測ミスーが頻繁に発生した場合、CPUのスケジューリングがうまくいかず、大きなペナルティを払ってしまうことになるのです。

そこで今回はdelphiでちょっとアイデアのテストコードを書いて見ました。これをCに移植したりするのは用意でしょう（shr は 右ビットシフト演算子です）。

    Blank := not(Black or White);

    Buf := ((Black shr 1)and White)shr 1;
    Dest :=  Dest or (Buf and Blank);
    Buf := (Buf and White)shr 1;
    Dest :=  Dest or (Buf and Blank);
    Buf := (Buf and White)shr 1;
    Dest :=  Dest or (Buf and Blank);
    Buf := (Buf and White)shr 1;
    Dest :=  Dest or (Buf and Blank);
    Buf := (Buf and White)shr 1;
    Dest :=  Dest or (Buf and Blank);
    Buf := (Buf and White)shr 1;
    Dest :=  Dest or (Buf and Blank);

black,white,blankはそれぞれ8bit符号なし整数型で、石があるところを1(blankは逆)にしています。
これで、右方向にひっくり返せる場合の、横一列の、着手可能位置を洗い出せます。MMXで書けば、一列ではなく、一面を一気に洗えるので、更に効率が上がるでしょう。大体メモリからL1キャッシュにデータを転送するのに高速でも数百ns以上かかることを考えれば、GHz単位のCPUであれば数百クロック分〜に相当します。これはもう、着手可能位置のテーブルを作るより断然早いでしょう。

更に言えばこれぐらいのコードであれば、コード自体がキャッシュに乗り切る可能性が極めて高く、更なる効率化を見込めます。ガッツリ先読みすれば、楽に1M単位でノードを読むことになるのは明白なので、その分効果も高いでしょう。

C++ならinline指定にすれば、呼び出しコストも馬鹿にならないかもしれません。

JUGEMテーマ：コンピュータ