プログラムTIPS

DEMO PROGRAM ヘキサドライブでは様々な研究開発をしています。その一部を紹介。

分岐しないコード(2008年4月15日)

昨今のCPUは10年前とは大きく変貌しています。
昔通用したアセンブラのテクニックや高速化のテクニックは
通用しなくなっていることが多いです。
 
たとえばPentium4に限って言えば、次のような現象が起こります。
値を8倍するコードです。
 
【左へ8bitシフト】
shl eax, 3
 
【2の3乗=8 を加算で表現】
add eax, eax
add eax, eax
add eax, eax
 
ぱっと見たら前者のほうが速そうに思いますが実は後者のほうが幾分高速です。
初めて見ると疑いたくなるような光景ですが・・・
これはPentium4の深いパイプラインが影響しているといえます。
 
このようにそれぞれのCPUに得手・不得手があり、
プログラマはそれに適応していくことが求められます。
ゲームの世界でも同じく高速なプログラムを書くことは大切です。
1秒間に60枚ものCG画像を生成するわけですので、
限られた時間の中でCPUはベストを尽くさなければなりません。
プログラマには、より高速なコーディングが求められます。
 
そして今日のお題。「分岐しないコード」。
最近のCPUは流れ作業的に実行されているパイプライン仕様です。
つまり作業中に別のところへジャンプすると、
そこでCPUには作業の仕切り直しが発生します。
 
たとえば32bitの中の1が立っている数を数えるとき、
普通に考えたらこう書きますよね。

int value;
int bitCount = 0;
for( int i=0; i> i) & 1 ) bitCount++;
}

これを分岐無し(branch free)で書くとこうなります。
 

int value;
int bitCount;
value -= ( (value >> 1) & 0x55555555);
value = (((value >> 2) & 0x33333333) + (value & 0x33333333));
value = (((value >> 4) + value) & 0x0f0f0f0f);
value += (value >> 8);
value += (value >> 16);
bitCount = value & 0x3f;

forやifが一切ないプログラムですが、同じ結果が得られます。
アツいですね。
しかも前者のループを用いた方法よりもかなり高速です。
他にもソートや数値の飽和演算などにもこういったワザが有効です。
プログラミングにはパズルを解くような面白さも兼ね備えています。
もしその面白さがゲームを作りながら体験できるとしたら幸せですネ。

【免責事項】

本サイトが提供している情報に関しては、安全性等、いかなる保証もされません。 株式会社ヘキサドライブは、これらの情報をあなたが利用することによって生ずるいかなる損害に対しても一切責任を負いません。

【著作権】

本サイトが提供しているコンテンツについては、特に断りのある場合を除き、株式会社ヘキサドライブが著作権を有します。