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

Ответ 1

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

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

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

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

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

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

Сводка как следует

• Массив V8 работает быстро, ОЧЕНЬ FAST
• Массив push/pop/shift ~ примерно на 20x + быстрее, чем любой эквивалент объекта.
• Удивительно Array.shift() быстро ~ примерно на 6 раз медленнее, чем массив, но примерно на 100 раз быстрее, чем удаление атрибута объекта.
• Интересно, что Array.push( data ); быстрее, чем Array[nextIndex] = data, почти 20 (динамический массив) до 10 (фиксированный массив) раз.
• Array.unshift(data) медленнее, как ожидалось, и ~ примерно на 5 раз медленнее, чем добавление нового свойства.
• Отбрасывание значения array[index] = null быстрее, чем удаление его delete array[index] (undefined) в массиве примерно на ~ 4x ++ быстрее.
• Удивительно Отбрасывание значения в объекте obj[attr] = null ~ примерно 2x медленнее, чем просто удаление атрибута 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. Кроме того, тест огромен, поэтому я еще не полностью проанализировал и оценил результаты: отредактируйте его в =)

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

Обновленное примечание (feb 2013): спасибо @badunk, для обеспечения видеосвязи в точном месте

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

• search config занял 87,56 секунды (массив)
• search config занял 0.21 секунды (объект)

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

Ответ 4

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

Вы можете увидеть этот эффект очень красиво, это от 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

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

Итак, первое число представляет, какой элемент был вставлен (первая строка для 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;
    }
}