プログラムを高速化する話

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)』かなり書き足されているので興味のある人はこちらをどうぞ。

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

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


プログラムを高速化する話” への4件のコメント

  1. KMCの資料を見たのですが、58 of 120 の「立っているビットの数を数える(popcount)」がどうしても理解できません。A´ 01100101の上位4ビットの立っているビットの数は2だと思うのですが、ページの一番下の2進数表記では3になってますよね???私は何か勘違いしているのでしょうか?

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です