各種マップ実装の性能比較

今回は小ネタのmikioです。key/valueのレコードを高速に格納・参照・削除する仕組みが連想配列とかマップとか呼ばれて親しまれていますが、Tokyo Cabinetのオンメモリマップの性能をC++の各種実装と比較してみました。

以下の実装を対象として、100万レコードの格納と検索にかかる時間を計測します。キーと値は各8バイトの文字列とします。

Tokyo Cabientのオンメモリマップ（TCMAP）
STL（C++の標準テンプレートライブラリ）のmapとmulti mapとset
GNU拡張テンプレートのハッシュマップ
Googleのdense hashおよびsparse hash

テストコードはこちらに挙げておきます。具体的な操作としては、マップオブジェクトを生成し、バケット配列の要素数をレコード数と同じにチューニングし、ループを回してレコード群を格納します。なお、STLのマップ系コンテナは、ハッシュ表でなく木（赤黒木とか）で実装されていますので、バケット数のチューニングはできません。

結果は以下のようになりました。測定は20回行い、結果の中央10件の平均を代表値としています。単位は秒です。

	insert	find
Tokyo Cabinet	0.40563	0.25999
STL map	2.63157	1.51657
STL multi map	2.54474	1.46864
STL set	2.34127	1.43893
GNU hash map	0.75396	0.48303
Google dense hash	0.74089	0.41089
Google sparse hash	2.06608	0.47091

つまり何が言いたいかというと、TCMAPってば地味に高速だよと言いたいわけです。社内のデータマイニングチームではTCのDBMとしての機能はよく使われているのですが、TCのユーティリティAPIも結構捨てたもんじゃないよと、この場を借りて宣伝するものです。

念のため付け加えると、このテストの結果は実用的な比較ではありますが、各実装に対する操作の前提条件が微妙に異なるので、テストコードを見た上であくまで参考程度にとらえてください。TCMAPでは、格納したvoid*領域は内部でコピーされて呼び出し元のオブジェクトとは独立して保持されます。それに近い条件にするために、今回のテストではC++テンプレートの各実装でもstringオブジェクトをコピーして保持するようにしています。つまり、TCMAPでは内部的にmallocとmemcpyのオーバーヘッドがかかっていて、C++の各実装では内部的にstringのコピーコンストラクタのオーバーヘッドがかかっています。ハッシュ表の処理の他にこのようなオブジェクトのコピーにかかる処理が性能に無視できない影響を及ぼしていることは気に留めておいてくださいませ。

TCMAPの利点としては、C++だけでなくCからも使え、上記のように性能が高いことの他に、レコードを格納した順番を記憶しているということが挙げられます。特定のレコードの順番を先頭や末尾に付け替えることもできます。したがって、LRU（least recent use）のレコードを消去することができるので、Tokyo TyrantやTokyo Dystopiaのキャッシュ機構としても活躍しているのです。

ということで、happy hacking!