KMC(京大マイコンクラブ)の人がKMCの合宿用の資料を作成されたのですが、その資料がとてもよく出来ているので紹介させていただきます。

プログラムを高速化する話(京大 マイコンクラブ)
http://www.slideshare.net/KMC_JP/ss-45855264

magic bitboardの話が出てきていて、「pext 命令の追加により実質役割を終えた」とあり、この人、よく勉強しているなーと感心しました。

ちなみにその話題自体は、私も去年の10月に以下の記事として取り上げました。

BMI使ってますか？
http://d.hatena.ne.jp/LS3600/20141011

これらは単なる偶然ではなく、CPU寄りの高速化は(メモリ)キャッシュの汚染の問題を除くと、SIMDやビット演算の問題に帰着することが多く、ビット演算の高速化技法をどれだけ理解しているかが高速化するための鍵となります。

そのビット演算の応用事例の一つとして、コンピューターチェスのプログラムが無視できない状況にあるので、「プログラムを高速化する」文脈において、magic bitboard〜pextの話が出てくるのは、ある意味、必然なのです。

ビット演算の技法がよくまとまっている有名どころの書籍としては『Hacker’s Delight』があります。邦訳『ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか』。これ、原著のほうは第二版が最近(2012年)に出ました。『Hacker’s Delight (2nd Edition)』かなり書き足されているので興味のある人はこちらをどうぞ。

[amazonjs asin=”443420159X” locale=”JP” title=”ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか”] [amazonjs asin=”B009GMUMTM” locale=”JP” title=”Hacker’s Delight (2nd Edition)”]

ちなみに第二版では確か、割り算を掛け算とビットシフトに変形する話題が追加されていたと思うのですが、その話題って私が『Windowsプロフェッショナルゲームプログラミング2【CD-ROM付】 (Game developer books)』(2003年)で書いた覚えがあります。世界的名著の『Hacker’s Delight』(第二版)に10年近くも先駆けて！どや！

とまあ、技術的紹介に始まり、私の自慢に終わるといういつもの流れでこの記事を終わりたいと思います。まる。