読者です 読者をやめる 読者になる 読者になる

Javaで簡潔ビットベクトル(35)

Java

簡潔ビットベクトルの最新の論文を読んでみた。

Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences
Dong Zhou, David G. Andersen, Michael Kaminsky, SEA'13, 2013.

http://www.cs.cmu.edu/~dga/papers/zhou-sea2013.pdf

アイデアとしては、rankについては、従来と同じように階層化して管理し、selectは、rankを利用したCombined Samplingの考え方を採用している。ただ、それらを単純に実装するのではなく、丁寧に設計をして、最近のCPUのスペックを適切に生かせるようにしている。特にキャッシュミスに気をつけており、キャッシュミスを減らすようにしている。内容としても読みやすく、ハードウェアに対する理解が深まりました。特に、PopCountって専用の命令を使うとテーブル計算よりもだいぶ速いんやね。性能測定の結果を見ると、Plain TypeのBitmapとしては、rankとselectの両方とも最速のグループとなっていた。ただし、他のデータ構造よりもサイズが小さいのでバランスが良い。

Javaで設計しているとそこまで意識することはないですが、ブロックサイズとかはかなり影響すると思う。やはり、32bitアーキテクチャだと64bitの整数の処理には、32bitの整数の処理の2倍の時間がかかっているようだ。

実装しようかと思ったが、Intelの人なので、特許とか取られていないかに気をつけないといけない。もうちょっと調査する。