Performance map vs set vs unordered_map

[hnmmmmmmmmmm]

bei meinem tuple<int,int,int> sind die ints ca. im Bereich [-10,10] und myvector ist ca. 12 Elemente groß.

[gerüchteküche]

hnmmmmmmmmmm schrieb:

bei meinem tuple<int,int,int> sind die ints ca. im Bereich [-10,10] und myvector ist ca. 12 Elemente groß.

Vergiss set, nimm vector<int> und mach lineare suche.

vector<int> found; found.reserve(myvector.size()/3); // in C++14 mit VLA
for (auto i = myvector.begin(); i != myvector.end()-2; ++i)
{
  assert(abs(*i)<100 && abs(*(i+1))<100 && abs(*(i+2))<100)
  int perfect_hash = *i + 100**(i+1) + 10000**(i+2);
  if (std::find(found.begin(), found.end(), perfect_hash) != found.end())
    return false;
  found.push_back(perfect_hash);
}

Ansonsten hast du mit perfect_hash bereits die Hashfunktion.

[gerüchteküche]

out schrieb:

Hat jemand ein Beispiel für eine gute Hashfunktion. Soll das eigentlich auch heißen, das die default Hashfunktion bei unordered_set nicht gut ist?

Genau das. hash<int> ist einach die Identität (pfui).

Hier g++-4.8 -Ofast -std=c++11:

1s 93704ns: std::set
0s 621184ns: std::unordered_set
0s 457518ns: std::unordered_set + better:hash

Für 1000 zufällige Inserts mit mt19937 und genauso vielen zufälligen Lookups.

Testcode hier: http://ideone.com/0cHZMZ (und vergiss die Ausgabe auf ideone, da wird ohne Optimierungen kompiliert)

Hashfunktion:

template <typename T>struct hash;
template<> struct hash<unsigned> {
  std::size_t tables[256][4];

  template <typename Sseq>
  hash(Sseq&& q)
  {
    std::mt19937 gen(q);
    std::generate(&tables[0][0],
		    &tables[0][0] + sizeof(tables)/sizeof(**tables),
		    gen);
  }

  std::size_t operator() (unsigned x) const
  {
    return tables[(x>> 0)&0xff][0]^
           tables[(x>> 8)&0xff][1]^
           tables[(x>>16)&0xff][2]^
           tables[(x>>24)&0xff][3];
  }
};

[out]

Ich hab mal ein kleines Vergleichsprogramm geschrieben:
set<string> VS. unordered_set<string>
set<int> VS. unordered_set<int>

#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 T>
void set_string( T it_begin, T it_end )
{
	set< typename iterator_traits<T>::value_type > s;

	for(; it_begin!=it_end; ++it_begin)
	{
		s.insert( *it_begin );
	}
}
template<typename T>
void unordered_set_string( T it_begin, T it_end )
{
	unordered_set< typename iterator_traits<T>::value_type > us;

	for(; it_begin!=it_end; ++it_begin)
	{
		us.insert( *it_begin );
	}
}

template<typename T>
void set_int( T it_begin, T it_end )
{
	set< typename iterator_traits<T>::value_type > s;

	for(; it_begin!=it_end; ++it_begin)
	{
		s.insert( *it_begin );
	}
}
template<typename T>
void unordered_set_int( T it_begin, T it_end )
{
	unordered_set< typename iterator_traits<T>::value_type > us;

	for(; it_begin!=it_end; ++it_begin)
	{
		us.insert( *it_begin );
	}
}

int main()
{
	const auto LOOPS = 20;
	const auto ANZ_ELEMENTS = 100000; // max. 566321, weil txt 566321 Woerter hat.
	ifstream file("test.txt"); // http://www.gutenberg.org/files/2600/2600.txt
	const vector<string> strings( (istream_iterator<string>(file)), (istream_iterator<string>()) );

	// set_string
	{
		stopwatch sw;
		float zeit = 0.f;
		for(auto i=0; i!=LOOPS; ++i)
		{
			sw.start();
			set_string( begin(strings), begin(strings)+ANZ_ELEMENTS );
			zeit += sw.elapsed();
		}
		cout << "Laufzeit set_string: " << zeit/LOOPS << "ms" << '\n';
	}
	// unordered_set_string
	{
		stopwatch sw;
		float zeit = 0.f;
		for(auto i=0; i!=LOOPS; ++i)
		{
			sw.start();
			unordered_set_string( begin(strings), begin(strings)+ANZ_ELEMENTS );
			zeit += sw.elapsed();
		}
		cout << "Laufzeit unordered_set_string: " << zeit/LOOPS << "ms" << '\n';
	}

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

	// set_int
	{
		stopwatch sw;
		float zeit = 0.f;
		for(auto i=0; i!=LOOPS; ++i)
		{
			sw.start();
			set_int( begin(ints), end(ints) );
			zeit += sw.elapsed();
		}
		cout << "Laufzeit set_int: " << zeit/LOOPS << "ms" << '\n';
	}
	// unordered_set_int
	{
		stopwatch sw;
		float zeit = 0.f;
		for(auto i=0; i!=LOOPS; ++i)
		{
			sw.start();
			unordered_set_int( begin(ints), end(ints) );
			zeit += sw.elapsed();
		}
		cout << "Laufzeit unordered_set_int: " << zeit/LOOPS << "ms" << '\n';
	}
}

Wer das Programm mal testen will... einfach den Parameter ANZ_ELEMENTS einstellen und das Programm laufen lassen. Bei mir ist es so, dass set ca. ab 10.000 Elementen die Oberhand gewinnt.

Bei ANZ_ELEMENTS = 100000 habe ich folgende Zeiten (MSVC11):
set<string> ==> 470ms
unordered_set<string> ==> 488ms

set<int> ==> 1113ms
unordered_set<int> ==> 2483ms (Wundert mich doch ein bisschen )

[gerüchteküche]

out schrieb:

Wer das Programm mal testen will...

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

/usr/include/c++/4.8.1/debug/safe_iterator.h:360:error: attempt to advance
a past-the-end iterator 1000 steps, which falls outside its valid range
.

Objects involved in the operation:
iterator @ 0x0x7fff65818b90 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPKSsNSt9__\
cxx19986vectorISsSaISsEEEEENSt7__debug6vectorISsS7_EEEE (constant iterator);
state = past-the-end;
references sequence with type `NSt7__debug6vectorISsSaISsEEE' @ 0x0x7fff65818\
b90
}

Ich habe keine Lust, das zu debuggen, bitte nachbessern.

[camper]

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

[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.