Was ist die Leistung von Objekten / Arrays in JavaScript? (speziell für Google V8)

Die mit Arrays und Objekten in JavaScript (insbesondere Google V8) verbundene Leistung wäre sehr interessant zu dokumentieren. Ich finde nirgendwo im Internet einen umfassenden Artikel zu diesem Thema.

Ich verstehe, dass einige Objekte Klassen als zugrunde liegende Datenstruktur verwenden. Wenn es viele Eigenschaften gibt, wird es manchmal als Hash-Tabelle behandelt?

Ich verstehe auch, dass Arrays manchmal wie C ++ - Arrays behandelt werden (dh schnelle zufällige Indizierung, langsames Löschen und Ändern der Größe). In anderen Fällen werden sie eher wie Objekte behandelt (schnelle Indizierung, schnelles Einfügen / Entfernen, mehr Speicher). Und vielleicht werden sie manchmal als verknüpfte Listen gespeichert (dh langsame zufällige Indizierung, schnelles Entfernen / Einfügen am Anfang / Ende)

Was ist die genaue Leistung von Array- / Objektabrufen und -manipulationen in JavaScript? (speziell für Google V8)

Genauer gesagt, welche Auswirkungen hat dies auf die Leistung:

• Hinzufügen einer Eigenschaft zu einem Objekt
• Entfernen einer Eigenschaft aus einem Objekt
• Indizieren einer Eigenschaft in einem Objekt
• Hinzufügen eines Elements zu einem Array
• Entfernen eines Elements aus einem Array
• Indizieren eines Elements in einem Array
• Array.pop () aufrufen
• Array.push () aufrufen
• Array.shift () aufrufen
• Array.unshift () aufrufen
• Array.slice () aufrufen

Alle Artikel oder Links für weitere Details sind ebenfalls willkommen. :) :)

EDIT: Ich frage mich wirklich, wie JavaScript-Arrays und -Objekte unter der Haube funktionieren. In welchem Kontext "weiß" die V8-Engine, auf eine andere Datenstruktur "umzuschalten"?

Angenommen, ich erstelle ein Array mit ...

var arr = [];
arr[10000000] = 20;
arr.push(21);

Was ist hier wirklich los?

Oder ... was ist damit ... ???

var arr = [];
//Add lots of items
for(var i = 0; i < 1000000; i++)
    arr[i] = Math.random();
//Now I use it like a queue...
for(var i = 0; i < arr.length; i++)
{
    var item = arr[i].shift();
    //Do something with item...
}

Bei herkömmlichen Arrays wäre die Leistung schrecklich. wohingegen, wenn eine LinkedList verwendet wurde ... nicht so schlecht.

Ich habe eine Testsuite erstellt, um genau diese (und weitere) Probleme zu untersuchen ( archivierte Kopie ).

In diesem Sinne können Sie die Leistungsprobleme in diesem Testfalltester über 50 sehen (es wird lange dauern).

Wie der Name schon sagt, wird die Verwendung der nativen verknüpften Listennatur der DOM-Struktur untersucht.

(Derzeit nicht verfügbar, wird gerade umgebaut.) Weitere Details dazu in meinem Blog .

Die Zusammenfassung ist wie folgt

• V8 Array ist schnell, sehr schnell
• Array Push / Pop / Shift ist ca. ca. 20x schneller als jedes Objektäquivalent.
• Überraschenderweise Array.shift()ist es ungefähr 6x langsamer als ein Array-Pop, aber ungefähr 100x schneller als das Löschen von Objektattributen.
• Amüsanterweise Array.push( data );ist es schneller als Array[nextIndex] = datafast 20 (dynamisches Array) bis 10 (festes Array) Mal.
• Array.unshift(data) ist langsamer als erwartet und ~ ca. 5x langsamer als das Hinzufügen einer neuen Eigenschaft.
• Das Nullstellen des Werts array[index] = nullist schneller als das Löschen delete array[index](undefiniert) in einem Array um ~ ca. 4x ++ schneller.
• Überraschenderweise ist das Nullstellen eines Werts in einem Objekt obj[attr] = nullca. 2x langsamer als das Löschen des Attributsdelete obj[attr]
• Es überrascht nicht, dass das mittlere Array Array.splice(index,0,data)langsam und sehr langsam ist.
• Überraschenderweise Array.splice(index,1,data)wurde optimiert (keine Längenänderung) und ist 100x schneller als nur SpleißenArray.splice(index,0,data)
• Es ist nicht überraschend, dass die divLinkedList einem Array in allen Sektoren unterlegen ist, mit Ausnahme der dll.splice(index,1)Entfernung (wo das Testsystem beschädigt wurde ).
• GRÖSSTE ÜBERRASCHUNG [wie jjrv hervorhob], V8-Array-Schreibvorgänge sind etwas schneller als V8-Lesevorgänge = O.

Hinweis: Diese Metriken gelten nur für große Arrays / Objekte, die in Version 8 nicht "vollständig optimiert" werden. Es kann sehr isolierte optimierte Leistungsfälle für Array- / Objektgrößen geben, die kleiner als eine beliebige Größe (24?) Sind. Weitere Details finden Sie in mehreren Google IO-Videos.

Hinweis 2: Diese wunderbaren Leistungsergebnisse werden nicht von allen Browsern, insbesondere dem *cough*Internet Explorer, geteilt. Auch der Test ist riesig, daher muss ich die Ergebnisse noch vollständig analysieren und bewerten: Bitte bearbeiten Sie ihn in =)

Aktualisierter Hinweis (Dezember 2012): Google-Vertreter haben Videos auf youtubes, in denen das Innenleben von Chrome selbst (z. B. beim Wechsel von einem verknüpften Listenarray zu einem festen Array usw.) und deren Optimierung beschrieben werden. Weitere Informationen finden Sie unter GDC 2012: Von der Konsole zu Chrome .

Auf einer grundlegenden Ebene, die im Bereich von JavaScript bleibt, sind Eigenschaften von Objekten viel komplexere Entitäten. Sie können Eigenschaften mit Setzern / Gettern mit unterschiedlicher Aufzählbarkeit, Beschreibbarkeit und Konfigurierbarkeit erstellen. Ein Element in einem Array kann nicht auf diese Weise angepasst werden: Es ist entweder vorhanden oder nicht. Auf der zugrunde liegenden Engine-Ebene ermöglicht dies eine wesentlich bessere Optimierung hinsichtlich der Organisation des Speichers, der die Struktur darstellt.

In Bezug auf die Identifizierung eines Arrays aus einem Objekt (Wörterbuch) haben JS-Engines immer explizite Linien zwischen den beiden gezogen. Aus diesem Grund gibt es eine Vielzahl von Artikeln über Methoden zum Erstellen eines semi-gefälschten Array-ähnlichen Objekts, das sich wie eines verhält, aber andere Funktionen zulässt. Der Grund, warum diese Trennung überhaupt besteht, ist, dass die JS-Engines die beiden unterschiedlich speichern.

Eigenschaften können in einem Array-Objekt gespeichert werden. Dies zeigt jedoch lediglich, wie JavaScript darauf besteht, alles zu einem Objekt zu machen. Die indizierten Werte in einem Array werden anders gespeichert als alle Eigenschaften, die Sie für das Array-Objekt festlegen, das die zugrunde liegenden Array-Daten darstellt.

Immer wenn Sie ein legitimes Array-Objekt verwenden und eine der Standardmethoden zum Bearbeiten dieses Arrays verwenden, werden Sie auf die zugrunde liegenden Array-Daten stoßen. Insbesondere in V8 entsprechen diese im Wesentlichen einem C ++ - Array, sodass diese Regeln gelten. Wenn Sie aus irgendeinem Grund mit einem Array arbeiten, das die Engine nicht mit Sicherheit als Array bestimmen kann, befinden Sie sich auf einem viel wackeligeren Boden. Mit den neuesten Versionen von V8 gibt es jedoch mehr Platz zum Arbeiten. Beispielsweise ist es möglich, eine Klasse zu erstellen, deren Prototyp Array.prototype ist, und dennoch effizienten Zugriff auf die verschiedenen nativen Array-Manipulationsmethoden zu erhalten. Dies ist jedoch eine kürzliche Änderung.

Spezifische Links zu den letzten Änderungen an der Array-Manipulation können hier nützlich sein:

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

Als kleines Extra sind hier Array Pop und Array Push direkt aus der V8-Quelle, beide in JS selbst implementiert:

function ArrayPop() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.pop"]);
  }

  var n = TO_UINT32(this.length);
  if (n == 0) {
    this.length = n;
    return;
  }
  n--;
  var value = this[n];
  this.length = n;
  delete this[n];
  return value;
}


function ArrayPush() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.push"]);
  }

  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
}

Ich möchte vorhandene Antworten durch eine Untersuchung der Frage ergänzen, wie sich Implementierungen in Bezug auf wachsende Arrays verhalten: Wenn sie auf die "übliche" Weise implementiert werden, würde man viele schnelle Pushs mit seltenen, eingestreuten langsamen Pushs sehen, an welchem ​​Punkt die Implementierung kopiert die interne Darstellung des Arrays von einem Puffer zu einem größeren.

Sie können diesen Effekt sehr gut sehen, dies ist von Chrome:

16: 4ms
40: 8ms 2.5
76: 20ms 1.9
130: 31ms 1.7105263157894737
211: 14ms 1.623076923076923
332: 55ms 1.5734597156398105
514: 44ms 1.5481927710843373
787: 61ms 1.5311284046692606
1196: 138ms 1.5196950444726811
1810: 139ms 1.5133779264214047
2731: 299ms 1.5088397790055248
4112: 341ms 1.5056755767118273
6184: 681ms 1.5038910505836576
9292: 1324ms 1.5025873221216042

Obwohl jeder Push profiliert ist, enthält die Ausgabe nur diejenigen, die über einem bestimmten Schwellenwert Zeit benötigen. Für jeden Test habe ich den Schwellenwert so angepasst, dass alle Pushs ausgeschlossen werden, die die schnellen Pushs darstellen.

Die erste Zahl gibt also an, welches Element eingefügt wurde (die erste Zeile steht für das 17. Element), die zweite gibt an, wie lange es gedauert hat (für viele Arrays wird der Benchmark parallel durchgeführt), und der letzte Wert ist die Division des erste Zahl durch die in der vorherigen Zeile.

Alle Zeilen mit einer Ausführungszeit von weniger als 2 ms sind für Chrome ausgeschlossen.

Sie können sehen, dass Chrome die Array-Größe in Potenzen von 1,5 plus einen gewissen Versatz erhöht, um kleine Arrays zu berücksichtigen.

Für Firefox ist es eine Zweierpotenz:

126: 284ms
254: 65ms 2.015873015873016
510: 28ms 2.0078740157480315
1022: 58ms 2.003921568627451
2046: 89ms 2.0019569471624266
4094: 191ms 2.0009775171065494
8190: 364ms 2.0004885197850513

Ich musste die Schwelle in Firefox ziemlich hoch legen, deshalb fangen wir bei # 126 an.

Mit IE bekommen wir eine Mischung:

256: 11ms 256
512: 26ms 2
1024: 77ms 2
1708: 113ms 1.66796875
2848: 154ms 1.6674473067915691
4748: 423ms 1.6671348314606742
7916: 944ms 1.6672283066554338

Es ist zuerst eine Zweierpotenz und dann eine Potenz von fünf Dritteln.

Daher verwenden alle gängigen Implementierungen den "normalen" Weg für Arrays (anstatt zum Beispiel mit Seilen verrückt zu werden ).

Hier ist der Benchmark-Code und hier ist die Geige , in der er sich befindet.

var arrayCount = 10000;

var dynamicArrays = [];

for(var j=0;j<arrayCount;j++)
    dynamicArrays[j] = [];

var lastLongI = 1;

for(var i=0;i<10000;i++)
{
    var before = Date.now();
    for(var j=0;j<arrayCount;j++)
        dynamicArrays[j][i] = i;
    var span = Date.now() - before;
    if (span > 10)
    {
      console.log(i + ": " + span + "ms" + " " + (i / lastLongI));
      lastLongI = i;
    }
}

Während der Ausführung unter node.js 0.10 (basierend auf Version 8) wurde eine CPU-Auslastung festgestellt, die für die Arbeitslast zu hoch schien. Ich habe ein Leistungsproblem auf eine Funktion zurückgeführt, die das Vorhandensein einer Zeichenfolge in einem Array überprüft hat. Also habe ich einige Tests durchgeführt.

• 90.822 Hosts geladen
• Das Laden der Konfiguration dauerte 0,087 Sekunden (Array)
• Das Laden der Konfiguration dauerte 0,152 Sekunden (Objekt)

Das Laden von 91k-Einträgen in ein Array (mit validate & push) ist schneller als das Setzen von obj [key] = value.

Im nächsten Test habe ich jeden Hostnamen in der Liste einmal nachgeschlagen (91.000 Iterationen, um die Suchzeit zu mitteln):

• Die Suche in der Konfiguration dauerte 87,56 Sekunden (Array)
• Die Suche in der Konfiguration dauerte 0,21 Sekunden (Objekt)

Die Anwendung hier ist Haraka (ein SMTP-Server). Sie lädt die host_list einmal beim Start (und nach Änderungen) und führt diese Suche anschließend während des Betriebs millionenfach durch. Der Wechsel zu einem Objekt war ein großer Leistungsgewinn.