google sparsehash

http://d.hatena.ne.jp/halo_w2/20050426#c

ここでhash_mapをこけにしたんですが、ふとGoogle CodeにSparse Hashがあることを思い出す。

http://sourceforge.net/projects/goog-sparsehash/

Sparse Hashは、空間効率を重視するsparse_hash_mapと、時間効率を重視するdense_hash_mapがあります。
ついでにSGIのhash_mapとほぼ同じインターフェースを提供しています。
ライブラリはヘッダだけなのですが、きちんとテストコードとベンチマークプログラムがあります。さすがgoogle。
んで、実行してみました。

% ./configure
% make CPPFLAGS="-O3 -march=athlon-xp"
% ./time_hash_map

(中略)

SPARSE_HASH_MAP:
map_grow 524 ns
map_predict/grow 201 ns
map_replace 114 ns
map_fetch 119 ns
map_remove 149 ns

DENSE_HASH_MAP:
map_grow 128 ns
map_predict/grow 28 ns
map_replace 22 ns
map_fetch 19 ns
map_remove 29 ns

STANDARD HASH_MAP:
map_grow 183 ns
map_predict/grow 127 ns
map_replace 48 ns
map_fetch 29 ns
map_remove 92 ns

STANDARD MAP:
map_grow 913 ns
map_predict/grow 842 ns
map_replace 326 ns
map_fetch 315 ns
map_remove 622 ns

おお、きちんと速いですね。
しかも空間効率を重視しているsparse_hash_mapでさえSTLのmapよりも数倍速い。
うーん、凄いですね。tcmallocは残念な結果になりましたが、これは使う価値ありそうです。