LAB

プログラムTIPS最適化Tips

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

RECRUIT

大阪・東京共にスタッフを募集しています。
特にキャリア採用のプログラマー・アーティストに興味がある方は下のボタンをクリックしてください

RECRUIT SITE