Почему конкатенация строк быстрее, чем объединение массива?

Ответ 1

Оптимизация строки браузера изменила изображение конкатенации строк.

Firefox стал первым браузером для оптимизации конкатенации строк. Начиная с версии 1.0, техника массивов на самом деле медленнее, чем использование оператора "плюс" во всех случаях. Другие браузеры также оптимизировали конкатенацию строк, поэтому Safari, Opera, Chrome и Internet Explorer 8 также показывают лучшую производительность с помощью оператора plus. Internet Explorer до версии 8 не имел такой оптимизации, поэтому техника массива всегда быстрее, чем оператор плюс.

- Написание эффективного JavaScript: Глава 7 - Даже более быстрые веб-сайты

В javascript-движке V8 (используемом в Google Chrome) используется этот код для выполнения конкатенации строк:

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

Таким образом, внутренне они оптимизируют его, создавая InternalArray (переменную parts), которая затем заполняется. Вызывается функция StringBuilderConcat с этими частями. Это быстро, потому что функция StringBuilderConcat - это сильно оптимизированный код на С++. Это слишком долго, чтобы процитировать здесь, но найдите в runtime.cc файл для RUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat), чтобы увидеть код.

Ответ 2

Firefox работает быстро, потому что использует нечто вроде Ropes (Веревки: альтернатива струнам). Канат - это просто DAG, где каждая Node является строкой.

Так, например, если бы вы сделали a = 'abc'.concat('def'), вновь созданный объект выглядел бы так. Конечно, это не совсем так, как это выглядит в памяти, потому что вам все равно нужно иметь поле для типа строки, длины и, возможно, другого.

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

И b = a.concat('123')

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

Итак, в простейшем случае виртуальная машина должна почти не работать. Единственная проблема заключается в том, что это немного замедляет другие операции над результирующей строкой. Кроме того, это, конечно, уменьшает издержки памяти.

С другой стороны, ['abc', 'def'].join('') обычно просто выделяет память для размещения новой строки в памяти. (Возможно, это должно быть оптимизировано)

Ответ 3

Тесты там тривиальны. Конкатенация тех же трех элементов будет повторяться, результаты будут проверены детерминированными и мемуаризованными, обработчик мусора будет просто отбрасывать объекты массива (который будет почти ничего не по размеру) и, вероятно, просто вытолкнул и выскочил из стека из-за отсутствия внешние ссылки и потому, что строки никогда не меняются. Я был бы более впечатлен, если бы тест состоял из большого количества случайно сгенерированных строк. Так же, как в строке или две строки.

Array.join FTW!

Ответ 4

Я бы сказал, что с помощью строк проще предусмотреть более высокий буфер. Каждый элемент имеет всего 2 байта (если UNICODE), поэтому даже если вы консервативны, вы можете предварительно распределить довольно большой буфер для строки. С arrays каждый элемент более "сложный", потому что каждый элемент является Object, поэтому консервативная реализация будет предубирать пространство для меньших элементов.

Если вы попытаетесь добавить for(j=0;j<1000;j++) перед каждым for, вы увидите, что (под хром) разница в скорости становится меньше. В конце концов это было 1,5x для конкатенации строк, но меньше, чем предыдущий.

И, чтобы скопировать элементы, символ Юникода, вероятно, меньше, чем ссылка на объект JS.

Помните, что существует вероятность того, что во многих реализациях JS-движков есть оптимизация для массивов однотипных типов, которые сделают все, что я написал бесполезно: -)

Ответ 5

Этот тест показывает штраф за фактическое использование строки, созданной с помощью конкатенации присваивания, с помощью метода array.join. Хотя общая скорость присваивания в Chrome v31 по-прежнему вдвое быстрее, но она больше не такая огромная, как при отсутствии результирующей строки.

Ответ 6

Это явно зависит от реализации javascript-движка. Даже для разных версий одного двигателя вы можете получить существенно разные результаты. Вы должны сделать свой собственный тест, чтобы проверить это.

Я бы сказал, что String.concat имеет лучшую производительность в последних версиях V8. Но для Firefox и Opera победитель Array.join.

Ответ 7

Моя догадка заключается в том, что, хотя каждая версия носит стоимость многих конкатенаций, версии соединений также строят массивы.