Informationen zur Implementierung der Map-Datenstruktur in V8

Der Standard ECMAScript 2015 , als ES6 bekannt ist , gibt es viele neue JavaScript-Sammlungen wie Map, Set, WeakMapund WeakSet. Sie scheinen eine großartige Ergänzung zu den Standard-JavaScript-Funktionen zu sein. Sie werden häufig in verschiedenen Bibliotheken, in Anwendungen und im Kern von Node.js verwendet. Heute werden wir über die Sammlung sprechen Map, versuchen, die Besonderheiten ihrer Implementierung in V8 herauszufinden und auf der Grundlage der gewonnenen Erkenntnisse einige praktische Schlussfolgerungen zu ziehen.



Der ES6-Standard gibt keinen klaren Hinweis auf den Ansatz, der zur Implementierung der Datenstrukturunterstützung gewählt werden sollte Map. Es gibt nur einige Hinweise zu möglichen Implementierungsmöglichkeiten. Es enthält auch Informationen über die erwarteten vonMapLeistungsmetriken:



Das Map-Objekt muss mithilfe von Hash-Tabellen oder anderen Mechanismen implementiert werden, die im Durchschnitt einen sublinearen Zugriff auf die Elemente der Sammlung ermöglichen. Die in der Kartenspezifikation verwendeten Datenstrukturen sollen nur die beobachtbare Semantik von Kartenobjekten beschreiben. Sie wurden nicht als reales Modell für die Implementierung dieser Objekte konzipiert.



Wie Sie sehen können, gibt die Spezifikation denjenigen, die JS-Engines erstellen, viel Freiheit. Gleichzeitig gibt es jedoch keine spezifischen Richtlinien hinsichtlich des spezifischen Ansatzes für die Implementierung Map, seiner Leistung und der Eigenschaften des Speicherverbrauchs. Wenn Datenstrukturen in einem kritischen Teil Ihrer Anwendung verwendet werdenMapund wenn Sie große Mengen an Informationen in solche Datenstrukturen schreiben, ist eine solide Kenntnis der Implementierung Mapsicherlich von großem Nutzen für Sie.



Ich habe Java-Entwicklungserfahrung, bin an Java-Sammlungen gewöhnt, bei denen Sie zwischen verschiedenen Implementierungen der Schnittstelle wählen Mapund sogar die ausgewählte Implementierung optimieren können, wenn die entsprechende Klasse dies unterstützt. Darüber hinaus können Sie in Java immer den Open-Source-Code einer beliebigen Klasse der Standardbibliothek lesen und sich mit deren Implementierung vertraut machen (dies kann sich natürlich in neuen Versionen ändern, jedoch nur in Richtung einer Steigerung der Effizienz). Deshalb konnte ich nicht widerstehen zu lernen, wie Objekte Mapin V8 funktionieren .



Bevor wir beginnen, möchte ich darauf hinweisen, dass sich das, was weiter unten erläutert wird, auf die V8 8.4-Engine bezieht, die in die neue Entwicklungsversion von Node.js integriert ist (genauer gesagt, wir sprechen über Commit 238104c). Sie müssen nichts außerhalb der Spezifikation erwarten.

Der Algorithmus hinter der Map-Implementierung

Zunächst möchte ich sagen, dass Datenstrukturen Mapauf Hash-Tabellen basieren. Im Folgenden gehe ich davon aus, dass Sie wissen, wie Hash-Tabellen funktionieren. Wenn Sie nicht vertraut mit Hash - Tabellen sind, dann sollten Sie zunächst über sie zu lesen ( hier zum Beispiel) und nur dann weiter diesen Artikel lesen.



Wenn Sie umfangreiche Erfahrungen mit Objekten haben Map, haben Sie möglicherweise bereits einen Widerspruch bemerkt. Es ist nicht garantiert, dass Hash-Tabellen Elemente in einer konstanten Reihenfolge zurückgeben, wenn sie darüber iterieren. In der ES6-Spezifikation heißt es, dass zum Implementieren eines Objekts Mapbeim Durchlaufen die Elemente in der Reihenfolge zurückgegeben werden müssen, in der sie hinzugefügt wurden. Als Ergebnis der "klassische" Algorithmus für die ImplementierungMapungeeignet. Es besteht jedoch das Gefühl, dass es mit einigen Änderungen weiterhin verwendet werden kann.



V8 verwendet die von Tyler Close vorgeschlagenen sogenannten " deterministischen Hash-Tabellen ". Der folgende Pseudocode, der auf TypeScript basiert, zeigt die grundlegenden Datenstrukturen, die zum Implementieren solcher Hash-Tabellen verwendet werden:

interface Entry {
    key: any;
    value: any;
    chain: number;
}
 
interface CloseTable {
    hashTable: number[];
    dataTable: Entry[];
    nextSlot: number;
    size: number;
}

Hier CloseTablerepräsentiert die Schnittstelle eine Hash-Tabelle. Es enthält ein Array, hashTabledessen Größe der Anzahl der Hash-Container entspricht. Das Array-Element mit dem Index Nentspricht dem N-ten Hash-Container und speichert den Index seines Kopfelements, das sich im Array befindet dataTable. Und dieses Array enthält die Datensätze der Tabelle in der Reihenfolge, in der sie eingefügt wurden. Die Einträge werden von der Schnittstelle dargestellt Entry. Schließlich hat jeder Eintrag eine Eigenschaft chain, die auf den nächsten Eintrag in der Kette der Hash-Container-Einträge verweist (oder genauer gesagt in einer einzeln verknüpften Liste).



Jedes Mal, wenn ein neuer Datensatz in die Tabelle eingefügt wird, wird er im Array-Element dataTablemit Index gespeichertnextSlot... Dieser Prozess erfordert auch das Aktualisieren der Daten im entsprechenden Hash-Container, wodurch der eingefügte Datensatz zum neuen letzten Element der einfach verknüpften Liste wird.



Wenn ein Datensatz aus einer Tabelle entfernt wird, wird er aus einer Tabelle entfernt dataTable(z. B. durch Schreiben in seine Eigenschaften keyund valueWerte undefined). Dann werden der vorhergehende und der darauf folgende Eintrag direkt miteinander verknüpft. Wie Sie vielleicht bemerkt haben, bedeutet dies, dass alle gelöschten Einträge weiterhin Platz in der belegen dataTable.



Und jetzt zum letzten Teil unseres Puzzles. Wenn eine Tabelle mit Datensätzen gefüllt ist (sowohl aktuelle als auch gelöschte), muss sie mit zunehmender Größe erneut aufbereitet (neu erstellt) werden. Die Größe der Tabelle kann nach unten geändert werden.



Bei diesem Ansatz entspricht das Durchlaufen der Datenstruktur dem Durchlaufen eines MapArrays dataTable. Dadurch wird sichergestellt, dass die Reihenfolge, in der Datensätze in die Tabelle eingefügt werden, erhalten bleibt und der Standard eingehalten wird. Vor diesem Hintergrund würde ich erwarten, dass die meisten (wenn nicht alle) JS-Engines deterministische Hash-Tabellen als einen der zugrunde liegenden Implementierungsmechanismen verwenden Map.

Praktische Erforschung des Algorithmus

Schauen wir uns einige Beispiele an, um den Algorithmus in der Praxis zu untersuchen. Angenommen, wir haben CloseTable2 Hash-Container ( hastTable.length), deren Gesamtkapazität 4 Elemente ( dataTable.length) beträgt . Diese Tabelle enthält folgenden Inhalt:

// ,    -, 
// ,     ,   function hashCode(n) { return n; }
table.set(0, 'a'); // => - 0 (0 % 2)
table.set(1, 'b'); // => - 1 (1 % 2)
table.set(2, 'c'); // => - 0 (2 % 2)

Die interne Darstellung der in diesem Beispiel erhaltenen Tabelle könnte folgendermaßen aussehen:

const tableInternals = {
    hashTable: [0, 1],
    dataTable: [
        {
            key: 0,
            value: 'a',
            chain: 2 //  <2, 'c'>
        },
        {
            key: 1,
            value: 'b',
            chain: -1 // -1    
        },
        {
            key: 2,
            value: 'c',
            chain: -1
        },
        //  
    ],
    nextSlot: 3, //    
    size: 3
}

Wenn Sie einen Datensatz mit dieser Methode löschen table.delete(0), sieht die Hash-Tabelle folgendermaßen aus:

const tableInternals = {
    hashTable: [0, 1],
    dataTable: [
        {
            key: undefined, //  
            value: undefined,
            chain: 2 
        },
        {
            key: 1,
            value: 'b',
            chain: -1
        },
        {
            key: 2,
            value: 'c',
            chain: -1
        },
        //  
    ],
    nextSlot: 3,
    size: 2 //  
}

Wenn wir der Tabelle ein paar weitere Datensätze hinzufügen, muss diese gehasht werden. Wir werden diesen Prozess im Folgenden ausführlich diskutieren.



Der gleiche Ansatz kann bei der Implementierung von Datenstrukturen angewendet werden Set. Der einzige Unterschied besteht darin, dass diese Datenstrukturen keine Eigenschaft benötigen value.



Nachdem wir herausgefunden haben, was sich hinter den Objekten Mapin V8 verbirgt, können wir fortfahren.

Implementierungsdetails

Die Datenstrukturimplementierung Mapin V8 wird in C ++ geschrieben, wonach der JS-Code Zugriff auf die entsprechenden Mechanismen erhält. Der größte Teil des Codes Mapbefindet sich in den Klassen OrderedHashTableund OrderedHashMap. Wir wissen bereits, wie diese Klassen funktionieren. Wenn Sie sich den Code selbst ansehen möchten, finden Sie ihn hier , hier und hier .



Da wir uns besonders für die praktischen Details der Implementierung Mapin V8 interessieren , müssen wir zunächst verstehen, wie die Kapazität der Tabelle festgelegt wird.

Tischkapazität

In V8 ist die Kapazität der Hash-Tabelle (Datenstruktur Map) immer eine Zweierpotenz. Wenn wir über die Auslastungsrate von Hash-Containern sprechen, wird sie immer durch die Zahl 2 dargestellt. Das heißt, die maximale Kapazität der Tabelle 2 * number_of_bucketsbeträgt das Zweifache der Anzahl von Hash-Containern. Beim Erstellen eines leeren Objekts Mapbefinden sich 2 Hash-Container in der internen Hash-Tabelle. Infolgedessen entspricht die Kapazität eines solchen Objekts 4 Datensätzen.



Die maximale Kapazität von Objekten ist begrenzt Map. Auf 64-Bit-Systemen sind dies etwa 16,7 Millionen Datensätze. Diese Einschränkung ist auf die Besonderheiten der Darstellung von Datenstrukturen Mapim Heap zurückzuführen. Wir werden später darüber sprechen.



Und schließlich wird der Faktor zum Erhöhen oder Verringern der Tabelle auch immer durch die Multiplikation einer Zahl mit 2 dargestellt. Dies bedeutet, dass nach dem Hinzufügen von 4 Datensätzen zur beschriebenen Tabelle die nächste Einfügeoperation die Tabelle erneut waschen muss, wodurch sich die Tabellengröße um zwei erhöht mal. Mit einer Verringerung der Größe der Tabelle kann sie jeweils zweimal kleiner werden.



Um sicherzustellen, dass das, was ich im Quellcode gesehen habe, genau so funktioniert, wie ich es verstanden habe, habe ich den in Node.js integrierten V8-Engine-Code so geändert, dass eine Mapneue Eigenschaft bucketsenthalten ist Informationen zur Anzahl der Hash-Container. Die Ergebnisse dieser Änderung finden Sie hier... In dieser speziellen Assembly von Node.js kann das folgende Skript ausgeführt werden:

const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
  if (prevBuckets !== map.buckets) {
    console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
    prevBuckets = map.buckets;
  }
  map.set({}, {});
}

Dieses Skript fügt einfach Map100 Datensätze in die Datenstruktur ein . Folgendes wird nach dem Start in der Konsole angezeigt:

$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128

Wie Sie sehen können, erhöht sich die Tabelle bei jeder Änderung ihrer Größe um das Zweifache. Versuchen wir nun, die Tabelle zu verkleinern, indem wir Elemente daraus entfernen:

const map = new Map();
for (let i = 0; i < 100; i++) {
  map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
 
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
  map.delete(i);
  if (prevBuckets !== map.buckets) {
    console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
    prevBuckets = map.buckets;
  }
}

Dieses Skript gibt Folgendes aus:

$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4

Auch hier können Sie sehen, dass die Größe der Tabelle jedes Mal verringert wird, wenn sie weniger number_of_buckets / 2Elemente enthält.

Hash-Funktion

Bisher haben wir die Frage, wie V8 Hash-Codes für in Objekten gespeicherte Schlüssel berechnet, nicht angesprochen Map. Und das ist eine wichtige Frage.



Für Werte, die als numerisch klassifiziert werden können, wird eine bekannte Hash-Funktion mit einer geringen Kollisionswahrscheinlichkeit verwendet.



Für Zeichenfolgenwerte wird ein Hashcode basierend auf den Werten selbst berechnet . Danach wird dieser Code im internen Header zwischengespeichert.



Und schließlich werden für Objekte Hashes basierend auf einer Zufallszahl berechnet, und was passiert, wird dann im internen Header zwischengespeichert.

Zeitliche Komplexität von Operationen mit Kartenobjekten

Die meisten Operationen, die an Datenstrukturen ausgeführt werden Map, wie z. B. setoder delete, erfordern das Durchsuchen dieser Datenstrukturen. Wie bei den "klassischen" Hash-Tabellen ist die zeitliche Komplexität der Suche in unserem Fall O(1).



Stellen Sie sich ein Worst-Case-Szenario vor, in dem der Tisch voll ist, dh Nvon den NSitzen aus besetzt ist. In diesem Fall gehören alle Datensätze zu einem einzelnen Hash-Container, und der erforderliche Datensatz befindet sich ganz am Ende der Datensatzkette. In einem solchen Szenario müssen Sie Schritte unternehmen, um diesen Eintrag zu finden N.



Wenn im besten Fall die Tabelle voll ist und nur zwei Datensätze in jedem Hash-Container vorhanden sind, sind im besten Fall nur zwei Schritte erforderlich, um einen Datensatz zu finden.



Bestimmte Operationen in Hash-Tabellen sind sehr schnell, dies ist jedoch bei Hash-Operationen nicht der Fall. Die zeitliche Komplexität der Hash-Operation beträgt O(N). Auf dem Heap muss eine neue Hash-Tabelle zugewiesen werden. Darüber hinaus wird das Aufwärmen nach Bedarf als Teil der Vorgänge zum Einfügen oder Entfernen von Elementen aus der Tabelle durchgeführt. Daher map.set()kann sich der Anruf beispielsweise als viel "teurer" als erwartet herausstellen. Glücklicherweise wird die Hash-Operation selten ausgeführt.

Speicherverbrauch

Natürlich muss die zugrunde liegende Hash-Tabelle Mapirgendwie auf dem Heap gespeichert werden. Es wird in einem sogenannten "Hilfsspeicher" gespeichert. Und hier erwartet uns eine weitere interessante Tatsache. Die gesamte Tabelle (und damit alles, was darin platziert ist Map) wird in einem einzigen Array fester Länge gespeichert. Die Struktur dieses Arrays ist in der folgenden Abbildung dargestellt.





Array zum Speichern von Kartendatenstrukturen im Speicher Die



einzelnen Teile des Arrays dienen folgenden Zwecken:

• Header: Enthält allgemeine Informationen, z. B. die Anzahl der Hash-Container oder die Anzahl der Elemente, aus denen entfernt wurde Map.
• Hash-Container-Details: Hier speichern wir Daten zu den Containern, die dem Array hashTableaus unserem Beispiel entsprechen.
• Hash-Tabelleneinträge: Hier werden die dem Array entsprechenden Daten gespeichert dataTable. Es enthält nämlich Informationen zu Hash-Tabelleneinträgen. Jeder Datensatz belegt drei Zellen im Array. Einer speichert den Schlüssel, der zweite speichert den Wert und der dritte speichert den "Zeiger" auf den nächsten Datensatz in der Kette.

Wenn wir über die Größe des Arrays sprechen, kann es grob geschätzt werden als N * 3,5. Hier Nist die Kapazität der Tabelle. Um was das bedeutet in Bezug auf den Speicherverbrauch zu verstehen, stellen wir uns vor , dass wir eine 64-Bit - System und den V8 haben Zeigerkomprimierung Funktion ist deaktiviert . In diesem Fall werden 8 Bytes benötigt, um jedes Element des Arrays zu speichern. Infolgedessen Mapsind 29 MB Heapspeicher erforderlich , um eine Datenstruktur zu speichern , die ungefähr 1 Million Datensätze enthält.

Ergebnis

In diesem Artikel haben wir viele Dinge im Zusammenhang mit der Datenstruktur Mapin JavaScript behandelt. Fassen wir zusammen:

• V8 Mapverwendet deterministische Hash-Tabellen für die Implementierung . Es ist sehr wahrscheinlich, dass diese Datenstruktur auch in anderen JS-Engines implementiert ist.
• Die Mechanismen, die die Arbeit unterstützen, Mapsind in C ++ implementiert. Anschließend werden sie als API dargestellt, auf die über JavaScript zugegriffen werden kann.
• Wenn wir über die zeitliche Komplexität von Operationen sprechen, die mit Objekten ausgeführt werden Map, dann sind sie sowie bei der Arbeit mit "klassischen" Hash-Tabellen komplex O(1). In diesem Fall ist die zeitliche Komplexität der Hashing-Operation O(N).
• 64- Map 1 29 , .
• , , Set.

Map JavaScript-?