Pg. ビットカウントから学ぶ最適化の見知

0106-23

はお、椛です。

いつも泣いてばかりなのでたまには技術ネタをw

結論から言いますと、トリッキーな最適化は自爆するぞっ、てことを学びましょう。

なにかっていうと「真（1）になっているビットの数を数える」ことを一時期頑張って自己流の方法を模索していたんですね。こんなの書かないよってやつで満足して終わっちゃいました。

まー、考えてたところで最適解はすでに世に出回っていたのですが･･･ ちょっと牙を剥きたかったお年ごろ?

さっそく。

Javaの実装はこんな感じらしいです。

public static int bitCount(int i) {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}

もう、なんなんだ。

コードレベルでうまく命令数が少なくなるように最適化されてますね。定数にできるものはとことん定数にしてます。どんなことしてるかは調べてくださいな。

だいたい次のやり方で収束してるみたいです。

int numofbits(long bits)
{
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

Javaの最適化前のパターンで定数化とシフト演算にマスク処理の組み合わせですね。コードも見た目キレイでなんとなくやってることも想像がつくと思います。

55555555とか33333333とかどっから出てきたんだって思いますが、ちゃんとビットのことを考えての値です。同じ数字が並んでるように見えて、16進数なのでそう簡単な数値ではないのです。

で、Javaのアルゴリズムをもっと頑張っちゃったらこうなったようでw

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

おっとー、乗算が入ってきたよ。もうわかんないw

あんまりマスクしすぎてもレジスタ使っちゃうみたいで遅くなるようなんですが、そこまで考えて組めないっス･･･

もう、コンパイラの最適化を先読みしないと無駄なオプティマイズになりますね、こりゃ。

Intel CPUには POPCNT命令があるのでそっちのが速いみたいなのでそちらを。

PowerPCにはもともと popcountってレジスタがあるんすね。

gccなら組み込みで __builtin_popcount関数があるのでおとなしくこちらをw

C++には std::bitset::countがありますが C++20で std::popcountが使えるようです。STLってか boostちょー頑張ってる。

たぶん･･･ でしかないですけど、最適化を考慮するならばおとなしく一つずつ数えたほうがめっちゃ速そうな気がします。

たとえば、こんな感じに冗長っぽくしても･･･

int numofbits(long bits)
{
    int c = 0;
    for (int i = 0; i < sizeof(long) << 3; i++)
    {
        c += (bits & 1);
        bits >>= 1;
    }

    return c;
}

最適化で sizeof(long) << 3 が定数になったり、Zero初期化も無くなったり、スレッドセーフ? であれば、あわよくば for もなくなることでしょう〜。

⭐️

っと、自分で書いてみたのはマクロなんですけどやってることは一緒。上位ビットと下位ビットに分けてひたすら (n & 1) していくだけなので、マクロ展開すると凄いことになるのですがコレがまたうまく最適化されるから面白いものです。

いろいろな方法を試して自爆して成長していきましょ〜w

---

参考

Bit Twiddling Hacks