bit を高速に数える手法の比較 #C

はじめての投稿なので温かい目で見てください。

はじめに

本記事では bit の 1 の数を数える手法（アルゴリズム）の比較を行います。アルゴリズムの詳しい内容等は紹介せずあくまで処理速度の比較だけ行います。アルゴリズムの詳しい内容は下の参考文献に飛んでください。

アルゴリズム

Hamming weight で紹介されている 5 つの手法の演算回数について簡単にまとめます。A は有名なアルゴリズムをそのまま実装した状態です。Bと C は A の高速化である派生です。D は bit が立っている（1 になっている）数に比例して演算量が増えます。E は力技で，16bit すべての数に対して立ってる bit の数をメモしておき，64bit を 4 分割してその合計として求めています。メモリを多く使用し，64bit のように bit 数が多い場合はあまり高速ではありません。

手法	算術	乗算	比較 / 分岐	メモリ読み込み	特徴
A	24	0	0	0	単純な実装
B	17	0	0	0	乗算が遅い環境で優秀
C	12	1	0	0	乗算が速い環境で優秀
D	3n	0	1n	0	n は 1 になっている数，n が小さいと高速
E	9	0	0	4	16bit ごとに分けてメモリから読み取る

実験

実験環境・ソースコード

実験で使用したソースコードは GitHub にあげておきます。実験環境は下のとおりです。最適化については GitHub にあげている Makefile を見てください。

OS: Ubuntu 20.04.1
Kernel: 5.4.0-58-generic
CPU: Intel i5-3360M (4) @ 3.5 GHz
gcc: version 9.3.0 (C11)

実験 1 単純な比較

まずは全 bit に対して処理を行う安直な手法 N と 5 つの手法 A–E を C 言語に実装してタイムを計測します。1 億個の乱数に対してビットカウントを行いその処理時間を計測します。計測結果を表にまとめます。このときの立っている bit の平均は 32 です。（64bit の乱数でやりました。）この環境では C が B よりも高速でした。D はこの中では最も遅いですがそれでも N に比べて十分高速です。E も C と同等の速度ですが，メモリのことを踏まえると微妙に感じます。

手法	時間
N	4.447 s
A	0.541 s
B	0.467 s
C	0.386 s
D	3.025 s
E	0.393 s

実験 2 特殊環境下での比較

次に立っている bit の数が平均 0.5 の場合で測定します。D は 4 倍程度高速になったがもっと高速化されてもいいのかなと思いました。しかし，C などと比較しまだ遅いことからこの環境下では使用する必要性はないと思います。また，N は下位 bit から参照し 0 になったとき終了するようにしているため，高速化されたがそもそも N は使わない。

手法	時間
N	1.966 s
A	0.534 s
B	0.458 s
C	0.381 s
D	0.735 s
E	0.364 s

実験 3 `-march=native` による最適化

-march=native は特定の CPU を指定して高速化を行います。コンパイル後のバイナリデータを他の人と共有する場合は不適切ですが，自分の環境だけでの使用の場合はおすすめします。実験結果を示します。D 以外は少し高速化されました。注目できるのは D で，30 倍程度高速化されこの中で最速となっています。

手法	時間
N	4.257 s
A	0.380 s
B	0.235 s
C	0.181 s
D	0.091 s
E	0.212 s

実験 4 `_popcnt64`と`asm`

最後に _popcnt64 と __asm__ を利用して計測する。-march=native 無しの結果を N，有りの結果を Y に示しています。結果はどの自作関数より高速になりました。これらが使える環境では使用したほうが良いと思います。

手法	時間 (N)	時間 (Y)
`_popcnt64`	0.234 s	0.071 s
`__asm__`	0.234 s	0.071 s

まとめ

bit を高速に数える手法の比較を行いました。安直に数える場合に比べて 10 倍程度高速に数えるアルゴリズムであると確認できました。_popcnt64 と __asm__ はこれらに比べてより高速であることも確認できました。

bit を高速に数える 手法の比較