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

Visual C++2005のstd::setとstdext::hash_setの速度

C++ speed 雑記

今日試しに使ってみたら、VC++2005のstd::setとstdext::hash_setがやけに遅かった。

doarWindows対応も一通り終ったので、VC++の上記クラスと検索速度を比較してみたのだが、結果は以下のようになった。

  • doar# 1.875 sec ※ 数値は、32587100要素(325871*100)を検索するのに掛かった秒数。以下同。
  • std::set# 33.062 sec
  • setext::hash_set# 24.469 sec

一桁違う。
計時方法自体はかなりテキトウで、入力データもソート済みのものを渡したのでDoubleArrayに有利な条件*1だったとは思うが、それにしても差が大きい。
g++(4.2.x)のstd::setとstd::tr1::unordered_setとでは、検索速度はほぼ同じ(数倍以内の差)か、std::tr1::unordered_setの方が早いくらいだったので、なおさらこの差を疑問に思う。


何故だろう。
単純に実装の問題か、それともオプションなどを指定すれば早くなったりするのだろうか?

蛇足

ちゃんと調べたわけではないけど、stdext::hash_setもstd::tr1::unordered_setも(std::setも?)、文字列要素としてはconst char*ではなく、std::string(あるいは他の文字列クラス)を渡す必要があるようだ。
前者の場合は、文字列としてではなく、ポインタ型(つまり32bitもしくは64bitの数値)として扱われるらしく、処理は早いが、同じ文字列でも異なるアドレスにある場合、検索に失敗してしまう(common lispで云えばeq比較)
テンプレート引数のハッシュ関数const char*型用にカスタマイズして渡せば、アドレス値ではなく文字列として比較するようにもできるのだろうが、デフォルトではないので若干面倒に思う。

*1:僕の実装では、多分メモリキャッシュの関係上、ソート済みのデータの方が未ソートのものより、だいたい数倍程度以上検索速度が早くなる傾向がある