Warum ist die Verkettung von Zeichenfolgen schneller als die Array-Verknüpfung?

114

Heute habe ich diesen Thread über die Geschwindigkeit der Verkettung von Zeichenfolgen gelesen .

Überraschenderweise war die Verkettung von Zeichenfolgen der Gewinner:

http://jsben.ch/#/OJ3vo

Das Ergebnis war das Gegenteil von dem, was ich dachte. Außerdem gibt es viele Artikel über diese , die wie entgegengesetzt zu erklären dies .

Ich kann mir vorstellen, dass Browser so optimiert sind, dass sie concatauf der neuesten Version angezeigt werden , aber wie machen sie das? Können wir sagen, dass es besser ist, +Zeichenfolgen zu verketten?


Aktualisieren

So wird in modernen Browsern String - Verkettung so optimiert, mit +Zeichen ist schneller als die Verwendung , joinwenn Sie möchten , verketten Saiten.

Aber @Arthur wies darauf hin , dass joinschneller ist , wenn Sie tatsächlich wollen beitreten Strings mit einem Separator.


Update - 2020
Chrome: Array joinist fast 2 times fasterString concat + Siehe: https://stackoverflow.com/a/54970240/984471

Als Hinweis:

  • Array joinist besser, wenn Sie habenlarge strings
  • Wenn wir several small stringsin der endgültigen Ausgabe generieren müssen , ist es besser, mit string concat zu arbeiten +, da andernfalls für Array am Ende mehrere Konvertierungen von Array zu String erforderlich sind , was zu einer Leistungsüberlastung führt.

Sanghyun Lee
quelle
1
Dieser Code soll 500 Terabyte Müll produzieren, läuft aber in 200 ms. Ich denke, dass sie nur etwas mehr Platz für eine Zeichenfolge reservieren, und wenn Sie eine kurze Zeichenfolge hinzufügen, passt diese normalerweise in einen zusätzlichen Bereich.
Ivan Kuckir

Antworten:

148

Browser-String-Optimierungen haben das Bild der String-Verkettung geändert.

Firefox war der erste Browser, der die Verkettung von Zeichenfolgen optimierte. Ab Version 1.0 ist die Array-Technik in allen Fällen langsamer als die Verwendung des Plus-Operators. Andere Browser haben ebenfalls die Verkettung von Zeichenfolgen optimiert, sodass Safari, Opera, Chrome und Internet Explorer 8 mit dem Plus-Operator ebenfalls eine bessere Leistung erzielen. Internet Explorer vor Version 8 hatte keine solche Optimierung, daher ist die Array-Technik immer schneller als der Plus-Operator.

- Effizientes JavaScript schreiben: Kapitel 7 - Noch schnellere Websites

Die V8-Javascript-Engine (in Google Chrome verwendet) verwendet diesen Code, um die Verkettung von Zeichenfolgen durchzuführen:

// ECMA-262, section 15.5.4.6
function StringConcat() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined", ["String.prototype.concat"]);
  }
  var len = %_ArgumentsLength();
  var this_as_string = TO_STRING_INLINE(this);
  if (len === 1) {
    return this_as_string + %_Arguments(0);
  }
  var parts = new InternalArray(len + 1);
  parts[0] = this_as_string;
  for (var i = 0; i < len; i++) {
    var part = %_Arguments(i);
    parts[i + 1] = TO_STRING_INLINE(part);
  }
  return %StringBuilderConcat(parts, len + 1, "");
}

Intern optimieren sie es also, indem sie ein InternalArray (die partsVariable) erstellen , das dann gefüllt wird. Die StringBuilderConcat-Funktion wird mit diesen Teilen aufgerufen. Es ist schnell, weil die StringBuilderConcat-Funktion stark optimierter C ++ - Code ist. Es ist zu lang, um hier zu zitieren, aber suchen Sie in der Datei runtime.ccRUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat) nach dem Code.

Daan
quelle
4
Sie haben das wirklich Interessante ausgelassen, das Array wird nur verwendet, um Runtime_StringBuilderConcat mit unterschiedlichen Argumentzahlen aufzurufen. Aber die eigentliche Arbeit ist dort erledigt.
Evilpie
41
Optimierung 101: Sie sollten auf die geringste Langsamkeit zielen! Zum Beispiel erhalten arr.join vs str+Sie auf Chrom (in Operationen pro Sekunde) 25k/s vs 52k/s. auf Firefox neu bekommt man 76k/s vs 212k/s. so str+ist SCHNELLER. aber schauen wir uns andere Browser an. Opera gibt 43k / s vs 26k / s. IE gibt 1300/s vs 1002/s. Schau was passiert? Der einzige Browser, der eine Optimierung benötigt, ist besser dran, wenn er das verwendet, was bei allen anderen langsamer ist, wo es überhaupt keine Rolle spielt. Keiner dieser Artikel versteht etwas über Leistung.
GCB
45
@gcb, die einzigen Browser, für die der Join schneller ist, sollten nicht verwendet werden. 95% meiner Nutzer haben FF und Chrome. Ich werde für den 95% Anwendungsfall optimieren.
Paul Draper
7
@PaulDraper Wenn 90% der Benutzer einen schnellen Browser verwenden und eine der von Ihnen gewählten Optionen 0,001 Sekunden erhält, erhalten 10% Ihrer Benutzer 2 Sekunden, wenn Sie die anderen Benutzer aus diesen 0,001 Sekunden heraus bestrafen ... die Entscheidung ist klar. Wenn Sie es nicht sehen können, tut es mir leid, für wen Sie codieren.
GCB
7
Ältere Browser werden irgendwann verschwinden, aber die Wahrscheinlichkeit, dass jemand zurückkehrt, um all diese Array-Joins zu konvertieren, ist unwahrscheinlich. Es ist besser, für die Zukunft zu programmieren, solange dies für Ihre derzeitigen Benutzer keine große Unannehmlichkeit darstellt. Wahrscheinlich gibt es wichtigere Dinge als die Verkettungsleistung beim Umgang mit alten Browsern.
Thomas Higginbotham
23

Firefox ist schnell, weil es sogenannte Seile verwendet ( Seile: eine Alternative zu Strings ). Ein Seil ist im Grunde nur eine DAG, bei der jeder Knoten eine Schnur ist.

Wenn Sie dies beispielsweise tun würden a = 'abc'.concat('def'), würde das neu erstellte Objekt folgendermaßen aussehen. Natürlich sieht das im Speicher nicht genau so aus, da Sie noch ein Feld für den Zeichenfolgentyp, die Länge und möglicherweise ein anderes benötigen.

a = {
 nodeA: 'abc',
 nodeB: 'def'
}

Und b = a.concat('123')

b = {
  nodeA: a, /* {
             nodeA: 'abc',
             nodeB: 'def'
          } */
  nodeB: '123'
}           

Im einfachsten Fall muss die VM also fast keine Arbeit leisten. Das einzige Problem ist, dass dies andere Operationen an der resultierenden Zeichenfolge etwas verlangsamt. Auch dies reduziert natürlich den Speicheraufwand.

Auf der anderen Seite ['abc', 'def'].join('')würde normalerweise nur Speicher zugewiesen, um die neue Zeichenfolge flach im Speicher auszulegen. (Vielleicht sollte dies optimiert werden)

Evilpie
quelle
6

Ich weiß, dass dies ein alter Thread ist, aber Ihr Test ist falsch. Sie tun, output += myarray[i];während es eher so sein sollte, output += "" + myarray[i];weil Sie vergessen haben, dass Sie Gegenstände mit etwas zusammenkleben müssen. Der Concat-Code sollte ungefähr so ​​lauten:

var output = myarray[0];
for (var i = 1, len = myarray.length; i<len; i++){
    output += "" + myarray[i];
}

Auf diese Weise führen Sie zwei Operationen anstelle einer durch, indem Sie Elemente zusammenkleben.

Array.join() ist schneller.

Arthur
quelle
Ich verstehe deine Antwort nicht. Was ist der Unterschied zwischen Putten "" +und Original?
Sanghyun Lee
Es sind zwei Operationen anstelle einer bei jeder Iteration, was mehr Zeit in Anspruch nimmt.
Arthur
1
Und warum müssen wir das sagen? Wir kleben bereits Artikel outputohne.
Sanghyun Lee
Denn so funktioniert Join. Zum Beispiel können Sie auch tun, Array.join(",")was mit Ihrer forSchleife nicht funktioniert
Arthur
Oh, ich habe es. Haben Sie bereits getestet, ob join () schneller ist?
Sanghyun Lee
5

Bei großen Datenmengen ist die Verknüpfung schneller, sodass die Frage falsch angegeben wird.

let result = "";
let startTime = new Date().getTime();
for (let i = 0; i < 2000000; i++) {
    result += "x";
}
console.log("concatenation time: " + (new Date().getTime() - startTime));

startTime = new Date().getTime();
let array = new Array(2000000);
for (let i = 0; i < 2000000; i++) {
    array[i] = "x";
}
result = array.join("");
console.log("join time: " + (new Date().getTime() - startTime));

Getestet auf Chrome 72.0.3626.119, Firefox 65.0.1, Edge 42.17134.1.0. Beachten Sie, dass es auch mit der enthaltenen Array-Erstellung schneller geht!

fast ein
quelle
~ Aug 2020. Richtig. In Chrome: Array-Verknüpfungszeit: 462. String Concat (+) -Zeit: 827. Die Verknüpfung ist fast zweimal schneller.
Manohar Reddy Poreddy
3

Die Benchmarks dort sind trivial. Das wiederholte Verketten derselben drei Elemente wird eingefügt, die Ergebnisse werden als deterministisch und gespeichert gespeichert, der Garbage Handler wird nur Array-Objekte (die so gut wie nichts in der Größe haben) wegwerfen und wahrscheinlich nur aufgrund von Nein vom Stapel gestoßen und geknallt externe Referenzen und weil sich die Zeichenfolgen nie ändern. Ich wäre beeindruckter, wenn der Test eine große Anzahl zufällig generierter Zeichenfolgen wäre. Wie bei ein oder zwei Konzerten.

Array.join FTW!

Jeremy Moritz
quelle
2

Ich würde sagen, dass es mit Strings einfacher ist, einen größeren Puffer vorab zuzuweisen. Jedes Element besteht nur aus 2 Bytes (wenn UNICODE). Selbst wenn Sie konservativ sind, können Sie der Zeichenfolge einen ziemlich großen Puffer zuweisen. Mit arraysjedem Element ist mehr „Komplex“, weil jedes Element ein ist Object, so dass eine konservative Umsetzung Raum für weniger Elemente preallocate wird.

Wenn Sie versuchen, for(j=0;j<1000;j++)vor jedem ein hinzuzufügen, werden forSie feststellen, dass (unter Chrom) der Geschwindigkeitsunterschied kleiner wird. Am Ende war es noch 1,5x für die String-Verkettung, aber kleiner als die 2,6, die vorher war.

UND wenn die Elemente kopiert werden müssen, ist ein Unicode-Zeichen wahrscheinlich kleiner als ein Verweis auf ein JS-Objekt.

Beachten Sie, dass es die Möglichkeit gibt, dass viele Implementierungen von JS-Engines eine Optimierung für Single-Type-Arrays haben, die alles, was ich geschrieben habe, unbrauchbar macht :-)

Xanatos
quelle
1

Dieser Test zeigt die Strafe für die tatsächliche Verwendung einer Zeichenfolge, die mit Zuordnungsverkettung erstellt wurde, im Vergleich zur Verwendung der Methode array.join. Die Gesamtzuweisungsgeschwindigkeit ist in Chrome v31 zwar immer noch doppelt so hoch, aber nicht mehr so ​​hoch wie bei Nichtverwendung der resultierenden Zeichenfolge.

srgstm
quelle
0

Dies hängt eindeutig von der Implementierung der Javascript-Engine ab. Selbst für verschiedene Versionen eines Motors können Sie signifikant unterschiedliche Ergebnisse erzielen. Sie sollten Ihren eigenen Benchmark durchführen, um dies zu überprüfen.

Ich würde sagen, dass dies String.concatin den letzten Versionen von V8 eine bessere Leistung bietet. Aber für Firefox und Opera Array.joinist ein Gewinner.

Vanuan
quelle
-1

Ich vermute, dass, während jede Version die Kosten vieler Verkettungen trägt, die Join-Versionen zusätzlich Arrays erstellen.

Marcelo Cantos
quelle