boost :: flat_map und seine Leistung im Vergleich zu map und unordered_map

In der Programmierung ist allgemein bekannt, dass die Speicherlokalität die Leistung aufgrund von Cache-Treffern erheblich verbessert. Ich habe kürzlich herausgefunden, boost::flat_mapwelches eine vektorbasierte Implementierung einer Karte ist. Es scheint nicht annähernd so beliebt zu sein wie das typische map/ unordered_mapso konnte ich keine Leistungsvergleiche finden. Wie vergleicht es sich und was sind die besten Anwendungsfälle dafür?

Vielen Dank!

Ich habe in letzter Zeit in meinem Unternehmen einen Benchmark für verschiedene Datenstrukturen durchgeführt, daher muss ich ein Wort verlieren. Es ist sehr kompliziert, etwas richtig zu bewerten.

Benchmarking

Im Internet finden wir selten (wenn überhaupt) einen ausgereiften Benchmark. Bis heute habe ich nur Benchmarks gefunden, die auf journalistische Weise durchgeführt wurden (ziemlich schnell und Dutzende von Variablen unter den Teppich gekehrt).

1) Sie müssen über die Cache-Erwärmung nachdenken

Die meisten Leute, die Benchmarks ausführen, haben Angst vor Timer-Diskrepanzen, deshalb führen sie ihre Sachen tausende Male aus und nehmen sich die ganze Zeit Zeit. Sie achten nur darauf, dass sie für jede Operation die gleichen tausend Male nehmen und halten dies dann für vergleichbar.

Die Wahrheit ist, dass es in der realen Welt wenig Sinn macht, weil Ihr Cache nicht warm ist und Ihre Operation wahrscheinlich nur einmal aufgerufen wird. Daher müssen Sie ein Benchmarking mit RDTSC durchführen und Zeitangaben nur einmal durchführen. Intel hat ein Dokument erstellt, in dem beschrieben wird, wie RDTSC verwendet wird (mithilfe einer cpuid-Anweisung wird die Pipeline geleert und zu Beginn des Programms mindestens dreimal aufgerufen, um sie zu stabilisieren).

2) RDTSC-Genauigkeitsmaß

Ich empfehle auch Folgendes:

u64 g_correctionFactor;  // number of clocks to offset after each measurement to remove the overhead of the measurer itself.
u64 g_accuracy;

static u64 const errormeasure = ~((u64)0);

#ifdef _MSC_VER
#pragma intrinsic(__rdtsc)
inline u64 GetRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // flush OOO instruction pipeline
    return __rdtsc();
}

inline void WarmupRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // warmup cpuid.
    __cpuid(a, 0x80000000);
    __cpuid(a, 0x80000000);

    // measure the measurer overhead with the measurer (crazy he..)
    u64 minDiff = LLONG_MAX;
    u64 maxDiff = 0;   // this is going to help calculate our PRECISION ERROR MARGIN
    for (int i = 0; i < 80; ++i)
    {
        u64 tick1 = GetRDTSC();
        u64 tick2 = GetRDTSC();
        minDiff = std::min(minDiff, tick2 - tick1);   // make many takes, take the smallest that ever come.
        maxDiff = std::max(maxDiff, tick2 - tick1);
    }
    g_correctionFactor = minDiff;

    printf("Correction factor %llu clocks\n", g_correctionFactor);

    g_accuracy = maxDiff - minDiff;
    printf("Measurement Accuracy (in clocks) : %llu\n", g_accuracy);
}
#endif

Dies ist ein Diskrepanzmesser, und es wird das Minimum aller gemessenen Werte benötigt, um zu vermeiden, dass von Zeit zu Zeit ein Wert von -10 ** 18 (64-Bit-Negativwerte) erhalten wird.

Beachten Sie die Verwendung von Intrinsics und nicht von Inline-Assemblys. Die erste Inline-Assemblierung wird heutzutage nur noch selten von Compilern unterstützt, aber viel schlimmer ist, dass der Compiler eine vollständige Ordnungsbarriere für die Inline-Assemblierung schafft, da er das Innere nicht statisch analysieren kann Einmal. Daher ist hier ein Intrinsic geeignet, da es die freie Neuordnung von Anweisungen durch den Compiler nicht beeinträchtigt.

3) Parameter

Das letzte Problem ist, dass die Leute normalerweise auf zu wenige Variationen des Szenarios testen. Die Leistung eines Containers wird beeinflusst durch:

1. Allokator
2. Größe des enthaltenen Typs
3. Kosten für die Implementierung des Kopiervorgangs, des Zuweisungsvorgangs, des Verschiebevorgangs, des Konstruktionsvorgangs des enthaltenen Typs.
4. Anzahl der Elemente im Container (Größe des Problems)
5. Typ hat triviale 3.-Operationen
6. Typ ist POD

Punkt 1 ist wichtig, da Container von Zeit zu Zeit zugewiesen werden, und es ist sehr wichtig, ob sie mithilfe der CRT "neu" oder einer benutzerdefinierten Operation wie Poolzuweisung oder Freelist oder anderen ... zuweisen.

( Für Leute, die sich für Punkt 1 interessieren, schließen Sie sich dem Mystery-Thread auf gamedev über die Auswirkungen auf die Leistung des Systemzuordners an. )

Punkt 2 ist, dass einige Container (z. B. A) Zeit verlieren, um Dinge zu kopieren, und je größer der Typ, desto größer der Overhead. Das Problem ist, dass beim Vergleich mit einem anderen Container B A für kleine Typen B gewinnen und für größere Typen verlieren kann.

Punkt 3 ist der gleiche wie Punkt 2, außer dass er die Kosten mit einem Gewichtungsfaktor multipliziert.

Punkt 4 ist eine Frage von Big O gemischt mit Cache-Problemen. Einige Container mit schlechter Komplexität können Container mit geringer Komplexität für eine kleine Anzahl von Typen weit übertreffen (z. B. mapvs. vector, da ihre Cache-Lokalität gut ist, aber mapden Speicher fragmentiert). Und dann verlieren sie an einem Kreuzungspunkt, weil die enthaltene Gesamtgröße beginnt, in den Hauptspeicher zu "lecken" und Cache-Fehler zu verursachen, und die Tatsache, dass die asymptotische Komplexität spürbar wird.

In Punkt 5 geht es darum, dass Compiler in der Lage sind, Dinge zu entfernen, die zur Kompilierungszeit leer oder trivial sind. Dies kann einige Vorgänge erheblich optimieren, da die Container mit Vorlagen versehen sind und daher jeder Typ sein eigenes Leistungsprofil hat.

Punkt 6 Wie Punkt 5 können PODs von der Tatsache profitieren, dass die Kopierkonstruktion nur ein Memcpy ist, und einige Container können für diese Fälle eine spezifische Implementierung haben, indem sie partielle Vorlagenspezialisierungen verwenden, oder SFINAE, um Algorithmen gemäß den Merkmalen von T auszuwählen.

Über die flache Karte

Anscheinend ist die flache Karte ein sortierter Vektor-Wrapper wie Loki AssocVector, aber mit einigen zusätzlichen Modernisierungen in C ++ 11, die die Bewegungssemantik nutzen, um das Einfügen und Löschen einzelner Elemente zu beschleunigen.

Dies ist immer noch ein bestellter Container. Die meisten Leute brauchen normalerweise nicht den bestellenden Teil, daher die Existenz von unordered...

Haben Sie darüber nachgedacht, dass Sie vielleicht eine brauchen flat_unorderedmap? Das wäre so etwas google::sparse_mapoder so etwas - eine offene Adress-Hash-Map.

Das Problem von Open-Address-Hash-Maps besteht darin, dass sie zum Zeitpunkt des rehashKopierens alles in das neue erweiterte flache Land kopieren müssen, während eine ungeordnete Standardkarte nur den Hash-Index neu erstellen muss, während die zugewiesenen Daten dort bleiben, wo sie sind. Der Nachteil ist natürlich, dass die Erinnerung höllisch fragmentiert ist.

Das Kriterium einer erneuten Aufbereitung in einer Hash-Map für offene Adressen ist, wenn die Kapazität die Größe des Bucket-Vektors multipliziert mit dem Lastfaktor überschreitet.

Ein typischer Lastfaktor ist 0.8; Daher müssen Sie sich darum kümmern, wenn Sie Ihre Hash-Karte vor dem Füllen vorab in der Größe intended_filling * (1/0.8) + epsilonanpassen können, immer in der Vorgröße : Dies gibt Ihnen die Garantie, dass Sie während des Füllens niemals alles falsch aufwärmen und neu kopieren müssen.

Der Vorteil von geschlossenen Adresskarten ( std::unordered..) ist, dass Sie sich nicht um diese Parameter kümmern müssen.

Aber das boost::flat_mapist ein geordneter Vektor; Daher hat es immer eine log (N) asymptotische Komplexität, die weniger gut ist als die Hash-Map für offene Adressen (amortisierte konstante Zeit). Das sollten Sie auch berücksichtigen.

Benchmark-Ergebnisse

Dies ist ein Test mit verschiedenen Karten (mit intSchlüssel und __int64/ somestructoder Wert) und std::vector.

Informationen zu getesteten Typen:

typeid=__int64 .  sizeof=8 . ispod=yes
typeid=struct MediumTypePod .  sizeof=184 . ispod=yes

Einfügen

BEARBEITEN:

Meine vorherigen Ergebnisse enthielten einen Fehler: Sie testeten tatsächlich die geordnete Einfügung, die ein sehr schnelles Verhalten für die flachen Karten zeigte.
Ich habe diese Ergebnisse später auf dieser Seite hinterlassen, weil sie interessant sind.
Dies ist der richtige Test:

Ich habe die Implementierung überprüft, es gibt keine verzögerte Sortierung, die in den flachen Karten hier implementiert ist. Jede Insertion wird im laufenden Betrieb sortiert, daher weist dieser Benchmark die asymptotischen Tendenzen auf:

Karte: O (N * log (N))
Hashmaps: O (N)
Vektor und Flatmaps: O (N * N)

Achtung : Im folgenden wird die 2 - Tests für std::mapund beide flat_maps sind Buggy und tatsächlich Test bestellt Insertion (vs Zufallsinsertion für andere Behälter Ja , es ist verwirrend sorry.):

Wir können sehen, dass das geordnete Einsetzen zu einem Zurückschieben führt und extrem schnell ist. Aufgrund der nicht aufgezeichneten Ergebnisse meines Benchmarks kann ich jedoch auch sagen, dass dies nicht in der Nähe der absoluten Optimalität für eine Rückeinfügung liegt. Bei 10k-Elementen wird eine perfekte Optimalität beim Zurücksetzen auf einem vorreservierten Vektor erhalten. Was uns 3 Millionen Zyklen gibt; Wir beobachten hier 4,8 M für die geordnete Einfügung in die flat_map(daher 160% des Optimums ).

Analyse: Denken Sie daran, dass dies eine zufällige Einfügung für den Vektor ist. Die massiven 1 Milliarde Zyklen ergeben sich aus der Notwendigkeit, die Hälfte (im Durchschnitt) der Daten bei jeder Einfügung nach oben (ein Element nach dem anderen) zu verschieben.

Zufällige Suche von 3 Elementen (Uhren auf 1 renormiert)

in der Größe = 100

in der Größe = 10000

Wiederholung

über Größe 100 (nur MediumPod-Typ)

über Größe 10000 (nur MediumPod-Typ)

Letztes Salzkorn

Am Ende wollte ich auf "Benchmarking §3 Pt1" (den Systemzuweiser) zurückkommen. In einem kürzlich durchgeführten Experiment zur Leistung einer von mir entwickelten Hash-Map für offene Adressen habe ich in einigen std::unordered_mapAnwendungsfällen ( hier beschrieben ) eine Leistungslücke von mehr als 3000% zwischen Windows 7 und Windows 8 gemessen .
Aus diesem Grund möchte ich den Leser vor den oben genannten Ergebnissen warnen (sie wurden unter Win7 erstellt): Ihr Kilometerstand kann variieren.

freundliche Grüße

Aus den Dokumenten geht hervor, dass dies analog zu Loki::AssocVectordem ist, von dem ich ein ziemlich starker Benutzer bin. Da es auf einem Vektor basiert, hat es die Eigenschaften eines Vektors, das heißt:

• Iteratoren werden ungültig, wenn sie sizedarüber hinaus wachsen capacity.
• Wenn es über die capacityNotwendigkeit hinausgeht , Objekte neu zuzuweisen und zu verschieben, dh das Einfügen ist keine konstante Zeit garantiert, außer für den Sonderfall des Einfügens zu dem endZeitpunktcapacity > size
• Die std::mapSuche ist schneller als aufgrund der Cache-Lokalität, einer binären Suche, die dieselben Leistungsmerkmale wie std::mapansonsten aufweist
• Verbraucht weniger Speicher, da es sich nicht um einen verknüpften Binärbaum handelt
• Es schrumpft nie, wenn Sie es nicht gewaltsam anweisen (da dies eine Neuzuweisung auslöst).

Die beste Verwendung ist, wenn Sie die Anzahl der Elemente im Voraus kennen (damit Sie dies im Voraus tun können reserve) oder wenn das Einfügen / Entfernen selten ist, die Suche jedoch häufig ist. Die Iterator-Ungültigmachung macht es in einigen Anwendungsfällen etwas umständlich, sodass sie hinsichtlich der Programmkorrektheit nicht austauschbar sind.