Какова производительность объектов / массивов в JavaScript? (специально для Google V8)

Было бы очень интересно задокументировать производительность, связанную с массивами и объектами в JavaScript (особенно Google V8). Я нигде в Интернете не нашел исчерпывающей статьи по этой теме.

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

Я также понимаю, что с массивами иногда обращаются как с массивами C ++ (т.е. быстрая случайная индексация, медленное удаление и изменение размера). А в других случаях они больше похожи на объекты (быстрая индексация, быстрая вставка / удаление, больше памяти). И, возможно, иногда они хранятся в виде связанных списков (т.е. медленная случайная индексация, быстрое удаление / вставка в начале / конце)

Какова точная производительность извлечения массивов / объектов и манипуляций с ними в JavaScript? (специально для Google V8)

В частности, каково влияние на производительность:

• Добавление свойства к объекту
• Удаление свойства из объекта
• Индексирование свойства в объекте
• Добавление элемента в массив
• Удаление элемента из массива
• Индексирование элемента в массиве
• Вызов Array.pop ()
• Вызов Array.push ()
• Вызов Array.shift ()
• Вызов Array.unshift ()
• Вызов Array.slice ()

Также приветствуются любые статьи или ссылки для получения более подробной информации. :)

EDIT: мне действительно интересно, как массивы и объекты JavaScript работают под капотом. Кроме того, в каком контексте движок V8 «знает» о «переключении» на другую структуру данных?

Например, предположим, что я создаю массив с ...

var arr = [];
arr[10000000] = 20;
arr.push(21);

Что здесь на самом деле происходит?

Или ... что с этим ... ???

var arr = [];
//Add lots of items
for(var i = 0; i < 1000000; i++)
    arr[i] = Math.random();
//Now I use it like a queue...
for(var i = 0; i < arr.length; i++)
{
    var item = arr[i].shift();
    //Do something with item...
}

Для обычных массивов производительность была бы ужасной; тогда как, если использовался LinkedList ... не так уж и плохо.

Я создал набор тестов именно для изучения этих (и других) проблем ( архивная копия ).

И в этом смысле вы можете увидеть проблемы с производительностью в этом тестере из более чем 50 тестовых случаев (это займет много времени).

Кроме того, как следует из названия, в нем исследуется использование природы связанного списка структуры DOM.

(В настоящее время не работает, перестраивается) Подробнее об этом в моем блоге .

Резюме следующее

• V8 Array работает быстро, очень быстро
• Массив push / pop / shift примерно в 20 раз быстрее, чем любой эквивалент объекта.
• На удивление Array.shift()быстро ~ примерно в 6 раз медленнее, чем извлечение массива, но примерно в 100 раз быстрее, чем удаление атрибута объекта.
• Забавно, Array.push( data );это быстрее, чем Array[nextIndex] = dataпочти в 20 (динамический массив) в 10 (фиксированный массив) раз.
• Array.unshift(data) работает медленнее, чем ожидалось, и примерно в 5 раз медленнее, чем добавление нового свойства.
• Обнуление значения array[index] = nullпроисходит быстрее, чем его удаление delete array[index](undefined) в массиве примерно на 4 ++ быстрее.
• Удивительно, но обнуление значения в объекте obj[attr] = nullпримерно в 2 раза медленнее, чем просто удаление атрибута.delete obj[attr]
• Неудивительно, что средний массив Array.splice(index,0,data)медленный, очень медленный.
• Удивительно, Array.splice(index,1,data)но оптимизирован (без изменения длины) и в 100 раз быстрее, чем просто сращиваниеArray.splice(index,0,data)
• неудивительно, что divLinkedList уступает массиву по всем секторам, кроме dll.splice(index,1)удаления (где он сломал тестовую систему).
• САМЫЙ БОЛЬШОЙ СЮРПРИЗ всего этого [в jjrv указывала], пишет массив V8 немного быстрее , чем V8 читает = O

Примечание. Эти показатели применимы только к большим массивам / объектам, которые в версии 8 не «полностью оптимизированы». Могут быть очень изолированные случаи оптимальной производительности для размера массива / объекта меньше произвольного размера (24?). Более подробную информацию можно найти в нескольких видеороликах Google IO.

Примечание 2: эти замечательные результаты производительности не используются в разных браузерах, особенно в *cough*IE. Также тест огромен, поэтому мне еще предстоит полностью проанализировать и оценить результаты: отредактируйте его в =)

Обновленное примечание (декабрь 2012 г.): у представителей Google есть видеоролики на YouTube, в которых описывается внутренняя работа самого Chrome (например, когда он переключается с массива связанных списков на фиксированный массив и т. Д.), А также способы их оптимизации. См. GDC 2012: От консоли к Chrome для получения дополнительной информации.

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

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

Свойства могут быть сохранены в объекте массива, но это просто демонстрирует, как JavaScript настаивает на превращении всего объекта в объект. Индексированные значения в массиве хранятся иначе, чем любые свойства, которые вы решите установить для объекта массива, представляющего базовые данные массива.

Всякий раз, когда вы используете законный объект массива и используете один из стандартных методов манипулирования этим массивом, вы будете обращаться к базовым данным массива. В частности, в V8 они по сути такие же, как массив C ++, поэтому будут применяться эти правила. Если по какой-то причине вы работаете с массивом, который движок не может с уверенностью определить как массив, то ваша почва гораздо шатче. Однако с последними версиями V8 есть больше возможностей для работы. Например, можно создать класс, прототипом которого является Array.prototype, и при этом получить эффективный доступ к различным методам работы с собственными массивами. Но это недавнее изменение.

Здесь могут пригодиться конкретные ссылки на недавние изменения в работе с массивами:

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

В качестве дополнительной информации, здесь Array Pop и Array Push непосредственно из источника V8, оба реализованы в самом JS:

function ArrayPop() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.pop"]);
  }

  var n = TO_UINT32(this.length);
  if (n == 0) {
    this.length = n;
    return;
  }
  n--;
  var value = this[n];
  this.length = n;
  delete this[n];
  return value;
}


function ArrayPush() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.push"]);
  }

  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
}

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

Вы можете очень хорошо увидеть этот эффект, это из Chrome:

16: 4ms
40: 8ms 2.5
76: 20ms 1.9
130: 31ms 1.7105263157894737
211: 14ms 1.623076923076923
332: 55ms 1.5734597156398105
514: 44ms 1.5481927710843373
787: 61ms 1.5311284046692606
1196: 138ms 1.5196950444726811
1810: 139ms 1.5133779264214047
2731: 299ms 1.5088397790055248
4112: 341ms 1.5056755767118273
6184: 681ms 1.5038910505836576
9292: 1324ms 1.5025873221216042

Несмотря на то, что каждое нажатие профилировано, выходные данные содержат только те, для которых время превышает определенный порог. Для каждого теста я настроил порог, чтобы исключить все толчки, которые, кажется, представляют собой быстрые толчки.

Таким образом, первое число представляет, какой элемент был вставлен (первая строка - для 17-го элемента), второе - сколько времени это заняло (для многих массивов эталонный тест выполняется параллельно), а последнее значение - это деление элемента первый номер по номеру в предыдущей строке.

Все строки с временем выполнения менее 2 мс исключаются для Chrome.

Вы можете видеть, что Chrome увеличивает размер массива в 1,5 раза, плюс некоторое смещение для учета небольших массивов.

Для Firefox это степень двойки:

126: 284ms
254: 65ms 2.015873015873016
510: 28ms 2.0078740157480315
1022: 58ms 2.003921568627451
2046: 89ms 2.0019569471624266
4094: 191ms 2.0009775171065494
8190: 364ms 2.0004885197850513

Мне пришлось немного поднять порог в Firefox, поэтому мы начинаем с # 126.

С IE мы получаем смесь:

256: 11ms 256
512: 26ms 2
1024: 77ms 2
1708: 113ms 1.66796875
2848: 154ms 1.6674473067915691
4748: 423ms 1.6671348314606742
7916: 944ms 1.6672283066554338

Сначала это степень двойки, а затем она переходит в степень пяти третей.

Итак, все распространенные реализации используют «нормальный» способ работы с массивами (например, вместо того, чтобы сходить с ума по веревкам ).

Вот код теста, а вот скрипка, в которой он находится.

var arrayCount = 10000;

var dynamicArrays = [];

for(var j=0;j<arrayCount;j++)
    dynamicArrays[j] = [];

var lastLongI = 1;

for(var i=0;i<10000;i++)
{
    var before = Date.now();
    for(var j=0;j<arrayCount;j++)
        dynamicArrays[j][i] = i;
    var span = Date.now() - before;
    if (span > 10)
    {
      console.log(i + ": " + span + "ms" + " " + (i / lastLongI));
      lastLongI = i;
    }
}

При работе под node.js 0.10 (построенной на v8) я наблюдал использование ЦП, которое казалось чрезмерным для рабочей нагрузки. Я проследил одну проблему производительности до функции, которая проверяла наличие строки в массиве. Итак, я провел несколько тестов.

• загружено 90 822 хоста
• загрузка конфигурации заняла 0,087 секунды (массив)
• загрузка конфигурации заняла 0,152 секунды (объект)

Загрузка 91 тыс. Записей в массив (с помощью проверки и нажатия) выполняется быстрее, чем установка obj [key] = value.

В следующем тесте я просмотрел каждое имя хоста в списке один раз (91 тыс. Итераций, чтобы усреднить время поиска):

• поиск конфигурации занял 87,56 секунды (массив)
• поиск конфигурации занял 0,21 секунды (объект)

Здесь используется приложение Haraka (SMTP-сервер), которое загружает host_list один раз при запуске (и после изменений), а затем выполняет этот поиск миллионы раз во время работы. Переключение на объект было огромным выигрышем в производительности.