Praktische Größenbeschränkungen für Hashtable und Dictionary in c #

12

Was sind die praktischen Grenzen für die Anzahl der Elemente, die ein C # 4-Wörterbuch oder eine Hashtabelle enthalten kann, und die Gesamtanzahl der Bytes, die diese Strukturen enthalten können? Ich arbeite mit einer großen Anzahl von Objekten und möchte wissen, wann bei diesen Strukturen Probleme auftreten.

Als Kontext verwende ich ein 64-Bit-System mit viel Speicher. Außerdem muss ich Objekte mithilfe einer Form oder eines Schlüssels finden. Angesichts der Leistungsanforderungen müssen sich diese Objekte im Speicher befinden, und viele davon sind langlebig.

Sie können auch andere Ansätze / Muster vorschlagen, obwohl ich die Verwendung von Bibliotheken von Drittanbietern oder Open-Source-Bibliotheken vermeiden muss. Aus Spezifikationsgründen muss ich in der Lage sein, dies mit nativem C # ( oder C ++ \ CLI ) zu erstellen .

JoeGeeky
quelle
1
Es sollte nur ein oder zwei Stunden dauern, um dieses Zeug zu verspotten und die Leistung beim Hinzufügen / Entfernen / Nachschlagen unter verschiedenen Auslastungen zu messen. Ich glaube, VS2010 bietet Ihnen sogar ein Skelett für Leistungstests. Egal, was hier jemand sagt, der Code, den Sie schreiben, trägt Ihren Namen direkt oder in Metadaten.
Job

Antworten:

8

Eine Sache, auf die hingewiesen werden muss, ist, dass das Dictionary nicht das Objekt selbst enthält (was einen großen Speicherbedarf haben kann), sondern nur einen Verweis auf das Objekt. Wenn die Objekte also komplex sind, hat dies keine Auswirkungen auf die Dictionary-Größe.

Ich habe mehrere tausend Elemente in einem Wörterbuch im Speicher gesammelt, und das Problem ist nicht die Größe des Wörterbuchs, sondern die Größe der Objekte selbst im Speicher. In diesen Fällen war das Wörterbuch selbst ein winziger Teil des Speichers.

Bei großen Wörterbüchern ist es wichtig, die Wörterbuchkapazität manuell zu konfigurieren und zu verwalten. Unter normalen Umständen verwaltet .Net dieses Problem (in der aktuellen Implementierung wird die Größe auf eine Primzahl geändert, die mindestens doppelt so groß ist wie das aktuelle Dictionary). Wenn Sie jedoch wissen, dass Sie ein umfangreiches Wörterbuch erstellen oder erweitern möchten, anstatt .Net zu schätzen und die Größe des Wörterbuchs für Sie zu ändern (was relativ kostspielig ist), ist es wahrscheinlich besser, dies selbst zu tun (mit Sicherheit mit der Initiale) Größe und wahrscheinlich später ändern). Dies kann durch die Verwaltung der Wörterbuchkapazität erreicht werden, wenn Sie eine vernünftige heuristische Vorstellung davon haben, wie groß die Kapazität des Wörterbuchs sein sollte. Microsoft empfiehlt dies aufMSDN in ihren Anmerkungen zum Dictionary-Objekt . Es scheint jedoch eine Debatte über den tatsächlichen Wert dieses Ansatzes zu geben, obwohl ich nicht sicher bin, wie streng dieser Test ist und ob es andere Optimierungen gibt, die die .NET-Plattform einführt, wenn die Größe eines Wörterbuchs extrem schnell geändert wird.

Dies ist eine nützliche Frage zum Stapelüberlauf bezüglich Objekt und Speichergröße.

AlexC
quelle
2

Praktische Grenzen können sich auf den Computer beziehen, auf dem Ihre Software ausgeführt wird, sowie auf die Anzahl der Objekte, die Sie tatsächlich in diesen Datenstrukturen enthalten möchten. Wie Oded bereits erwähnte, ist int.MaxValue eine große Zahl, aber entsprechen 2 Milliarden Artikel einer praktischen Grenze? Das Speichern so vieler Elemente im Speicher ist wahrscheinlich nicht sehr praktisch.

Bernard
quelle
0

Da in der Dokumentation nicht angegeben ist, wo die Daten physisch gespeichert sind, und die Grenze nicht angegeben ist, wird empfohlen, ein Experiment mit der voraussichtlich maximal verfügbaren Größe durchzuführen und den Systemspeicher vor und nach der Speicherzuweisung zu notieren.

Keine Chance
quelle
-1

Ich habe kürzlich das Hash-Table-Shootout des Github-Projekts aktualisiert (hier: https://github.com/jimbelton/hash-table-shootout ). Die ungeordnete gcc-Standardkarte hat einen Overhead von ca. 1,8 GByte zum Speichern von 40 Millionen Objekten. Dies scheint mir ziemlich grausam zu sein, aber selbst die sparse_hash_map von Google mit dem besten Arbeitsspeicher benötigt 600 MB, und Sie zahlen eine Leistungsstrafe, wenn Sie sie verwenden. Wenn Sie Geschwindigkeit wünschen, ist der Glib GHashTable von den enthaltenen Algorithmen der schnellste und weist eine gute Speicherleistung auf (etwa 1,3 GB Overhead). Die Benchmark-Ergebnisse werden hier veröffentlicht: https://jimbelton.wordpress.com/2015/07/01/hash-table-shootout-on-github/

Jim Belton
quelle