The Articles - Elegant C++

ようやくVisual Studio 2008がリリースされました。 また、Google Sparse Hash 1.0.2やGCC 4.2.2もリリースされていることなので、三度、パフォーマンス測定を行うことにします。今回は、素直にGoogle Sparse Hash 1.0.2に含まれているtime_hash_mapでパフォーマンス測定を行います。

先ずVisual Studio 2008ですが、Visual C++ 2008 Feature Pack Betaを用い、以下のコードを追加してstd::tr1::unordered_mapのパフォーマンス測定も行います。

#include <unordered_map>
using std::tr1::unordered_map;

template <class T>
struct hash : public std::unary_function<T, std::size_t>
{
  std::size_t operator()(T val) const { return val.Hash(); }
};

measure_map< unordered_map<HashObj, int, hash<HashObj> > >("TR1 UNORDERED_MAP", iters);

SPARSE_HASH_MAP:
map_grow               1953.0 ns
map_predict/grow       1031.0 ns
map_replace             437.0 ns
map_fetch               375.0 ns
map_fetch_empty         219.0 ns
map_remove              531.0 ns

DENSE_HASH_MAP:
map_grow                235.0 ns
map_predict/grow        172.0 ns
map_replace             141.0 ns
map_fetch               125.0 ns
map_fetch_empty          15.0 ns
map_remove              140.0 ns

STANDARD HASH_MAP:
map_grow                906.0 ns
map_predict/grow       1187.0 ns
map_replace             156.0 ns
map_fetch               141.0 ns
map_fetch_empty          32.0 ns
map_remove              516.0 ns

STANDARD MAP:
map_grow               1000.0 ns
map_predict/grow        906.0 ns
map_replace             172.0 ns
map_fetch               172.0 ns
map_fetch_empty          15.0 ns
map_remove              547.0 ns

TR1 UNORDERED_MAP:
map_grow               1141.0 ns
map_predict/grow       1203.0 ns
map_replace             156.0 ns
map_fetch               140.0 ns
map_fetch_empty          32.0 ns
map_remove              500.0 ns

次に、GCC 4.2.2ですが、こちらは以下のコードを追加してstd::tr1::unordered_mapのパフォーマンス測定も行います。

#include <tr1/unordered_map>
using std::tr1::unordered_map;

template <class T>
struct hash : public std::unary_function<T, std::size_t>
{
  std::size_t operator()(T val) const { return val.Hash(); }
};

measure_map< unordered_map<HashObj, int, hash<HashObj> > >("TR1 UNORDERED_MAP", iters);

SPARSE_HASH_MAP:
map_grow                350.0 ns
map_predict/grow        146.0 ns
map_replace              58.0 ns
map_fetch                65.0 ns
map_fetch_empty          15.0 ns
map_remove               86.0 ns

DENSE_HASH_MAP:
map_grow                 71.0 ns
map_predict/grow         22.0 ns
map_replace              14.0 ns
map_fetch                14.0 ns
map_fetch_empty           3.0 ns
map_remove               21.0 ns

STANDARD HASH_MAP:
map_grow                128.0 ns
map_predict/grow         83.0 ns
map_replace              24.0 ns
map_fetch                 6.0 ns
map_fetch_empty          14.0 ns
map_remove               54.0 ns

STANDARD MAP:
map_grow                542.0 ns
map_predict/grow        509.0 ns
map_replace             258.0 ns
map_fetch               253.0 ns
map_fetch_empty           9.0 ns
map_remove              489.0 ns

TR1 UNORDERED_MAP:
map_grow                162.0 ns
map_predict/grow        145.0 ns
map_replace              17.0 ns
map_fetch                19.0 ns
map_fetch_empty          22.0 ns
map_remove               48.0 ns

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