bitを高速に数える（手法の比較）
2020年12月31日
2022年5月15日
C
bit

はじめに

本記事では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になっている数
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__はこれらに比べてより高速であることも確認できました。

文献

  1. ソースコード(GitHub)
  2. Hamming weight (Wiki)
  3. x86_64でpopcnt/tzcnt/lzcntする【ビット演算テクニックAdvent Calendar 2016 5日目】 (Qiita)
  4. GCC (GNU)
  5. bitを高速に数える 手法の比較(Qiita)