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

Question

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: Мне действительно интересно, как массивы 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 был использован ... не так уж и плохо.

Answer 1

ОБНОВЛЕНИЕ: Обратите внимание, что JSPref в настоящее время не работает

(я сохранил копию контрольного примера и обновлю ответ, как только JSPref будет исправлен или найден преемник)

---

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

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

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

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

Сводка следующая

• Массив V8 - это быстро, ОЧЕНЬ БЫСТРО
• 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] (не определено) в массиве примерно на 4x ++ быстрее.
• Удивительно, но обнуление значения в объекте на 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

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

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

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

Обновлено примечание (февраль 2013 г.): Thx @badunk, для предоставления видеосвязи в точной точке

Обновленная заметка (июнь 2016 г.): Thx @Benedikt, относительно разницы производительности push-массива в фиксированных / динамических массивах.

Answer 2

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

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

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

Всякий раз, когда вы используете допустимый объект массива и используете один из стандартных методов манипулирования этим массивом, вы попадете в базовые данные массива. В частности, в V8 они в основном совпадают с массивом C ++, поэтому эти правила будут применяться. Если по какой-то причине вы работаете с массивом, который механизм не может с уверенностью определить как массив, то вы находитесь на более шаткой почве. С последними версиями V8 есть больше возможностей для работы. Например, можно создать класс с Array.prototype в качестве 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;
}

Answer 3

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

Вы можете очень хорошо увидеть этот эффект, это из 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-го элемента), втораяэто сколько времени заняло (для многих массивов эталонный тест выполняется параллельно), а последним значением является деление первого числа на число, указанное в предыдущей строке.

Все строки, у которых меньшедля Chrome исключено время выполнения более 2 мс.

Вы можете видеть, что 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;
    }
}

Answer 4

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

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

Загрузка 91k записей в массив (с проверкой и отправкой) происходит быстрее, чем установка obj [ключ] = значение.

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

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

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