Hashtabellen - Ein einfacher Performanzvergleich

Inhaltsverzeichnis[Anzeigen]

Bevor ich das Interface der Hashtabellen - offiziell ungeordnete assoziative Container genannt- genauer betrachte, will ich ihre Performanz mit der der geordneten assoziativen Container vergleichen. Die idealen Kandidaten dafür sind die std::unordered_map und ihr geordneter Pendant die std::map, da sie von allen assoziativen Containern am häufigsten zum Einsatz kommen.

Zugegeben, die acht Variationen von assoziativen Container bergen einiges an Verwirrungspotential. Zumal die Namen der neuen Container mit dem Namensbestandteil unordered sehr sperrig sind und viel Tipparbeit abverlangen. Der Grund für die sperrigen Namen ist einfach erklärt. Die ungeordneten assoziativen Container schafften es einerseits nicht mehr in den klassischen C++98-Standard. Andererseits wurden sie sehr vermisst, so dass sie in der Zwischenzeit viele Plattformen als C++-Erweiterung anboten. Damit waren die einfachen Namen bereits vergeben, so dass das C++-Standardisierungskomitee auf die sperrigen Namen ausweichen musste. Schön ist aber, dass die Namen der assoziativen Container einem einfachen Baukastensystem folgen. Dieses Baukastensystem habe ich im Artikel Hashtabellen genauer vorgestellt. 

std::map versus std::unordered_map

 Für einen einfachen Performanzvergleich bietet es sich an, sehr viele beliebige Werte aus einem std::map bzw. std::unorderd_map abzufragen und die Zeiten gegenüber zustellen. Genau das passiert in dem Programm.

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// associativeCompare.cpp

#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <unordered_map>

static const long long mapSize= 10000000;
static const long long accSize= 1000000;

int main(){

  std::cout << std::endl;

  std::map<int,int> myMap;
  std::unordered_map<int,int> myHash;

  for ( long long i=0; i < mapSize; ++i ){
    myMap[i]=i;
    myHash[i]= i;
  }

  std::vector<int> randValues;
  randValues.reserve(accSize);

  // random values
  std::random_device seed;
  std::mt19937 engine(seed());
  std::uniform_int_distribution<> uniformDist(0,mapSize);
  for ( long long i=0 ; i< accSize ; ++i) randValues.push_back(uniformDist(engine));

  auto start = std::chrono::system_clock::now();
  for ( long long i=0; i < accSize; ++i){
    myMap[randValues[i]];
  }
  std::chrono::duration<double> dur= std::chrono::system_clock::now() - start;
  std::cout << "time for std::map: " << dur.count() << " seconds" << std::endl;

  auto start2 = std::chrono::system_clock::now();
  for ( long long i=0; i < accSize; ++i){
    myHash[randValues[i]];
  }
  std::chrono::duration<double> dur2= std::chrono::system_clock::now() - start2;
  std::cout << "time for std::unordered_map: " << dur2.count() << " seconds" << std::endl;

  std::cout << std::endl;

}

 

In den Zeilen 19 - 22  fülle ich die std::map (Zeile 20)  und die std::unordered_map (Zeile 21) mit mapSize Schlüssel/Wert Paaren. In dem konkreten Fall ist mapsize zehn Millionen. Anschließend erzeuge ich einen std::vector mit einer Million Elementen, gefüllt mit zufälligen Werten zwischen 0 und mapSize. Die Zufallszahlen liefert der Zufallszahlengenerator engine(seed()) (Zeile 29), der durch seed auf einen zufälligen Wert initialisiert wird. In Zeile 30 kommt der Zufallszahlengenerator engine mit der Zufallszahlenverteilung unformDist zusammen: uniformDist(engine). uniformDist stellt, wie nicht schwer zu vermuten, die Gleichverteilung dar. Nun besitzt randValues eine Million zufällig erzeugte Elemente zwischen 0 und 10 Millionen, die gleichverteilt sind. Genau diese eine Million Elemente sind die Schlüssel der Werte, an denen ich für die std::map und die std::unordered_map interessiert bin. Wie schlagen sich die beiden assoziativen Container?

Ohne Optimierung

Zuerst übersetze ich das Programm ohne Optimierung mit dem aktuellen Microsoft Visual C++ Compiler und dem GCC Compiler. Hier sind die Ergebnsse.

Microsoft Visual C++ Compiler

windows

GCC Compiler

linux

Die Performanzunterschiede sind signifikant. Die std::unordered_map ist ca. um den Faktor 3 unter Windows und ca. um den Faktor 5 unter Linux schneller als seine Pendant std::map. Weitere Schlußfolgerungen zu den absoluten Zahlen möchte ich nicht ziehen, da die Programme auf verschiedene Rechner ausgeführt wurden.

Nun interessiert mich natürlich noch der optimierte Fall.

Maximale Optimierung

Um die ausführbaren Programme voll optimiert zu übersetzen, verwende ich bei dem cl.exe Compiler das Flag Ox, bei dem g++ Compiler das Flag O3. Die Performanzunterschiede zu dem unoptimierten Programm sind sehr beeindruckend.

Microsoft Visual C++

Durch das voll optimierte Übersetzen wird der Zugriff der std::map ca. um den Faktor 2, der der std::unordered_map ca. um den Faktor 6 schneller. Damit ist std::unordered_map und dem Faktor 11 schneller als std::map.

windowsOptimizePNG

GCC Compiler

Die Performanzverbesserungen bei dem GCC Compiler gestalten sich nicht ganz so drastisch. So ist optimierte Zugriff mit der std::map nur um ca 20% schneller, hingegen der mit der std::unordered_map um den Faktor 6.

linuxOptimzed

Wer vor lauter Zahlen wie ich den Überblick verloren hat, dem fasse ich hier nochmals alles in einer Tabelle zusammen.

Die nackten Zahlen

Der Einfachheit halber habe ich die Werte auf drei Nachkommastellen gerundet. Die zwei letzten Spalten stehen für die ausführbaren Programme, die ich mit maximaler Optimierung unter Windows (cl.exe /Ox) bzw, mit maximaler Optimierung und Linux (g++ -O3) erzeugt habe.

comparisonTable

Wie geht's weiter?

Im Artikel Hashtabllen schrieb ich ein bisschen oberflächlich, dass die ungeordneten assoziativen Container ein ähnliches Interface wie die geordneten assoziativen Container anbieten. Das stimmt nicht ganz. Die ungeordneten assoziativen Container besitzen einen mächtigeres Infterface als ihr geordneten Pendants. So erlauben es ungeordnete assoziative Container darüber hinaus noch, sowohl die Hashfunktion als auch die Verteilung der Hashwert in den Buckets fein abzustimmen. Dazu mehr im nächsten Artikel.

 

 

 

 

 

 

 

title page smalltitle page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Hole dir dein E-Book. Unterstütze meinen Blog.

 

 

Kommentare   

0 #1 Cazare 2016-09-19 05:43
For the reason that the admin of this site is working,
no doubt very soon it will be well-known, due to its quality contents.
Zitieren
0 #2 towi 2017-05-16 12:24
Der Artikel erweckt den Anschein unordered_map sei besser als map.

Es ist gefählich das zu vermitteln.

Mit verklumpten Daten wird die Performance quadratisch.

Besonders schlimm wird es, wenn == und hash nicht wie bei int sind, sondern mehrere Werte, die == sind, auf denselben hash abgebildet werden.

Probieren Sie mal aus alle geraden int's auf den einen Hashwert und ungeraden auf einen anderen Hashwert abzubilden und vergleichen Sie die Performance noch einmal.
Zitieren
0 #3 damu 2017-05-16 12:56
Interessant wäre natürlich noch GCC auf derselben Maschine und auf Windows (MinGW) gewesen sowie die verwendeten Programmversionen...
Hab das mal eben getestet:
Visual Studio 2017 mit Ox:
std::map: 0.88305 seconds
std::unordered_map: 0.0740043 seconds
Mit Default (O2):
std::map: 0.86805 seconds
std::unordered_map: 0.0760044 seconds
MinGW/GCC 6.3.0 x86_64 mit O3:
std::map: 0.855049 seconds
std::unordered_map: 0.0760044 seconds
Mit default (O2):
std::map: 0.842048 seconds
std::unordered_map: 0.0770044 seconds
Die Zeiten schwanken grade so um +- 0.03 da Firefox genug CPU zieht um so viel Schwanken zu erzeugen. Visual Studio und GCC sind also im Rahmen der Schwankungen hier identisch, sowohl mit normalen Optimierungen als auch stärksten.
Beide Anwendungen wurden als 64Bit gebaut.

Unter Visual Studio kriege ich die Warnung, dass in Zeile 20 und 21 ein __int64 (der long long) in einen const int (der index) umgewandelt wird. Wenn ich in Zeile 18 statt long long nur int verwende, ist die Warnung weg. An den Zeiten ändert sich dadurch nichts.
Zitieren
0 #4 Rainer Grimm 2017-05-17 05:43
zitiere towi:
Der Artikel erweckt den Anschein unordered_map sei besser als map.

Probieren Sie mal aus alle geraden int's auf den einen Hashwert und ungeraden auf einen anderen Hashwert abzubilden und vergleichen Sie die Performance noch einmal.


Ich habe in keiner Weise vermittelt (wollen), dass ein unordered_map besser als ein map ist. Falls eine schlechte Hashfunktion zum Einsatz kommt, ist das nicht das Problem von std::unordered_map, sondern der Hashfunktion. Wer auf die Idee kommt, eine eigene Hashfunktion zu implementieren, sollte natürlich erst Mal schauen, ob diese Funktion die Schlüssel einigermaßen anständig verteilt. Sonst wird aus O(1) O(n), denn die Suche im Bucket ist linear. Dazu habe ich schon ein paar Artikel geschrieben. Dies sind unter dem Tag Hashtabellen verlinkt.

Ich denke, ich werde in Zukunft einen Artikel schreiben, in dem ich auf die Güte der Hashfunktion eingehe.
Zitieren

Kommentar schreiben


Abonniere den Newsletter (+ pdf Päckchen)

Beiträge-Archiv

Sourcecode

Neuste Kommentare