Почему array.push иногда быстрее, чем array[n] = value?

Question

В качестве побочного результата тестирования некоторого кода я написал небольшую функцию для сравнения скорости использования метода array.push с прямой адресацией (array[n] = value). К моему удивлению, метод push часто оказывался быстрее, особенно в Firefox, а иногда и в Chrome. Просто из любопытства: у кого-нибудь есть объяснение этому? Вы можете найти тест на этой странице (нажмите "Сравнение методов массива")

Answer 1

В игру вступают все виды факторов, в большинстве реализаций JS используется плоский массив, который преобразуется в разреженную память, если в дальнейшем это становится необходимым.

По сути, решение стать разреженным является эвристическим, основанным на том, какие элементы устанавливаются, и сколько места будет потрачено впустую, чтобы оставаться плоским.

В вашем случае вы устанавливаете последний элемент первым, что означает, что движок JS увидит массив, который должен иметь длину n но только один элемент. Если n достаточно большой, это немедленно сделает массив разреженным массивом - в большинстве движков это означает, что все последующие вставки будут использовать случай медленного разреженного массива.

Вы должны добавить дополнительный тест, в котором вы заполняете массив от индекса 0 до индекса n-1 - это должно быть намного, намного быстрее.

В ответ на @Christoph и из-за желания прокрастинировать, вот описание того, как массивы (как правило) реализуются в JS - специфика варьируется от движка JS к движку JS, но общий принцип тот же.

Все JS Objects (поэтому не строки, числа, правда, ложь, undefined, или же null) наследовать от базового типа объекта - точная реализация может быть разной, это может быть наследование C++ или вручную в C (есть преимущества в любом случае) - базовый тип Object определяет методы доступа к свойству по умолчанию, например.

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

Этот тип Object обрабатывает всю стандартную логику доступа к свойствам, цепочку прототипов и т. Д. Затем реализация Array становится

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
}

Теперь, когда вы создаете массив в JS, движок создает нечто похожее на приведенную выше структуру данных. Когда вы вставляете объект в экземпляр Array, метод put массива проверяет, является ли имя свойства целым числом (или его можно преобразовать в целое число, например, "121", "2341" и т. Д.) В диапазоне от 0 до 2^32. -1 (или, возможно, 2^31-1, я точно забыл). Если это не так, то метод put перенаправляется в реализацию базового объекта, и стандартная логика [[Put]] выполняется. В противном случае значение помещается в собственное хранилище массива, если данные достаточно компактны, то движок будет использовать хранилище плоского массива, в этом случае вставка (и извлечение) является просто стандартной операцией индексации массива, в противном случае движок преобразует массив Разбавить хранилище и положить / получить использовать карту, чтобы перейти от propertyName к значению location.

Я, честно говоря, не уверен, что какой-либо движок JS в настоящее время преобразует из разреженного в плоское хранилище после этого преобразования.

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

Незначительный дополнительный пункт, в то время как спецификация ES относится к propertyName как строковые движки JS, как правило, специализируются на целочисленных поисках, так someObject[someInteger] не будет преобразовывать целое число в строку, если вы смотрите на объект, который имеет целочисленные свойства, например. Типы Array, String и DOM (NodeListи т. д.).

Answer 2

Вот результат, который я получаю с вашим тестом

на сафари:

• Array.push (n) 1 000 000 значений: 0,124 с
• Массив [n .. 0] = значение (по убыванию) 1 000 000 значений: 3,669 с
• Массив [0 .. n] = значение (по возрастанию) 1 000 000 значений: 0,073 с

на FireFox:

• Array.push (n) 1 000 000 значений: 0,075 с
• Массив [n .. 0] = значение (по убыванию) 1 000 000 значений: 1,193 с
• Массив [0 .. n] = значение (по возрастанию) 1 000 000 значений: 0,055 с

на IE7:

• Array.push (n) 1 000 000 значений: 2,828 с
• Массив [n .. 0] = значение (по убыванию) 1 000 000 значений: 1,141 с
• Массив [0 .. n] = значение (по возрастанию) 1 000 000 значений: 7,984 с

Согласно вашему тесту метод push выглядит лучше в IE7 (огромная разница), и, поскольку в других браузерах разница невелика, метод push действительно лучший способ добавить элемент в массив.

Но я создал еще один простой тестовый сценарий, чтобы проверить, какой метод позволяет быстро добавлять значения в массив, результаты меня очень удивили, использование Array.length кажется намного быстрее по сравнению с использованием Array.push, поэтому я действительно не знаю, что говорить или думать больше, я не знаю.

Кстати, на моем IE7 ваш сценарий останавливается, и браузеры спрашивают меня, хочу ли я разрешить ему продолжить (вы знаете типичное сообщение IE, которое говорит: "Прекратить выполнение этого сценария? ..."). Я бы рекомендовал немного уменьшить количество циклов,

Answer 3

push() является частным случаем более общего [[Put]] и поэтому может быть дополнительно оптимизирован:

При вызове [[Put]] для объекта массива аргумент должен быть сначала преобразован в целое число без знака, потому что все имена свойств, включая индексы массива, являются строками. Затем его необходимо сравнить со свойством длины массива, чтобы определить, нужно ли увеличивать длину. При нажатии не нужно выполнять такое преобразование или сравнение: просто используйте текущую длину в качестве индекса массива и увеличьте ее.

Конечно, есть другие вещи, которые будут влиять на время выполнения, например, вызов push() должен быть медленнее, чем вызов [[Put]] через [] потому что цепь прототипа должна быть проверена на первое.

---

Как отметил olliej: фактическая реализация ECMAScript оптимизирует преобразование, т. Е. Для числовых имен свойств не выполняется преобразование из строки в uint, а просто проверяется тип. Базовое допущение должно сохраниться, хотя его влияние будет меньше, чем я предполагал изначально.

Answer 4

Вот хороший тестовый стенд, который подтверждает, что прямое назначение значительно быстрее, чем push: http://jsperf.com/array-direct-assignment-vs-push.

Редактировать: кажется, что есть некоторая проблема с отображением совокупных результатов, но, надеюсь, это будет исправлено в ближайшее время.

Answer 5

array[n] = value (при подъеме) всегда быстрее, чем array.push если массив в первом случае инициализируется длиной.

Изучив исходный код javascript вашей страницы, вашArray[0 .. n] = value (ascending) test не инициализирует массив заранее длиной.

Так Array.push(n) иногда выходит вперед при первом запуске, но при последующих запусках вашего теста тогда Array[0 .. n] = value (ascending) на самом деле стабильно работает лучше всего (как в Safari, так и в Chrome).

Если код модифицирован таким образом, что он заранее инициализирует массив с длиной, например var array = new Array(n) тогда Array[0 .. n] = value (ascending) показывает, что array[n] = value выполняет в 4,5–9 раз быстрее, чем Array.push(n) в моем рудиментарном запуске этого конкретного тестового кода.

Это согласуется с другими тестами, такими как @Timo Kähkönen. См. Конкретно эту версию упомянутого теста: https://jsperf.com/push-method-vs-setting-via-key/10

Модифицированный код, поэтому вы можете увидеть, как я его отредактировал и справедливо инициализировал массив (без необходимости инициализировать его длиной для тестового примера array.push):

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

Answer 6

Push добавляет его в конец, в то время как массив [n] должен пройти через массив, чтобы найти правильное место. Вероятно, зависит от браузера и способа обработки массивов.