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

人生の岐路に立ったとき、分岐せず思った道をまっすぐ突き進む!
そんな熱いあなたの心はきっとプログラマー色です

熱いプログラマ来たれ!パンチ
ヘキサドライブはそんなあなたを応援します。

posted by 管理人 at 23:05 | プログラミング