Hashtabellen - Ein einfacher Performanzvergleich

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 Containern 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 Ergebnisse.

Microsoft Visual C++ Compiler

GCC Compiler

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 verschiedenen Rechnern 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.

GCC Compiler

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

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.

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.

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.