Lief ein einfacher Leistungstest auf Hash, es scheint, dass C ++ Version langsamer als die Perl-Version und die Golang-Version ist.
Auf meinem PC mit Core (TM) i7-2670QM CPU @ 2.20GHz, Ubuntu 14.04.3LTS,
Irgendwelche Ideen?
Perl-Version
%Vor%C ++ Version
%Vor%Golang-Version
%Vor%Update 1
Um die C ++ - Version zu verbessern, wurde x = mymap["China"]; in mymap["China"]; geändert, aber die Leistung ist sehr gering.
Update 2
Ich habe das ursprüngliche Ergebnis beim Kompilieren ohne Optimierung erhalten: g++ -std=c++11 unorderedMap.cc . Mit "-O2" -Optimierung kostet es nur etwa die Hälfte der Zeit (150ms)
Update 3
Um den möglichen char* to string -Konstruktoraufruf zu entfernen, habe ich eine String-Konstante erstellt. Die Zeit beträgt etwa 220ms (keine Optimierung beim Kompilieren). Dank des Vorschlags von @ neil-kirk, mit Optimierung (-O2-Flag) beträgt die Zeit ca. 80ms.
Update 4
Danke an @ steffen-ullrich, der darauf hingewiesen hat, dass es einen Syntaxfehler für die Perl-Version gibt. Ich habe es geändert. Die Performance-Nummer beträgt ca. 150ms.
Aktualisieren Sie 5
Es scheint, dass die Anzahl der ausgeführten Anweisungen zählt. Verwenden Sie den Befehl valgrind --tool=cachegrind <cmd>
Für die Go-Version
%Vor%Für C ++ optimierte Version (kein Optimierungs-Flag)
%Vor%Für C ++ optimierte Version
%Vor%Aus Ihrem Perl-Code (vor Ihren Versuchen, es zu beheben):
%Vor%
Dies ist keine Karte, sondern ein Array. Die Syntax für Hash-Maps lautet:
%Vor% Sie erstellen also effektiv ein Array und keine Hash-Map und greifen ständig auf das Element 0 zu.
Bitte benutze use strict; und use warnings; die ganze Zeit mit Perl und schon eine einfache Syntaxprüfung mit Warnungen hätte dir das Problem gezeigt:
Abgesehen davon macht der Hauptteil des Benchmarks effektiv nichts Sinnvolles (weise eine Variable zu und benutze sie nie) und einige Compiler können sie erkennen und einfach optimieren.
Wenn Sie den von Ihrem Perl-Programm erzeugten Code überprüfen würden, würden Sie sehen:
%Vor%Das heißt, das Problem wird zur Kompilierzeit erkannt und durch einen Zugriff auf den Array-Index 0 ersetzt.
Also wann immer Sie Benchmarks benötigen:
Und die Verwendung eines einfachen Timers ist kein realistischer Maßstab. Es gibt andere Prozesse auf dem System, es gibt den Scheduler, es gibt Cache-Trashing ... und bei der heutigen CPU hängt es stark von der Belastung des Systems ab, weil vielleicht die CPU einen Benchmark in einem niedrigeren Leistungsmodus als die anderen Benchmarks ausführt , dh mit einem anderen CPU-Takt. Zum Beispiel variieren mehrere Läufe der gleichen "Benchmark" in der gemessenen Zeit zwischen 100ms und 150ms auf meinem System.
Benchmarks sind Lügen und Mikro-Benchmarks wie Ihres doppelt so.
Ich habe Ihr Beispiel ein wenig modifiziert, um einige Details über die Struktur der Hash-Tabelle zu erhalten:
%Vor%Wird dies auf meinem System ausgeführt, bekomme ich eine Laufzeit von ~ 68ms mit folgender Ausgabe:
%Vor%Es stellt sich heraus, dass die Hash-Tabelle nicht gut optimiert ist und einige Kollisionen enthält. Ein weiteres Drucken der Elemente im Bucket zeigt, dass sich Spanien und China in Bucket 9 befinden. Der Bucket ist wahrscheinlich eine verknüpfte Liste mit Knoten, die im Speicher verteilt sind, und erklärt den Leistungsabfall.
Wenn Sie eine andere Größe der Hash-Tabelle wählen, so dass keine Kollisionen auftreten, können Sie eine Beschleunigung erzielen. Ich habe es mit mymap.rehash(1001) getestet und habe eine Beschleunigung von 20-30% auf etwas zwischen 44-52ms bekommen.
Nun wäre ein weiterer Punkt die Berechnung der Hash-Werte für "China". Die Funktion wird in jeder Iteration ausgeführt. Wir können dies verschwinden lassen, wenn wir zu konstanten einfachen C-Strings wechseln:
%Vor% Auf meinem Rechner reduziert dies die Laufzeit um 50% auf ~ 20ms. Der Unterschied besteht darin, dass der Hash-Wert nicht mehr aus dem String-Inhalt berechnet wird, sondern nur die Adresse in einen Hash-Wert umgewandelt wird, der viel schneller ist, da er den Adresswert einfach als size_t zurückgibt. Wir müssen auch nicht erneut hashen, da es keine Kollisionen für den Bucket mit cn gibt.
Dies zeigt nur, dass Go Hash Map Implementierung für diesen speziellen Anwendungsfall sehr gut optimiert ist.
mymap["China"] ruft mapaccess1_faststr auf, das speziell für Strings optimiert wurde Schlüssel. Insbesondere für kleine Ein-Bucket-Maps wird der Hash-Code nicht einmal für kurze Strings (weniger als 32 Bytes) berechnet.
Das ist eine Vermutung:
unordered_map :: operator [] benötigt ein String-Argument. Sie stellen ein char * zur Verfügung. Ohne Optimierungen aktiviert die C ++ - Version den std :: string (char *) -Konstruktor millionenfach, um "China" in eine std :: string zu verwandeln. Die Sprachspezifikation von Go macht wahrscheinlich "String-Literale" vom gleichen Typ wie string, so dass keine Konstruktoren aufgerufen werden müssen.
Wenn Optimierungen aktiviert sind, wird der String-Konstruktor aus der Schleife geholt und Sie sehen nicht das gleiche Problem. Oder es wird höchstwahrscheinlich kein Code erzeugt, außer den beiden Systemaufrufen, um die Uhrzeit zu erhalten, und dem Systemaufruf, um die Differenz auszudrucken, denn letztendlich hat alles keinen Effekt.
Um das zu bestätigen, müssen Sie sich tatsächlich ansehen, welche Assembly generiert wird. Das wird eine Compileroption sein. Siehe diese Frage für die Flaggen erforderlich für GCC.