Open Source im professionellen Einsatz
Linux-Magazin 12/2013

Modernes C++ in der Praxis – Folge 13

Geschwindigkeit zählt

"Performance matters": Was sich wie ein Glaubensbekenntnis anhört, bleibt ein wichtiges Designkriterium in C++. Mit den neuen Hashtabellen kann der Programmierer richtig Tempo machen.

1828

Zu den am meisten vermissten Features im alten C++-Standard gehören Hashtabellen. Diese Datenstrukturen sind auch unter den Namen Dictionaries oder assoziative Arrays bekannt. Hashtabellen sind Container, die Schlüssel-Wert-Paare enthalten. Der Programmierer verwendet den Schlüssel, um dessen assoziierten Wert zu erhalten.

Der Zugriff ist sowohl komfortabel als auch performant: Komfortabel, da natürliche Zahlen, Fließkommazahlen, Zeiger und Strings als Schlüssel zur Auswahl stehen. Performant, da die Zugriffszeit im Idealfall konstant ist – sie ist unabhängig davon, wie groß die Hashtabelle ist. Der Kasten "Allerlei Arrays" macht es einfacher, Hashtabellen als Teil von C++ zu begreifen.

Allerlei Arrays

Der Datentyp "assoziatives Array" wird leichter verständlich, wenn man ihn sich als ein verallgemeinertes Array vorstellt. Sind bei einem herkömmlichen Array nur natürliche Zahlen als Schlüssel erlaubt, unterstützt das assoziative Array neben den Built-in-Datentypen auch eigene Datentypen als Schlüssel, sofern für diese eine Hashfunktion definiert ist. Der einzige Unterschied zwischen assoziativen Arrays und Arrays besteht dann nur noch darin, dass man die Schlüssel bei normalen Arrays als Indizes bezeichnet.

Hashtabellen gehören zum täglich Brot professioneller Entwickler. Das klassische C++ bietet mit »std::map« , »std::multimap« , »std::set« und »std::multiset« bereits vier assoziative Arrays an, die sich wie Hashtabellen verhalten. Es gibt aber einen feinen Unterschied: Die Schlüssel der klassischen assoziativen Arrays sind geordnet. Damit hängt die Zugriffszeit auf die Werte logarithmisch von der Anzahl der Schlüssel ab. Konsequenterweise erhalten die neuen Hashtabellen in C++11 den Namenszusatz "unordered": »std::unordered_map« , »std::unordered_multimap« , »std::unordered_set« und »std::unordered_multiset« .

Um ein wenig Übersicht zu schaffen, stellt Tabelle 1 die Container aus C++98 jenen in C++11 gegenüber, die ein ähnliches Interface anbieten. Listing 1 zeigt die beiden gebräuchlichsten Container »std::map« und »std::unordered_map« im Einsatz.

Tabelle 1

Assoziative Container in C++98 und C++11

C++98

C++11

std::map

std::unordered_map

std::set

std::unordered_set

std::multimap

std::unordered_multimap

std::multiset

std::unordered_multiset

Listing 1

std::map und std::unordered_map

01 #include <iostream>
02 #include <map>
03 #include <unordered_map>
04
05 int main(){
06
07   std::cout << std::endl;
08
09   std::cout << "C++ map: " << std::endl;
10   std::map<std::string,int> m { {"Dijkstra",1972},{"Scott",1976} };
11   m["Ritchie"] = 1983;
12   std::cout << "    m[Ritchie]: " <<  m["Ritchie"] << "\n    ";
13   for(auto p : m) std::cout << '{' << p.first << ',' << p.second << '}';
14   m.erase("Scott");
15   std::cout << "\n    ";
16   for(auto p : m) std::cout << '{' << p.first << ',' << p.second << '}';
17   m.clear();
18   std::cout << std::endl;
19   std::cout << "    m.size(): " << m.size() << std::endl;
20
21
22   std::cout << std::endl;
23
24   std::cout << "C++11 unordered_map: " << std::endl;
25   std::unordered_map<std::string,int> um { {"Dijkstra",1972},{"Scott",1976} };
26   um["Ritchie"] = 1983;
27   std::cout << "    um[Ritchie]: " <<  um["Ritchie"] << "\n    ";
28   for(auto p : um) std::cout << '{' << p.first << ',' << p.second << '}';
29   um.erase("Scott");
30   std::cout << "\n    ";
31   for(auto p : um) std::cout << '{' << p.first << ',' << p.second << '}';
32   um.clear();
33   std::cout << std::endl;
34   std::cout << "    um.size(): " << um.size() << std::endl;
35
36   std::cout << std::endl;
37
38 }

Das kleine Programm ist relativ unspektakulär. Zuerst füllt Zeile 10 mit einer Initialisierer-Liste die »std::map« mit zwei Paaren. Der Typ des Schlüssels ist ein String, der des Wertes eine natürliche Zahl. Der Index-Operator erlaubt sowohl (in Zeile 11), die Map um ein zusätzliches Paar zu erweitern, als auch in der anschließenden Zeile, den Wert zum Schlüssel »Ritchie« zu finden.

Pärchenweise

Dank der neuen Range-basierten For-Schleife lassen sich alle Schlüssel-Wert-Paare direkt ausgeben. Dazu kommen die Attribute »p.first« und »p.second« zum Einsatz. Ein einzelnes Paar löscht die Methode »m.erase("Scott")« (Zeile 14), die ganze Map lässt sich mit der Methode »m.clear()« (Zeile 17) leeren. Dieser Code wiederholt sich von Zeile 24 an. Die einzige Variation besteht darin, dass nun »std::unordered_map« zur Verwendung kommt. Ein scharfer Blick auf die Ausgabe des Programms in Abbildung 1 zeigt, dass die Schlüssel der »std::unordered_map« nicht sortiert sind.

Abbildung 1: std::map und std::unordered_map: Im zweiten Fall sind die Schlüssel unsortiert.

Warum aber besitzt modernes C++ acht assoziative Container, jeweils zwei mit ähnlichem Interface? Vier bieten die Schlüssel sortiert, die vier mit dem Namenszusatz »unordered« unsortiert an. Daneben lassen sich zwei weitere Unterscheidungsmerkmale anwenden: Ist dem Schlüssel ein Wert zugeordnet? Darf ein Schüssel mehrfach vorkommen? Tabelle 2 beantwortet diese Fragen für alle acht.In [1] sind alle komplexen Details zu den acht assoziativen Containern detailliert dargestellt.

Tabelle 2

Übersicht der acht assoziativen Container

Container

Ist dem Schlüssel ein Wert zugeordnet?

Darf ein Schlüssel mehrfach vorkommen?

std::map, std::unordered_map

ja

nein

std::set, std::unordered_set

nein

nein

std::multimap, std::unordered_multimap

ja

ja

std::multiset, std::unordered_multiset

nein

ja

Das beantwortet allerdings nicht die Frage, warum man das klassische C++ um vier ungeordnete Container erweitert hat. Die Antwort ist zweiteilig: Zum einen brauchen die Schlüssel in den ungeordneten Containern keine Kleiner-als-Relation zu unterstützen, zum anderen: Performance matters.

C++11 überholt C++

Ist ein assoziatives Array sehr groß und brauchen die Schlüssel nicht geordnet zu sein, sollte eine Hashtabelle die erste Wahl des Programmierers sein. Mit ein wenig Aufwand lässt sich das in einem kleinen Experiment belegen. Zu diesem Zweck liest ein Programm – zufällig verteilt – eine Million Schlüssel aus zehn Millionen Schlüssel-Wert-Paaren.

Listing 2 füllt eine »std::map« und eine »std::unordered_map« mit jeweils zehn Millionen Schlüssel-Wert-Paaren (Zeilen 18, 19). Der Einfachheit halber sind die Schlüssel und Werte identisch. Der Vektor »randValues« dient als Container für eine Million gleichmäßig verteilter Zufallszahlen von Null bis zehn Millionen (Zeilen 26 bis 29).

Listing 2

Performancevergleich von std::map und std::unordered_map

01 #include <chrono>
02 #include <iostream>
03 #include <map>
04 #include <random>
05 #include <unordered_map>
06
07 static const long long mapSize= 10000000;
08 static const long long accSize= 1000000;
09
10 int main(){
11
12   std::cout << std::endl;
13
14   std::map<int,int> myMap;
15   std::unordered_map<int,int> myHash;
16
17   for ( long long i=0; i < mapSize; ++i ){
18     myMap[i]=i;
19     myHash[i]= i;
20   }
21
22   std::vector<int> randValues;
23   randValues.reserve(accSize);
24
25   // random values
26   std::random_device seed;
27   std::mt19937 engine(seed());
28   std::uniform_int_distribution<> uniformDist(0,mapSize);
29   for ( long long i=0 ; i< accSize ; ++i) randValues.push_back(uniformDist(engine));
30
31   auto start = std::chrono::system_clock::now();
32   for ( long long i=0; i < accSize; ++i){
33     myMap[randValues[i]];
34   }
35   std::chrono::duration<double> dur= std::chrono::system_clock::now() - start;
36   std::cout << "time for std::map: " << dur.count() << " seconds" << std::endl;
37
38   auto start2 = std::chrono::system_clock::now();
39   for ( long long i=0; i < accSize; ++i){
40     myHash[randValues[i]];
41   }
42   std::chrono::duration<double> dur2= std::chrono::system_clock::now() - start2;
43   std::cout << "time for std::unordered_map: " << dur2.count() << " seconds" << std::endl;
44
45   std::cout << std::endl;
46
47 }

Das Entscheidende an Listing 2 sind die Abschnitte von Zeile 31 bis 36 und von Zeile 38 bis 43. Hier misst das Programm, wie lange das Auslesen einer Million Schlüssel dauert. Im Fall der »std::map« sind es 1,7 Sekunden, bei der »std::unordered_map« 0,3 Sekunden. Das Ergebnis ist in Abbildung 2 zu sehen. Übersetzt man den Sourcecode mit dem GCC-Compiler voll optimiert, ergibt sich ein noch größerer Unterschied (Abbildung 3). Dann stehen 1,2 Sekunden 0,08 Sekunden gegenüber. Der unsortierte Container ist um den Faktor 15 schneller. Was für ein Performance-Boost!

Abbildung 2: Performancevergleich von std::map und std::unordered_map, nicht optimiert.
Abbildung 3: Performancevergleich von std::map und std::unordered_map mit GCC-Optimierungen.

Abbildung 4 zeigt die interne Struktur der geordneten assoziativen Container, Abbildung 5 die der ungeordneten. Beide enthalten die Schlüssel »Grimm« , »Grimm-Jaud« , »Schmidt« und »Huber« . Schön ist zu sehen, dass geordnete Container als binäre Suchbäume implementiert sind, während ihre ungeordneten Verwandten ihre Schlüssel in Buckets speichern. Die Baumstruktur heißt binärer Suchbaum, da jeder Knoten maximal zwei Kinder besitzt und die Knoten eine Ordnung aufweisen.

Abbildung 4: Ein geordneter assoziativer Container ordnet seine Schlüssel in einem binären Suchbaum.
Abbildung 5: Beim ungeordneten assoziativen Container findet die Hashfunktion die Schlüssel in Buckets.

Während ein Programm beim geordneten Container den ganzen Suchbaum bis zum richtigen Blatt durchqueren muss, um den Wert zu einem Schlüssel zu erhalten, ermittelt beim ungeordneten Container die Hashfunktion, in welchem Bucket sich der Schlüssel befindet.

Das erklärt den Performance-Unterschied: Die Tiefe des binären Suchbaums und somit die erforderliche Zugriffszeit hängt logarithmisch von der Anzahl der enthaltenen Elemente ab. Um den richtigen Bucket eines Schlüssels bei der Hashtabelle zu ermitteln, muss der Rechner dagegen lediglich die Hashfunktion anwenden. Die für diese Operation benötigte Zeit bleibt konstant und somit auch die Zugriffszeit.

Natürlich kann es dabei vorkommen, dass ein Bucket ohne Schlüssel bleibt oder mehrere Schlüssel in einem Bucket landen. Im zweiten Fall spricht man von einer Kollision, die die Hashtabelle behandeln muss. Eine Hashfunktion ist dann gut, wenn sie die Schlüssel möglichst kollisionsfrei auf ihre Buckets verteilt. In C++11 kann der Entwickler aber auch viele Eigenschaften der Hashtabelle anpassen.

So lässt sich etwa die Kapazität, also die Anzahl B der Buckets, sowohl ermitteln als auch verändern. Teilt man die Anzahl der Elemente n durch die Anzahl der Buckets B, ergibt sich der Ladefaktor L = n/B der Hashtabelle. Wird dieser Ladefaktor zu groß (typischerweise größer als 1), so erhält die Hashtabelle neue Buckets und die Schlüssel werden neu auf diese verteilt. Dieser Vorgang heißt Rehashing, er lässt sich auch explizit anstoßen.

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 3 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • C++11

    Container sind nicht nur bei der Virtualisierung derzeit in aller Munde, auch dem Programmierer sind Behälter für Objekte nützlich. Die Version 11 von C++ enthält einige Algorithmen, die die Arbeit mit solchen Containern deutlich vereinfachen.

  • C++11

    In C++11 lässt sich manches prägnanter formulieren als in klassischem C++. Dieser Artikel zeigt, wie die neue Range-basierte For-Schleife und die automatische Typableitung dabei helfen.

  • Reichhaltiges Angebot

    C++0x bringt nicht nur Veränderungen in der Kernsprache. Die Standardbibliothek der C++-Neuausgabe hat Multithreading, asynchrone Funktionsaufrufe, reguläre Ausdrücke und vieles mehr im Angebot.

  • C++11

    Die Referenz-Wrapper bilden eine kleine, aber feine neue Bibliothek in C++11. Diese Objekte verhalten sich wie Referenzen, der Artikel erklärt die Details.

  • C++11

    Die neue Zeitbibliothek ist ein elementarer Baustein nicht nur für die Mulithreading-Fähigkeit von C++. Mit ihrer Hilfe legt der Entwickler einen Thread bis zu einem definierten Zeitpunkt schlafen oder fordert auf gut Glück ein Lock für eine Zeitspanne an.

comments powered by Disqus

Ausgabe 10/2017

Digitale Ausgabe: Preis € 6,40
(inkl. 19% MwSt.)

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.