bit数え上げ

トリッキーなコードが早いとは限らないもので…

32bit の中の'1'bitの数を数え上げる、というコード。

おそらく普通なら以下のようにcounterを使うんじゃないかと思います。

counter版 enum_bits

int enum_bits(unsigned long x)
{
        int i;
        int counter = 0;

        for (i = 0; i< 32; i++) {
                if (x & 1) counter++;
                x >>=1;
        }
        return counter;
}

ちょっとトリッキーに、

rotate版 enum_bits

inline rotate_right(unsigned long x)
{
        asm ("ror $1, %0" : "=r" (x) : "0" (x));
        return x;
}

int enum_bits(unsigned long x)
{
        int i;
        int acc = x;
        register int s=x;

        for (i = 0; i< 31; i++) {
                acc += (s = rotate_right(s));
        }
        return -acc;
}

ローテート使ってみます。ループ回数も減ってるし、条件分岐も無いし、いい感じ！

コンパイルしてみると…

gcc version 4.0.2 20050901 -O4付きでコンパイルしてみました。ターゲットは、model name : Intel(R) Pentium(R) 4 CPU 3.20GHz

まずはcounter版。ループの部分は

.L13:
        movl    %edx, %eax
        andl    $1, %eax
        cmpl    $1, %eax
        sbbl    $-1, %edi
        shrl    %edx
        decl    %ecx
        jne     .L13

gccの賢さにめまいがします。キャリ付き演算で条件分岐を消し去ってます（しかも減算で逆条件を補正してる…）。す、すごい。

一方で rotate版は以下のようになります。

.L13:
#APP
        ror $1, %eax
#NO_APP
        addl    %eax, %ecx
        decl    %edx
        jne     .L13

むうう、そのまんまだけど勝ててそう。

…んが！？

time で計ってみると、なんとなく「あれれ？」。counter版の方が速くないかい？
私はあきらめが悪いので執念深くrdtscでクロック数を計ってみます。

10000回平均でのクロック数

	counter版	rotate版
クロック数	240	311

ショ、ショック…
コードだけ見ると反対のような気がするけど、同時発行命令や分岐予測の問題なんでしょうか？むむむ、、、最近のプロセッサはよくわからないです。
まじめにIntelのマニュアル読んでみるかな…

追記

しかも、、counter版、何も32回も回る必要ないじゃん。

int enum_bits(unsigned long x)
{
        int counter = 0;

        for (; x; x>>=1) {
                if (x & 1) counter++;
        }

        return counter;
}

L13:
        movl    %edx, %ebx
        andl    $1, %ebx
        cmpl    $1, %ebx
        sbbl    $-1, %ecx
        shrl    %edx
        jne     L13

orz..... もう寝る

しかもしかも！

paralell版

int enum_bit(unsigned long x)
{
   int i;
   unsigned long mask[] = {
      0xaaaaaaaa,1,
      0xcccccccc,2,
      0xf0f0f0f0,4,
      0xff00ff00,8,
      0xffff0000,16 };

   for (i = 0; i< sizeof(mask)/sizeof(unsigned long); i+=2) {
      x = ((x & mask[i])>>mask[i+1]) + (x &~mask[i]) ;
   }

   return x;
}

L16:
        movl    -72(%ebp,%ebx,4), %esi
        movl    -68(%ebp,%ebx,4), %ecx
        addl    $2, %ebx
        movl    %esi, %eax
        andl    %edi, %eax
        notl    %esi
        shrl    %cl, %eax
        andl    %edi, %esi
        cmpl    $9, %ebx
        leal    (%eax,%esi), %edi
        jbe     L16

もういや。。。。まあ余計な記憶域が必要になりますが。。。

ちなみにこれが最速 176clkでした。
#unrolling したらもっと速いのかな。