Population count

先日の「Long.bitCount(long) の速度」の記事で比較した it.unimi.dsi.bits.Fast.count(long) だが、Wikipedia にも同様のコードが載っていてショック。

Hamming weight - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Hamming_weight

そのコードを一般化したものが次のページに載っている。

Counting bits set, in parallel - Bit Twiddling Hacks
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Long.bitCount(long) の速度

Java の Long.bitCount(long) が POPCNT にコンパイルされるとのことで、速度を簡易的に計ってみた。

比較対象は次の3つ。

1. Long.bitCount(long)
2. Long.bitCount(long) のソースをコピーして作った関数
3. it.unimi.dsi.bits.Fast.count(long) 

Oracle Java 7u6 での速度比（小さいほど速い）は、

1. 278
2. 2269
3. 1636

になった。

Long.bitCount(long) の呼び出しが BIOS コールのエミュレーションのように POPCNT に変換されているのかな？

ついでに dsiutils-2.0.7.jar の it.unimi.dsi.bits.Fast.count(long) も計測したんだけど、意外にも速かった。「broadword algorithm」というのは、Java ライブラリの実装アルゴリズムよりも速いんだろうか？

Broadword implementation of rank/select queries
http://vigna.dsi.unimi.it/papers.php#VigBIRSQ

ざくっと計ったので、参考まで。