Performance map vs set vs unordered_map

[out]

camper schrieb:

gerüchteküche schrieb:

out schrieb:

Wer das Programm mal testen will...

kriegt einen Segfault (nachdem der MSVC-Blödsinn in Zeile 128 korrigiert wurde).

Vergessen, test.txt vorzubereiten?

Ich erhalte (g++-4.8.1 -O3 -march=native)
Laufzeit set_string: 34.05ms
Laufzeit unordered_set_string: 8ms
Laufzeit set_int: 28.15ms
Laufzeit unordered_set_int: 15.2ms
mit ANZ=100000

Ich hab ja find vergessen. Dass das keinem aufgefallen ist . Der neue Quellcode:

#include <algorithm>
#include <chrono>
#include <fstream>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <unordered_set>
#include <string>
#include <vector>
using namespace std;

class stopwatch
{
    std::chrono::time_point<std::chrono::high_resolution_clock> last_;
public:
    stopwatch()
    {
        start();
    }
    void start()
    {
        last_ = std::chrono::high_resolution_clock::now();
    }
    std::chrono::milliseconds::rep elapsed() const
    {
        auto t = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::milliseconds>(t - last_).count();
    }
};
struct random_number
{
    int lower_bound;
    int upper_bound;
    random_device& engine;

    random_number( int lower_bound, int upper_bound, random_device& engine ) : lower_bound(lower_bound), upper_bound(upper_bound), engine(engine) {}

    int operator()()
    {
        uniform_int_distribution<int> distribution( lower_bound, upper_bound );
        return distribution( engine );
    }
};

template<typename Elementtyp, typename Set>
void test( const string& what, unsigned loops, unsigned anz_elemente, const vector<Elementtyp>& daten, Set& set_ )
{
	stopwatch sw;
	float zeit = 0.f;

	for(auto i=0; i!=loops; ++i)
	{
		Set s = set_;
		sw.start();

		// Daten einfuegen
		for(auto it=begin(daten); it!=begin(daten)+anz_elemente; ++it)
			s.insert( *it );

		// Daten suchen
		for(auto it=begin(daten); it!=begin(daten)+anz_elemente; ++it)
			s.find( *it );

		zeit += sw.elapsed();
	}
	cout << "Laufzeit " << what << ": " << zeit << "ms" << '\n';
}

int main()
{
    const auto LOOPS = 20;
    const auto ANZ_ELEMENTS = 100000; // max. 566321, weil test.txt 566321 Woerter hat.

	// Teste strings
	{
		ifstream file("test.txt"); // http://www.gutenberg.org/files/2600/2600.txt
		const vector<string> daten( (istream_iterator<string>(file)), (istream_iterator<string>()) );

		set<string> set_string;
		test( "set_string", LOOPS, ANZ_ELEMENTS, daten, set_string );

		unordered_set<string> unordered_set_string;
		test( "unordered_set_string", LOOPS, ANZ_ELEMENTS, daten, unordered_set_string );
	}

	// Teste ints
	{
		const auto lower_bound = 0;
		const auto upper_bound = 100000000;
		vector<int> daten( ANZ_ELEMENTS );
		generate_n( begin(daten), ANZ_ELEMENTS, random_number(lower_bound,upper_bound,random_device()) );

		set<int> set_int;
		test( "set_int", LOOPS, ANZ_ELEMENTS, daten, set_int );

		unordered_set<int> unordered_set_int;
		test( "unordered_set_int", LOOPS, ANZ_ELEMENTS, daten, unordered_set_int );
	}
}

Nun bekomme ich:
set<string> ==> 9536ms
unordered_set<string> ==> 6231ms

set<int> ==> 22162ms
unordered_set<int> ==> 12120ms

Wieso ist das mit Ganzzahlen so langsam

Würdest du es bitte nochmals testen, camper.

[out]

out schrieb:

Wieso ist das mit Ganzzahlen so langsam

Ah, ok, das liegt daran, dass der random_device wirklich ziemlich gute Zufallszahlen erzeugt, da kommen fast keine doppelten vor . In der test.txt Datei sind logischerweise viele Wörter doppelt.

[out]

out schrieb:

out schrieb:

Wieso ist das mit Ganzzahlen so langsam

Ah, ok, das liegt daran, dass der random_device wirklich ziemlich gute Zufallszahlen erzeugt, da kommen fast keine doppelten vor . In der test.txt Datei sind logischerweise viele Wörter doppelt.

Ach ich hab upper_bound ja auf 100 Mio gesetzt

[knivil]

Einfach mal mit VS 2013 Preview im Release Mode:

Laufzeit set_string: 1090ms
Laufzeit unordered_set_string: 290ms
Laufzeit set_int: 900ms
Laufzeit unordered_set_int: 370ms

[out]

knivil schrieb:

Einfach mal mit VS 2013 Preview im Release Mode:

Laufzeit set_string: 1090ms
Laufzeit unordered_set_string: 290ms
Laufzeit set_int: 900ms
Laufzeit unordered_set_int: 370ms

Welchen Quellcode hast du genommen knivil, den 1 oder den 2? Kann eigentlich nicht sein dass VS 2012 im Release so viel langsamer ist. :p

[camper]

out schrieb:

Würdest du es bitte nochmals testen, camper.

Laufzeit set_string: 1324ms
Laufzeit unordered_set_string: 282ms
Laufzeit set_int: 957ms
Laufzeit unordered_set_int: 297ms
mit der Anpassung

random_device rdevice{};
        generate_n( begin(daten), ANZ_ELEMENTS, random_number(lower_bound,upper_bound,rdevice) );

[gerüchteküche]

Laufzeit set_string: 2874ms
Laufzeit unordered_set_string: 663ms
Laufzeit better_unordered_set_string: 609ms
Laufzeit set_int: 3418ms
Laufzeit unordered_set_int: 1116ms
Laufzeit better_unordered_set_int: 1161ms

Mit

unordered_set<string, better::hash<string> > better_unordered_set_string;
test( "better_unordered_set_string", LOOPS, ANZ_ELEMENTS, daten, better_unordered_set_string );

Wobei der String-Hash einfach

std::size_t hash = 13;
while (*s)
    hash = hash * 101  +  *s++;

ist.

Das zeigt wieder, wie schlecht std::hash ist. (Der int-hash ist hier einigermassen akzeptabel, aber nur, weil der Inhalt selbst zufällig ist, was normalerweise ja nicht der Fall ist.)

[knivil]

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)

Das zeigt wieder, wie schlecht std::hash ist

Unterschied < 10%, so unglaublich schlecht scheint es nicht zu sein.

[gerüchteküche]

Test mit Google sparsehash:

Laufzeit set_string: 2879ms
Laufzeit unordered_set_string: 700ms
Laufzeit better_unordered_set_string: 634ms
Laufzeit google_sparse_hash_set: 1200ms
Laufzeit google_dense_hash_set: 534ms
Laufzeit set_int: 3565ms
Laufzeit unordered_set_int: 1194ms
Laufzeit better_unordered_set_int: 1225ms
Laufzeit google_sparse_hash_set: 1037ms
Laufzeit google_dense_hash_set: 215ms

Einfach includes hinzufügen und

google::sparse_hash_set<int> sparse_hash;
test( "google_sparse_hash_set", LOOPS, daten.size(), daten, sparse_hash );

google::dense_hash_set<int> dense_hash;
dense_hash.set_empty_key(-1);
test( "google_dense_hash_set", LOOPS, daten.size(), daten, dense_hash );

google::sparse_hash_set<string> sparse_hash;
test( "google_sparse_hash_set", LOOPS, ANZ_ELEMENTS, daten, sparse_hash );

google::dense_hash_set<string> dense_hash;
dense_hash.set_empty_key(std::string(1, '\0'));
test( "google_dense_hash_set", LOOPS, ANZ_ELEMENTS, daten, dense_hash );

Faktor 5!!!

[knivil]

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.

[gerüchteküche]

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.

[out]

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.

[gerüchteküche]

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.