Superhochleistungs-C / C ++ - Hash-Map (Tabelle, Wörterbuch) [geschlossen]

83

Ich muss primitive Schlüssel (int, möglicherweise long) auf Strukturwerte in einer Hochleistungs-Hash-Map-Datenstruktur abbilden.

Mein Programm wird einige hundert dieser Karten haben, und jede Karte wird im Allgemeinen höchstens einige tausend Einträge haben. Die Karten werden jedoch ständig "aktualisiert" oder "aufgewühlt". vorstellen Millionen Verarbeitung addund deleteNachrichten einer Sekunde.

Welche Bibliotheken in C oder C ++ haben eine Datenstruktur, die zu diesem Anwendungsfall passt? Oder wie würden Sie empfehlen, Ihre eigenen zu bauen? Vielen Dank!

Haywood Jablomey
quelle
1
Müssen Sie die Suche nach Schlüsseln in Ihre Daten verarbeiten?
Guillaume Lebourgeois
3
Werden Aktualisierungen oder Abfragen häufiger durchgeführt? (Hinzufügen / Löschen oder Lesen / Aktualisieren, ohne den Schlüssel zu ändern)
Falstro
stackoverflow.com/questions/266206/… . Dies ist vielleicht ein guter Anfang.
DumbCoder
@Guillaume Lebourgeois:Alle Vorgänge werden pro Schlüssel durchgeführt. Irgendwann werde ich große Mengen von Schlüsseln oder Werten verarbeiten, aber ich vermute, dass dies besser für eine Baumstruktur geeignet wäre.
Haywood Jablomey
2
@roe:Die Operationen zum Hinzufügen / Löschen sind viel (100x) häufiger als die Operationen zum Abrufen.
Haywood Jablomey

Antworten:

30

Ich würde Ihnen empfehlen, Google SparseHash (oder die C11-Version Google SparseHash-c11 ) auszuprobieren und zu prüfen, ob es Ihren Anforderungen entspricht. Sie haben eine speichereffiziente Implementierung sowie eine auf Geschwindigkeit optimierte. Ich habe vor langer Zeit einen Benchmark durchgeführt, es war die beste verfügbare Hashtable-Implementierung in Bezug auf die Geschwindigkeit (jedoch mit Nachteilen).

Scharron
quelle
16
Können Sie die Nachteile erläutern?
Haywood Jablomey
IIRC, es war ein Speicherproblem, beim Entfernen eines Elements wurde das Element zerstört, aber sein Speicher war noch aktiv (wird vermutlich als Cache verwendet).
Scharron
4
@ Haywood Jablomey: Der Hauptnachteil besteht darin, dass Sie einen oder zwei Werte (falls Sie jemals Elemente löschen) aufteilen und diese niemals verwenden müssen. In einigen Fällen ist dies einfach, z. B. negative Ints oder ähnliches, in anderen Fällen jedoch nicht ganz.
Doublep
3
Würden Sie heute zu dieser Empfehlung stehen?
Einpoklum
11

Welche Bibliotheken in C oder C ++ haben eine Datenstruktur, die zu diesem Anwendungsfall passt? Oder wie würden Sie empfehlen, Ihre eigenen zu bauen? Vielen Dank!

Schauen Sie sich die LGPL'd Judy Arrays an . Ich habe mich nie benutzt, wurde mir aber nur selten beworben.

Sie können auch versuchen, STL-Container (std :: hash_map usw.) zu vergleichen. Abhängig von der Plattform / Implementierung und der Optimierung des Quellcodes (so viel wie möglich vorab zuzuweisen ist eine dynamische Speicherverwaltung teuer) können sie leistungsfähig genug sein.

Wenn die Leistung der endgültigen Lösung die Kosten der Lösung übertrifft, können Sie versuchen, das System mit ausreichend RAM zu bestellen, um alles in einfache Arrays zu packen. Die Leistung des Zugriffs nach Index ist unschlagbar.

Die Operationen zum Hinzufügen / Löschen sind viel (100x) häufiger als die Operationen zum Abrufen.

Dies deutet darauf hin, dass Sie sich zunächst auf die Verbesserung von Algorithmen konzentrieren möchten. Wenn Daten nur geschrieben, nicht gelesen werden, warum dann überhaupt schreiben?

Dummy00001
quelle
11

Verwenden Sie einfach boost::unordered_map(oder tr1usw.) standardmäßig. Profilieren Sie dann Ihren Code und prüfen Sie, ob dieser Code der Engpass ist. Nur dann würde ich vorschlagen, Ihre Anforderungen genau zu analysieren, um einen schnelleren Ersatz zu finden.

Mark B.
quelle
15
Es ist. VS2013 std::unordered_mapnimmt 90 +% meiner gesamten Ausführungszeit in Anspruch, obwohl ich die Karten nur für einen relativ kleinen Teil der Verarbeitung verwende.
Cameron
6

Wenn Sie ein Multithread-Programm haben, finden Sie einige nützliche Hash-Tabellen in der Intel Thread Building Blocks-Bibliothek . Zum Beispiel hat tbb :: concurrent_unordered_map dieselbe API wie std :: unordered_map, aber die Hauptfunktionen sind threadsicher.

Auch einen Blick auf Facebook hat Torheit Bibliothek , hat es eine hohe Leistung gleichzeitig Hash - Tabelle und Skip-Liste .

Pavel Davydov
quelle
3

aus Android-Quellen (also Apache 2 lizenziert)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

Schauen Sie sich hashmap.c an und wählen Sie include / cutils / hashmap.h aus. Wenn Sie keine Thread-Sicherheit benötigen, können Sie Mutex-Code entfernen. Eine Beispielimplementierung befindet sich in libcutils / str_parms.c

Sherpya
quelle
2

Überprüfen Sie zunächst, ob vorhandene Lösungen wie libmemcache Ihren Anforderungen entsprechen.

Wenn nicht ...

Hash-Maps scheinen die eindeutige Antwort auf Ihre Anforderung zu sein. Es bietet o (1) Suche basierend auf den Schlüsseln. Die meisten STL-Bibliotheken bieten heutzutage eine Art Hash an. Verwenden Sie also die von Ihrer Plattform bereitgestellte.

Sobald dieser Teil erledigt ist, müssen Sie die Lösung testen, um festzustellen, ob der Standard-Hashing-Algorithmus hinsichtlich Ihrer Leistung ausreichend leistungsfähig ist.

Wenn dies nicht der Fall ist, sollten Sie einige gute schnelle Hashing-Algorithmen im Internet untersuchen

  1. gute alte Primzahl multiplizieren algo
  2. http://www.azillionmonkeys.com/qed/hash.html
  3. http://burtleburtle.net/bob/
  4. http://code.google.com/p/google-sparsehash/

Wenn dies nicht gut genug ist, können Sie selbst ein Hashing-Modul rollen, das das Problem behebt, das Sie bei den von Ihnen getesteten STL-Containern und einem der oben genannten Hashing-Algorithmen gesehen haben. Stellen Sie sicher, dass Sie die Ergebnisse irgendwo veröffentlichen.

Oh, und es ist interessant, dass Sie mehrere Karten haben ... Vielleicht können Sie es vereinfachen, indem Sie Ihren Schlüssel als 64-Bit-Zahl mit den hohen Bits verwenden, um zu unterscheiden, zu welcher Karte er gehört, und alle Schlüsselwertpaare zu einem riesigen Hash hinzufügen. Ich habe Hashes mit ungefähr hunderttausend Symbolen gesehen, die auf dem grundlegenden Haschalgorithmus für Primzahlen ziemlich gut funktionieren.

Sie können überprüfen, wie diese Lösung im Vergleich zu Hunderten von Karten funktioniert. Ich denke, das könnte aus Sicht der Speicherprofilerstellung besser sein. Bitte veröffentlichen Sie die Ergebnisse irgendwo, wenn Sie diese Übung durchführen können

Ich glaube, dass mehr als der Hashing-Algorithmus das ständige Hinzufügen / Löschen von Speicher (kann dies vermieden werden?) Und das CPU-Cache-Nutzungsprofil sein könnten, das für die Leistung Ihrer Anwendung entscheidender sein könnte

Viel Glück

Computerleben
quelle
2

Probieren Sie Hash-Tabellen aus verschiedenen Containervorlagen aus . Es closed_hash_mapist ungefähr so ​​schnell wie Google dense_hash_map, aber einfacher zu verwenden (keine Einschränkung der enthaltenen Werte) und bietet auch einige andere Vorteile.

doublep
quelle
2

Ich würde Uthash vorschlagen . Fügen Sie der Struktur einfach #include "uthash.h"ein hinzu UT_hash_handle, fügen Sie dann ein hinzu und wählen Sie ein oder mehrere Felder in Ihrer Struktur aus, die als Schlüssel dienen sollen. Ein Wort zur Leistung hier .

Saharsh-Jain
quelle
1

http://incise.org/hash-table-benchmarks.html gcc hat eine sehr sehr gute Implementierung. Beachten Sie jedoch, dass eine sehr schlechte Standardentscheidung eingehalten werden muss:

Wenn eine erneute Aufbereitung stattfindet, werden alle Iteratoren ungültig, aber Verweise und Zeiger auf einzelne Elemente bleiben gültig. Wenn keine tatsächliche Aufbereitung stattfindet, werden keine Änderungen vorgenommen.

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

Dies bedeutet im Grunde, dass der Standard besagt, dass die Implementierung auf verknüpften Listen basieren muss. Es verhindert eine offene Adressierung mit besserer Leistung.

Ich denke, Google Sparse verwendet offene Adressierung, obwohl in diesen Benchmarks nur die dichte Version die Konkurrenz übertrifft. Die Version mit geringer Dichte übertrifft jedoch alle Konkurrenz bei der Speichernutzung. (es hat auch kein Plateau, reine Gerade für die Anzahl der Elemente)

v.oddou
quelle
1
Siehe auch dies , in dem erläutert wird, wie die Bucket-Schnittstelle auch eine Verkettung erfordert. Der Punkt über Referenzen ist sehr gut. Es ist verlockend zu argumentieren und zu sagen, dass dies eine nützliche Garantie ist, aber in vielen Fällen möchten wir nur, dass Referenzen das erneute Nachschlagen von Elementen vermeiden. Der übliche Grund ist, dass die Suche zu langsam ist ... was nicht der Fall wäre, wenn dies nicht der Fall wäre Referenzen müssen gültig bleiben und könnten daher offene Adressierung verwenden! Es scheint also ein bisschen Hühnchen und Ei zu sein. Dies zitiert den Vorschlag von 2003, in dem die Wahl explizit erörtert wird.
underscore_d