Performance map vs set vs unordered_map

knivil schrieb:

gerüchteküche schrieb:

Faktor 5!!!

Normalerweise wird Geschwindigkeit meist mit Speicher eingekauft. Bei einem ernsthaften Vergleich nur eine Seite zu betrachten, ist grob fahrlaessig.

Das "dense" Hashset ist extrem auf Speicher optimiert ("2 bits/entry overhead").

Deshalb vermute ich auch, dass es schneller ist, weil das sparse eher statisch und auf Lookup spezialisiert ist, in diesem Test aber hauptsächlich eingefügt wird.

camper

Laufzeit set_string: 1401ms
Laufzeit unordered_set_string: 290ms
Laufzeit google_sparse_hash_set: 643ms
Laufzeit google_dense_hash_set: 268ms
Laufzeit set_int: 1142ms
Laufzeit unordered_set_int: 315ms
Laufzeit google_sparse_hash_set: 595ms
Laufzeit google_dense_hash_set: 81ms

übrigens auch ein Q9650 (linux 3.8.6 hardened), die Ergebnisse sind also mit denen von knivil einigermaßen vergleichbar.

knivil

gerüchteküche schrieb:

Das "dense" Hashset ist extrem auf Speicher optimiert ("2 bits/entry overhead").

Ich Weiss nicht, laut Doku fuer dense_hash_set:

dense_hash_set is distinguished from other hash-set implementations by its speed and by the ability to save and restore contents to disk. On the other hand, this hash-set implementation can use significantly more space than other hash-set implementations, and it also has requirements -- for instance, for a distinguished "empty key" -- that may not be easy for all applications to satisfy.

Und wenn man weiter sucht, dann findet man: http://sparsehash.googlecode.com/svn/trunk/doc/performance.html wobei gcc2.95.3 -g -O2 etwas veraltet ist.

knivil schrieb:

out schrieb:

Kann eigentlich nicht sein dass VS 2012 im Release so viel langsamer ist.

Den 2ten. Es macht einen Unterschied, ob mittels F5 oder mittles Strg+F5 gestartet wird, also Release Mode + Debugger oder einfach ohne Debugger. (Intel Core2Quad Q9650 3GHz)

Ok, danke das wusste ich nicht. Nun hab ich auch ca. deine und campers Ergebnisse.

camper

Das Ganze mal mit clang 3.3 (und libstdc++ von g++ 4.8.1)
Laufzeit set_string: 704ms
Laufzeit unordered_set_string: 302ms
Laufzeit google_sparse_hash_set: 691ms
Laufzeit google_dense_hash_set: 285ms
Laufzeit set_int: 554ms
Laufzeit unordered_set_int: 253ms
Laufzeit google_sparse_hash_set: 750ms
Laufzeit google_dense_hash_set: 108ms
Hier scheint clang mit sets irgendwelche Codemagie zu betreiben - doppelte Geschwindigkeit ist doch etwas unerwartet.

Clang ist doch echt krank. Faktor 2 für ordered und dann das:

Laufzeit set_string: 1555ms
Laufzeit unordered_set_string: 764ms
Laufzeit string_hash_set_string: 306ms
Laufzeit google_sparse_hash_set_string: 1383ms
Laufzeit google_dense_hash_set_string: 566ms
Laufzeit set_int: 1966ms
Laufzeit unordered_set_int: 862ms
Laufzeit google_sparse_hash_set: 1145ms
Laufzeit google_dense_hash_set: 263ms

struct string_hash {
  std::size_t operator()(std::string const& str) const
  { return std::accumulate(str.begin(), str.end(), 13,
	[](std::size_t h, unsigned char c) {return h*101 + c;});
  }
};
unordered_set<string, string_hash> string_hash_unordered_set_string;
test( "string_hash_set_string", LOOPS, ANZ_ELEMENTS, daten, string_hash_unordered_set_string );

Ethon

Hab mal std::set mit einem eigenen Allokator probiert der den Speicher für die Nodes aus einem Pool holt. Der Geschwindigkeitsboost war extrem.