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

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.

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.

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.

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

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.

Wie geht’s weiter?

Ein heimlicher Star des C++-Standards ist die Range-basierte For-Schleife. Erlaubt sie es doch, einfach über die Elemente eines Containers zu iterieren und sie bei Bedarf zu modifizieren. Kommt dazu mit »auto« ein weiterer Star in der Schleife zum Einsatz, um den Typ der Container-Elemente automatisch zu bestimmen, reduziert sich der Schreibaufwand auf das Notwendigste. Grund genug, um diese Glanzlichter von C++11 im nächsten Artikel dieser Reihe genauer zu betrachten. Ohne die beiden ist fast kein modernes C++-Programm vorstellbar. (mhu)

Der Autor

Rainer Grimm arbeitet als Software-Architekt und Gruppenleiter bei der Metrax GmbH in Rottweil. Insbesondere die Software auf den Defibrillatoren ist ihm eine Herzensangelegenheit. Sein Buch “C++11: Der Leitfaden für Programmierer zum neuen Standard” ist bei Addison-Wesley erschienen.