GolangでBucketized Cuckoo Hashingを実装してみた

先日、Cuckoo Hashingの記事を書いたところ、以下のご指摘を頂いたのでBucketized版も実装してみました。

bucketizedして性能バク上げしよう₍₍ (ง´･_･`)ว ⁾⁾

— まっちゃら (@matsu_chara) 2017年5月6日

Erlingssonらの論文にも述べられていますが、挿入した要素がテーブルサイズの50%に達すると性能が低下するそうです。 前回も述べましたが、挿入時のハッシュの衝突によって要素の追い出しが起きてしまうためですね。そこで、挿入できる数をひとつでなく複数個にする(本記事ではこれをbucketと呼ぶことにします)ことで、衝突しても用意したbucketの大きさだけそのまま挿入できるようにしたものがBucketized Cuckoo Hashingです。

Fotakisらによるとひとつのbucketに4つの要素まで詰め込めるようにした場合では97%まで空間効率を上げることができるそうです。 この論文中ではBucketized Cuckoo Hashingはd-ary Cuckoo Hashingと呼ばれており、d=4の場合で97%と述べられています。

実装

gist0b30182c97fa91f73174ebcf3baf7645

上記では結果が見やすいようにd=2としています。

ベンチマーク

せっかくなのでbucketized CuckooHashingを通常のCuckooHashingと比較してみます。 ここでは一様乱数で発生させた要素を挿入し、挿入時間を測定します。 測定内容を実環境の問題と合わせて考えるべきですが、実環境の問題はどんなのがあるんでしょうか…

挿入する要素数をテーブルサイズ×bucketサイズで除した値を充填率とし、充填率が大きくなったときに挿入時間がどのように変化するか測定します。
今回は限られたメモリ上でbucketizedするかしないかを決定することを想定し、テーブルサイズとbucketのサイズを以下とします。

[Normal CuckooHashing]
N       int64 = 100000 // テーブルの大きさ

[Bucketized CuckooHashing]
N       int64 = 25000 // テーブルの大きさ
BCKSIZE int   = 4     // bucketのサイズ

ベンチマークコードはGithubにあります。 ベンチマーク結果は以下です。

全体としてbucketizedしたほうが挿入時間が小さくなっていることがわかります。

References

• GolangでCuckoo Hashingを実装してみた
• Ross, Kenneth A. “Efficient hash probes on modern processors.” Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on. IEEE, 2007.
• Erlingsson, Ulfar, Mark Manasse, and Frank McSherry. “A cool and practical alternative to traditional hash tables.” Proc. 7th Workshop on Distributed Data and Structures (WDAS’06). 2006.
• Cuckoo hashing - wikipedia
• Fotakis, Dimitris, et al. “Space efficient hash tables with worst case constant access time.” Annual Symposium on Theoretical Aspects of Computer Science. Springer Berlin Heidelberg, 2003.