The Articles - Elegant C++

Google Sparse Hashのversion 0.9.1がリリースされました。

前回の記事ではversion 0.6をLinux上(GCC)で性能比較を行いましたが、今回はversion 0.9.1をWindows上(Visual C++ 2005)で性能比較を行ってみました。

最適化オプションは/O2で、処理時間の測定にはWindows Server 2003 Resource Kit Toolsのtimeitを使用しました。

#include <iostream>
#include <sstream>
#include <map>
#include <hash_map>
#include <google/sparse_hash_map>
#include <google/dense_hash_map>

inline std::string toString(int n)
{
  std::stringstream stm;
  stm << n;
  return stm.str();
}

int main()
{
#if 1
  std::map<std::string, int> data;
#endif
#if 0
  stdext::hash_map<std::string, int> data;
#endif
#if 0
  google::sparse_hash_map<std::string, int> data;
#endif
#if 0
  google::dense_hash_map<std::string, int> data;
  data.set_empty_key("");
#endif
  
  for (int n = 0; n < 1000000; ++n) {
    data[toString(n)] = n;
  }
  
  for (int n = 0; n < 2000000; ++n) {
    data.find(toString(n));
  }
  
  return 0;
}

処理時間順の測定結果は次のとおりです。

google::dense_hash_map
Elapsed Time:     0:00:09.718
Process Time:     0:00:09.781

std::map
Elapsed Time:     0:00:10.734
Process Time:     0:00:10.875

stdext::hash_map
Elapsed Time:     0:00:10.937
Process Time:     0:00:11.046

google::sparse_hash_map
Elapsed Time:     0:00:13.906
Process Time:     0:00:13.828

前回同様、最も速かったのはdense_hash_mapでした。
stdext::hash_mapは意外にも、std::mapと大差ない結果でした。

最後に、ハッシュに限ったことではありませんが、ライブラリの処理速度は実装に依存します。
使用の際には、自分の処理系で、プロファイリングを行うことをお薦めします。

関連記事
・ハッシュコンテナ
・ハッシュコンテナ - Part2
・ハッシュコンテナ - Part3