超高速ビットカウント
ビットカウントとは、バイナリ列の中で、1の個数を調べる計算のこと。
たとえば、
01100011 01011101 00010011 10010110
の32ビットのうち、1の個数は16個、となる。
まず、よく知られているアルゴリズムを挙げてみる。
ビットを数える・探すアルゴリズム
高速ビットカウントその1
ここで挙がっているのは、
- 素直に1ビットずつ調べる方法
- 1が立っているビットの中で小さい順に調べる方法(i&(i-1)で立っているビットの中で最下位のビットがクリアできることを利用)
- 0~255、0~65535までの立っているビット数を予め計算してテーブル化
- 分割統治法(以下で説明)
である。実行速度は概ね下に行くほど速い様子。今回は分割統治法をさらに高速化するテクニックを述べる。
分割統治法によるビットカウント
簡単のため16ビットずつ数えることとする。
数えるビット列が下のようなとき、
ビット論理積&を使ってビットマスクをしてビット列を奇数ビット目と偶数ビット目の2つに分ける。
[0 1 0 1 0 0 1 0 ]
[ 1 0 0 1 1 1 1 1]
片方をビットシフト>>してやる
[ 0 1 0 1 0 0 1 0]
[ 1 0 0 1 1 1 1 1]
これを足し算してやると、
となり、2ビットごとにその2ビットで立っていたビットの数が格納される。
この一連の計算はa = (a & 0x5555) + ((a & 0xAAAA) >> 1);と書ける。
同様にして、ビット列を2ビットごとに分割する。
[01 00 01 10 ]
[ 01 10 01 01]
これを再びビットシフトして足してやると、
となり、4ビットごとにその4ビットで立っていたビットの数が格納される。
この計算はa = (a & 0x3333) + ((a & 0xCCCC) >> 2);
さらに4ビットごと、8ビットごとに分割して同様の計算をするともとの16ビットのビット列に立っていたビットの数として9が得られる。
これらの計算をまとめて書くと、
a = (a & 0x5555) + ((a & 0xAAAA) >> 1);
a = (a & 0x3333) + ((a & 0xCCCC) >> 2);
a = (a & 0x0F0F) + ((a & 0xF0F0) >> 4);
a = (a & 0x00FF) + ((a & 0xFF00) >> 8);
とするともともとaに立っていたビットの数がaに格納される。
この方法を使うと、ビットの数を数える操作において、時間のかかる処理である条件分岐･ループ･乗除算などが登場せず、しかも計算回数がビット数の対数になるため、非常に高速になるのである。
さらなる高速化
この分割統治法を用いた高速ビットカウントは、ビットカウントするデータ列がある程度長い場合、さらなる高速化を施すことができるというのがこの記事のメインテーマである。高速化が要求される場面ではデータ列がある程度長いのはよくあることなので、かなり有効だと言える。
まず、２回目までの畳み込み処理(ビット列から2ビット、4ビットで立っていたビット数を計算する処理)は、各ワードごとに行う。(ワード:2,4,8バイトなど、コンピュータにとって都合の良いデータサイズ。)
2回目の畳み込み処理が終わった時点で、4ビットごとにそこに立っていたビット数が記録されている。ここで、その4ビットに記録されている数値は最大で4(二進数で0100)であるが、4ビットで記録できる数の最大値は15(二進数で1111)である。そこで、3ワードのデータを足してしまう。こうしても、4ビットごとの最大値は12(二進数で1100)で15を越えないし、4ワード以上を足してしまうと15を超えるおそれがある。
そして、その足した結果をもう一度畳み込みすることで、１ワード分の畳み込みで3ワード分のビット数が求められることになる。
さて、3回目の畳み込みが終わった時点で、8ビットごとの最大値は8*3=24(二進数で00011000)で、8ビットの最大値は255(二進数で11111111)であるから、同様に10組のデータ(元は30ワード)を足すことができ、その後の計算が3*10倍速くなる。
4回目、5回目でも同じことができ、4回目には136組(元は4080ワード)、5回目は32896組(元は134215680ワード)のデータをまとめることができる。
こうすることで、1ワードあたりの畳み込みの回数は、(データ長が十分長い場合)1ワードが2バイトなら4回から約2.3667回、4バイト以上ならば5,6,…回から約2.3669回に減るため、ワード長が長いほどこのテクニックの恩恵を受けることができる(もっとも、ワード長あたりの実行時間が長ければ意味はないが)。
ちなみに
IntelのSSE4.2命令にはその名もズバリpopcntという立っているビットの数を数える命令が存在していて、とても高速である。
速度比較
ビットを数える各種アルゴリズムを比較してみる。
検証環境
- CPU:Intel Core i7-3770 @ 3.40GHz
- Memory:8GB
- Compiler:clang++ 3.4 option:-lm -O3 -std=c++11,popcntのみ-msse4.2を追加
結果
データ長:1GB=8Gbit
分割統治法のワード長:8バイト(これが最も高速だった)
- 素直に1ビットずつ調べる方法:4.8sec
- 1が立っているビットの中で小さい順に調べる方法:2.9sec
- テーブルを用いた方法,8ビット:1.3sec
- テーブルを用いた方法,16ビット:0.90sec
- 分割統治法:0.46sec
- 分割統治法(高速化ver):0.29sec
- popcnt命令(SSE4.2):0.19sec
アルゴリズムによって実行時間に10倍以上の開きがあることがわかる。
やはりCPUが直接処理するpopcnt命令は非常に高速であることがわかるが、一方で分割統治法の高速化verもそれなりに高速であり、SSE4.2命令が使えない環境では有効な代替になりうると言える。
参考文献
最終更新：2013年07月15日 01:27
