Warum ist array.push manchmal schneller als array [n] = value?

Als Nebenergebnis beim Testen von Code habe ich eine kleine Funktion geschrieben, um die Geschwindigkeit der Verwendung der array.push-Methode mit der direkten Adressierung zu vergleichen (array [n] = value). Zu meiner Überraschung erwies sich die Push-Methode insbesondere in Firefox und manchmal in Chrome oft als schneller. Nur aus Neugier: Hat jemand eine Erklärung dafür? Sie finden den Test auf dieser Seite (klicken Sie auf 'Vergleich der Array-Methoden').

Alle möglichen Faktoren spielen eine Rolle. Die meisten JS-Implementierungen verwenden ein flaches Array, das in einen spärlichen Speicher konvertiert wird, wenn dies später erforderlich wird.

Grundsätzlich ist die Entscheidung, spärlich zu werden, eine Heuristik, die darauf basiert, welche Elemente festgelegt werden und wie viel Platz verschwendet würde, um flach zu bleiben.

In Ihrem Fall setzen Sie zuerst das letzte Element, was bedeutet, dass die JS-Engine ein Array sieht, das eine Länge von nnur einem einzelnen Element haben muss. Wenn nes groß genug ist, wird das Array sofort zu einem Array mit geringer Dichte. In den meisten Engines bedeutet dies, dass alle nachfolgenden Einfügungen den Fall eines langsamen Arrays mit geringer Dichte annehmen.

Sie sollten einen zusätzlichen Test hinzufügen, in dem Sie das Array von Index 0 bis Index n-1 füllen - es sollte viel, viel schneller sein.

Als Antwort auf @Christoph und aus dem Wunsch heraus zu zögern, finden Sie hier eine Beschreibung, wie Arrays (allgemein) in JS implementiert werden - die Besonderheiten variieren von JS-Engine zu JS-Engine, aber das allgemeine Prinzip ist dasselbe.

Alle JS Object(also keine Zeichenfolgen, Zahlen, true, false undefinedoder null) erben von einem Basisobjekttyp - die genaue Implementierung variiert, es kann sich um eine C ++ - Vererbung oder manuell in C handeln (dies hat beide Vorteile ) - Der Basisobjekttyp definiert die Standardmethoden für den Zugriff auf Eigenschaften, z.

interface Object {
    put(propertyName, value)
    get(propertyName)
private:
    map properties; // a map (tree, hash table, whatever) from propertyName to value
}

Dieser Objekttyp behandelt die gesamte Standard-Eigenschaftszugriffslogik, die Prototypenkette usw. Dann wird die Array-Implementierung

interface Array : Object {
    override put(propertyName, value)
    override get(propertyName)
private:
    map sparseStorage; // a map between integer indices and values
    value[] flatStorage; // basically a native array of values with a 1:1
                         // correspondance between JS index and storage index
    value length; // The `length` of the js array
}

Wenn Sie nun ein Array in JS erstellen, erstellt die Engine etwas, das der obigen Datenstruktur ähnelt. Wenn Sie ein Objekt in die Array-Instanz einfügen, prüft die put-Methode des Arrays, ob der Eigenschaftsname eine Ganzzahl ist (oder in eine Ganzzahl konvertiert werden kann, z. B. "121", "2341" usw.) zwischen 0 und 2 ^ 32 -1 (oder möglicherweise 2 ^ 31-1, ich vergesse genau). Ist dies nicht der Fall, wird die put-Methode an die Basisobjektimplementierung weitergeleitet, und die Standardlogik [[Put]] wird ausgeführt. Andernfalls wird der Wert in den eigenen Speicher des Arrays gestellt. Wenn die Daten ausreichend kompakt sind, verwendet die Engine den Flat-Array-Speicher. In diesem Fall ist das Einfügen (und Abrufen) nur eine Standard-Array-Indizierungsoperation, andernfalls konvertiert die Engine das Array Verwenden Sie eine Karte, um von propertyName zu value location zu gelangen.

Ich bin mir ehrlich gesagt nicht sicher, ob eine JS-Engine nach dieser Konvertierung derzeit von dünnem zu flachem Speicher konvertiert.

Wie auch immer, das ist ein ziemlich allgemeiner Überblick darüber, was passiert, und lässt einige der schwierigeren Details aus, aber das ist das allgemeine Implementierungsmuster. Die Einzelheiten darüber, wie der zusätzliche Speicher und wie Put / Get versendet werden, sind von Motor zu Motor unterschiedlich - aber dies ist das klarste, was ich wirklich beschreiben kann.

Ein kleiner Zusatzpunkt, während die ES-Spezifikation propertyNameals Zeichenfolge bezeichnet wird. JS-Engines sind in der Regel auch auf die Suche nach Ganzzahlen spezialisiert. Daher someObject[someInteger]wird die Ganzzahl nicht in eine Zeichenfolge konvertiert, wenn Sie ein Objekt mit ganzzahligen Eigenschaften betrachten, z. Array-, String- und DOM-Typen ( NodeLists usw.).

Dies ist das Ergebnis, das ich mit Ihrem Test erhalte

auf Safari:

• Array.push (n) 1.000.000 Werte: 0,124 Sek
• Array [n .. 0] = Wert (absteigend) 1.000.000 Werte: 3,697 Sek
• Array [0 .. n] = Wert (aufsteigend) 1.000.000 Werte: 0,073 Sek

auf FireFox:

• Array.push (n) 1.000.000 Werte: 0,075 Sek
• Array [n .. 0] = Wert (absteigend) 1.000.000 Werte: 1,193 Sek
• Array [0 .. n] = Wert (aufsteigend) 1.000.000 Werte: 0,055 Sek

auf IE7:

• Array.push (n) 1.000.000 Werte: 2,828 Sek
• Array [n .. 0] = Wert (absteigend) 1.000.000 Werte: 1,141 Sek
• Array [0 .. n] = Wert (aufsteigend) 1.000.000 Werte: 7,984 Sek

Laut Ihrem Test scheint die Push- Methode im IE7 besser zu sein (großer Unterschied), und da der Unterschied in den anderen Browsern gering ist, scheint die Push- Methode wirklich der beste Weg zu sein, einem Array ein Element hinzuzufügen.

Aber ich habe ein anderes einfaches Testskript erstellt, um zu überprüfen, mit welcher Methode Werte schnell an ein Array angehängt werden können. Die Ergebnisse haben mich wirklich überrascht. Die Verwendung von Array.length scheint im Vergleich zur Verwendung von Array.push viel schneller zu sein , daher weiß ich wirklich nicht, was zu sagen oder zu denken, ich bin ahnungslos.

Übrigens: Auf meinem IE7 stoppt Ihr Skript und der Browser fragt mich, ob ich es weitergehen lassen möchte (Sie kennen die typische IE-Meldung: "Stop runnign this script? ..."). Ich würde empfehlen, die Schleifen ein wenig zu reduzieren .

push() ist ein Sonderfall des allgemeineren [[Put]] und kann daher weiter optimiert werden:

Beim Aufruf von [[Put]] für ein Array-Objekt muss das Argument zuerst in eine Ganzzahl ohne Vorzeichen konvertiert werden, da alle Eigenschaftsnamen - einschließlich Array-Indizes - Zeichenfolgen sind. Dann muss es mit der Längeneigenschaft des Arrays verglichen werden, um zu bestimmen, ob die Länge erhöht werden muss oder nicht. Beim Push muss keine solche Konvertierung oder kein solcher Vergleich stattfinden: Verwenden Sie einfach die aktuelle Länge als Array-Index und erhöhen Sie sie.

Natürlich gibt es andere Dinge, die sich auf die Laufzeit auswirken, z. B. push()sollte der Aufruf langsamer sein als der Aufruf von [[Put]] über, []da die Prototypkette auf die erstere überprüft werden muss.

Wie olliej betonte: Durch tatsächliche ECMAScript-Implementierungen wird die Konvertierung optimiert, dh für numerische Eigenschaftsnamen wird keine Konvertierung von Zeichenfolge in uint durchgeführt, sondern nur eine einfache Typprüfung. Die Grundannahme sollte weiterhin gelten, obwohl ihre Auswirkungen geringer sein werden als ursprünglich angenommen.

Hier ist eine gute Testumgebung, die bestätigt, dass die direkte Zuweisung erheblich schneller ist als Push: http://jsperf.com/array-direct-assignment-vs-push .

Bearbeiten: Es scheint ein Problem bei der Anzeige kumulativer Ergebnisdaten zu geben, aber hoffentlich wird es bald behoben.

array[n] = value(beim Aufsteigen) ist immer schneller als array.pushwenn das Array im ersteren Fall zuerst mit einer Länge initialisiert wird.

Von der Überprüfung des Javascript-Quellcodes von Ihrer SeiteArray[0 .. n] = value (ascending) überprüfen, initialisiert Ihr Test das Array nicht mit einer Länge im Voraus.

So Array.push(n)kommt es manchmal beim ersten Durchlauf voran, aber bei nachfolgenden Durchläufen Ihres Tests ist die Leistung Array[0 .. n] = value (ascending)tatsächlich konstant am besten (sowohl in Safari als auch in Chrome).

Wenn der Code geändert wird , so dass es ein Array mit einer Länge im Voraus wie initialisiert var array = new Array(n)dann Array[0 .. n] = value (ascending)zeigt , dassarray[n] = value 4.5x führt schneller 9x alsArray.push(n) in meinem rudimentären Betrieb dieses speziellen Testcode.

Dies steht im Einklang mit anderen Tests, wie @Timo Kähkönen berichtete. Siehe speziell diese Revision des von ihm erwähnten Tests: https://jsperf.com/push-method-vs-setting-via-key/10

Der geänderte Code, damit Sie sehen können, wie ich ihn bearbeitet und das Array auf faire Weise initialisiert habe (nicht unnötig mit einer Länge für den Testfall array.push initialisiert):

function testArr(n, doPush){

  var now = new Date().getTime(),
                  duration,
                  report =  ['<b>.push(n)</b>',
                             '<b>.splice(0,0,n)</b>',
                             '<b>.splice(n-1,0,n)</b>',
                             '<b>[0 .. n] = value</b> (ascending)',
                             '<b>[n .. 0] = value</b> (descending)'];
  doPush = doPush || 5;

  if (doPush === 1) {
   var arr = [];
   while (--n) {
     arr.push(n);
   }
  } else if (doPush === 2) {
   var arr = [];
   while (--n) {
    arr.splice(0,0,n);
   }
  } else if (doPush === 3) {
   var arr = [];
   while (--n) {
    arr.splice(n-1,0,n);
   }
  } else if (doPush === 4) {
   var arr = new Array(n);
   for (var i = 0;i<n;i++) {
    arr[i] = i;
   }
  } else {
    while (--n) {
    var arr = [];
      arr[n] = n;
    }
  }
  /*console.log(report[doPush-1] + '...'+ arr.length || 'nopes');*/
  duration = ((new Date().getTime() - now)/1000);
  $('zebradinges').innerHTML +=  '<br>Array'+report[doPush-1]+' 1.000.000 values: '+duration+' sec' ;
  arr = null;
}

Push fügt es am Ende hinzu, während Array [n] das Array durchlaufen muss, um den richtigen Punkt zu finden. Hängt wahrscheinlich vom Browser und seiner Art ab, mit Arrays umzugehen.