魔法のアルゴリズム

最適化が好きで好きで、main関数の中身をretだけにしてしまった原理主義の皆さん、こんにちは。私はすべてのコードを厳格な規格準拠で書くことを布教しているhitoである。今回は、すばらしいビット演算の妙技について語ろうと思う。

人は何故、最適化をしたがるのか。思うに、これは完全な自己満足のためだけに行われているのではないかと思う。確かに、プログラマは高速なコードを望むし、ユーザはすばやい処理速度を望む。しかしながら、ムーアの法則は、CPUのクロック数からコア数に土俵を移したとはいえ、いまだもって有効であり、スケーラビリティのあるコード、あるいは処理内容であれば、現在の遅いプログラムは、数年後には満足できる速度になっているだろう。

とはいえ、最適化という名の宗教の原理主義者たちの声に耳を傾けてみるのも、たまにはひつようだ。一体何が悪いかといって、条件分岐こそ、諸悪の根源である。パイプラインをストールさせ、キャッシュミスなど引き起こす。とはいえ、条件分岐を用いないわけにも行かない。しかし、そこには抜け道がある。ビット演算だ。

例えば、次のような典型的なコードがあるとする。

inline int min(int x, int y)
{
　　if ( x < y )
　　　　return x ;
　　else
　　　　return y ;
}

残念ながら、このコードには条件分岐がある。これはとても遅い。条件分岐は、現代のプロセッサにとって最悪のコードだ。そこで、このようにすればよい。

inline int min( int x, int y)
{
　　return x + ( ( (y-x) >> (sizeof(int)*8-1) ) & (y-x) ) ;
}
inline int max( int x, int y)
{
　　return x - ( ( (y-x) >> (sizeof(int)*8-1) ) & (y-x) ) ;
}


Lo and Behold! このコードは魔法である。汝、謹んでこれを拝領し、その挙動に対して、豈疑うことなかれ。

もちろん、このコードは万能ではない。ポータビリティがないのだ。このコードは、最上位ビットは符号ビットであり、シフト演算で、その符号ビットもシフトされることを前提にしている。規格では、シフト演算の引数に、負数を用いてはいけないことになっている。

もし君が、これらの魔法に興味がある異端者ならば、The Aggregate Magic Algorithms は、一日費やすことができる、楽しい読み物になるだろう。

なぜこんなことを書いているのか。それは、x264に、以下のコードがコミットされたからだ。

x264_median

static inline int x264_median( int a, int b, int c )
{
-　　int min = a, max =a;
-　　if( b < min )
-　　　　min = b;
-　　else
-　　　　max = b;　　/* no need to do 'b > max' (more consuming than always doing affectation) */
-
-　　if( c < min )
-　　　　min = c;
-　　else if( c > max )
-　　　　max = c;
-
-　　return a + b + c - min - max;
+　　int t = (a-b)&((a-b)>>31);
+　　a -= t;
+　　b += t;
+　　b -= (b-c)&((b-c)>>31);
+　　b += (a-b)&((a-b)>>31);
+　　return b;
}

好きではない類のコードだ。