Dlaczego konkatenacja ciągów jest szybsza niż łączenie tablic?

Dziś przeczytałem ten wątek o szybkości konkatenacji ciągów.

O dziwo zwyciężyła konkatenacja ciągów:

http://jsben.ch/#/OJ3vo

Wynik był odwrotny od tego, co myślałem. Poza tym, istnieje wiele artykułów na ten temat, które wyjaśniają przeciwnie jak ten .

Domyślam się, że przeglądarki są zoptymalizowane pod kątem ciągów znaków concatw najnowszej wersji, ale jak to robią? Czy możemy powiedzieć, że lepiej jest używać +podczas łączenia ciągów?

Aktualizacja

Tak więc w nowoczesnych przeglądarkach konkatenacja ciągów jest zoptymalizowana, więc używanie +znaków jest szybsze niż używanie, joingdy chcesz połączyć ciągi.

Ale @Arthur wskazał, że joinjest to szybsze, jeśli faktycznie chcesz łączyć ciągi za pomocą separatora.

Aktualizacja - 2020
Chrome: tablica joinjest prawie 2 times fasterzgodna ze stringami + Zobacz: https://stackoverflow.com/a/54970240/984471

Uwaga:

• Tablica joinjest lepsza, jeśli maszlarge strings
• Jeśli potrzebujemy wygenerować several small stringsw końcowym wyniku, lepiej jest zastosować konkatację ciągów +, ponieważ w przeciwnym razie przejście z Array będzie wymagało kilku konwersji Array na String na końcu, co jest przeciążeniem wydajności.

Optymalizacje ciągów w przeglądarce zmieniły obraz konkatenacji ciągów.

Firefox był pierwszą przeglądarką, która zoptymalizowała konkatenację ciągów. Począwszy od wersji 1.0, technika tablicowa jest w rzeczywistości wolniejsza niż użycie operatora plus we wszystkich przypadkach. Inne przeglądarki również zoptymalizowały konkatenację ciągów, więc Safari, Opera, Chrome i Internet Explorer 8 również wykazują lepszą wydajność przy użyciu operatora plus. Internet Explorer przed wersją 8 nie miał takiej optymalizacji, więc technika tablicowa jest zawsze szybsza niż operator plus.

- Pisanie wydajnego JavaScript: Rozdział 7 - Jeszcze szybsze strony internetowe

Silnik javascript V8 (używany w Google Chrome) używa tego kodu do konkatenacji ciągów:

// 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, "");
}

Tak więc wewnętrznie optymalizują ją, tworząc tablicę InternalArray ( partszmienną), która jest następnie wypełniana. Funkcja StringBuilderConcat jest wywoływana z tymi częściami. Jest szybki, ponieważ funkcja StringBuilderConcat to mocno zoptymalizowany kod C ++. Jest za długo, aby cytować w tym miejscu, ale wyszukaj kod w pliku runtime.ccRUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat) .

Firefox jest szybki, ponieważ używa czegoś, co nazywa się Ropes ( Ropes: an Alternative to Strings ). Lina to po prostu DAG, w którym każdy węzeł jest sznurkiem.

Na przykład, gdybyś to zrobił a = 'abc'.concat('def'), nowo utworzony obiekt wyglądałby tak. Oczywiście nie tak to wygląda w pamięci, ponieważ nadal musisz mieć pole na typ, długość i być może inne.

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

I b = a.concat('123')

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

Tak więc w najprostszym przypadku maszyna wirtualna nie musi wykonywać prawie żadnej pracy. Jedynym problemem jest to, że spowalnia to nieco inne operacje na wynikowym ciągu. Oczywiście zmniejsza to również obciążenie pamięci.

Z drugiej strony ['abc', 'def'].join('')zwykle przydzielałby pamięć, aby rozłożyć nowy ciąg na płasko w pamięci. (Może to powinno zostać zoptymalizowane)

Wiem, że to stary wątek, ale twój test jest nieprawidłowy. Robisz, output += myarray[i];podczas gdy powinno być bardziej, output += "" + myarray[i];bo zapomniałeś, że musisz coś skleić razem. Kod concat powinien wyglądać mniej więcej tak:

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

W ten sposób wykonujesz dwie operacje zamiast jednej z powodu sklejania elementów ze sobą.

Array.join() jest szybszy.

W przypadku dużej ilości danych łączenie jest szybsze, więc pytanie jest sformułowane nieprawidłowo.

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));

Przetestowano na Chrome 72.0.3626.119, Firefox 65.0.1, Edge 42.17134.1.0. Zwróć uwagę, że jest to szybsze nawet przy dołączonym tworzeniu macierzy!

Tam wzorce są trywialne. Wielokrotne łączenie tych samych trzech elementów zostanie wstawione, wyniki okażą się deterministyczne i zapamiętane, program do obsługi śmieci po prostu wyrzuci obiekty tablicowe (które będą prawie zerowe) i prawdopodobnie po prostu wypchną i wyskoczą ze stosu z powodu braku odniesienia zewnętrzne i ponieważ ciągi znaków nigdy się nie zmieniają. Byłbym pod większym wrażeniem, gdyby test obejmował dużą liczbę losowo generowanych ciągów. Jak na koncercie lub dwóch strunach.

Array.join FTW!

Powiedziałbym, że w przypadku łańcuchów łatwiej jest wstępnie przydzielić większy bufor. Każdy element ma tylko 2 bajty (jeśli jest UNICODE), więc nawet jeśli jesteś konserwatywny, możesz wstępnie przydzielić całkiem duży bufor dla ciągu. Z arrayskażdego elementu jest bardziej „złożone”, ponieważ każdy element jest Objecttak konserwatywny realizacja przydzielenia miejsca dla mniejszych elementów.

Jeśli spróbujesz dodać for(j=0;j<1000;j++)przed każdym for, zobaczysz, że (pod chromem) różnica w prędkości zmniejszy się. Ostatecznie było to nadal 1,5x dla konkatenacji ciągów, ale mniejsze niż 2,6, które było wcześniej.

ORAZ konieczność skopiowania elementów, znak Unicode jest prawdopodobnie mniejszy niż odniesienie do obiektu JS.

Należy pamiętać, że istnieje możliwość, że wiele implementacji silników JS ma optymalizację dla tablic jednego typu, która sprawiłaby, że wszystko, co napisałem, byłoby bezużyteczne :-)

Ten test pokazuje karę za faktyczne użycie łańcucha utworzonego za pomocą konkatenacji przypisań w porównaniu z utworzonym metodą array.join. Podczas gdy ogólna prędkość przypisywania jest nadal dwa razy większa w Chrome v31, ale nie jest już tak duża, jak wtedy, gdy nie używasz wynikowego ciągu.

Zależy to oczywiście od implementacji silnika javascript. Nawet w przypadku różnych wersji jednego silnika można uzyskać znacząco różne wyniki. Powinieneś zrobić własny test porównawczy, aby to zweryfikować.

Powiedziałbym, że String.concatma lepszą wydajność w ostatnich wersjach V8. Ale dla Firefoksa i Opery Array.joinjest zwycięzcą.

Domyślam się, że podczas gdy każda wersja ma koszt wielu konkatenacji, wersje złączeń oprócz tego budują tablice.