Сорта элементов (element kinds) в движке V8

2020-11-20
ru
by Mathias Bynens
habr

В качестве имени свойства JavaScript-объекта может выступать произвольная строка. Но для некоторых особенных подмножеств имен имеет смысл делать специальные оптимизации в JavaScript-движках. Одним из таких случаев являются числовые индексы массивов.

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

Основные сорта элементов

Во время исполнения JavaScript-кода, V8 отслеживает сорт элементов каждого массива — то, какие именно элементы он хранит. Эта информация позволяет движку лучше оптимизировать операции над массивами. К примеру, встроенные функции вроде map, reduce или forEach специализированы для каждого сорта элементов.

Рассмотрим, к примеру, такой массив:

const array = [1, 2, 3];

Какие элементы в нем содержатся? С точки зрения оператора typeof все просто — это элементы типа number. И это все, что можно о них сказать изнутри JavaScript: язык не различает int, float и double. Тем не менее, на уровне движка различия есть. Сорт элементов этого массива — PACKED_SMI_ELEMENTS. В терминах V8, SMI — особый формат хранения небольших целых чисел (small integers). Что означает PACKED, мы рассмотрим чуть позже.

Добавление к массиву дробного числа приводит его элементы к более общему сорту:

const array = [1, 2, 3];
// сорт элементов: PACKED_SMI_ELEMENTS
array.push(4.56);
// сорт элементов: PACKED_DOUBLE_ELEMENTS

Добавление туда же строки делает сорт элементов еще более общим:

const array = [1, 2, 3];
// сорт элементов: PACKED_SMI_ELEMENTS
array.push(4.56);
// сорт элементов: PACKED_DOUBLE_ELEMENTS
array.push("x");
// сорт элементов: PACKED_ELEMENTS

В этом коде представлены три основных сорта элементов:

SMI_ELEMENTS — для небольших целых чисел
DOUBLE_ELEMENTS — для чисел с плавающей точкой и целых, слишком больших для SMI
ELEMENTS — для произвольных значений, которые не могут быть представлены как SMI или DOUBLE

Важно заметить, что преобразования элементов всегда осуществляются только в сторону более общих сортов. К примеру, массив с элементами сорта PACKED_ELEMENTS никогда больше не станет массивом PACKED_DOUBLE_ELEMENTS.

Подведем итог:

Движок V8 назначает каждому массиву определенный сорт элементов.
Сорт элементов массива — не константа, он может меняться в рантайме.
Сорт элементов может меняться только на более общий.

Сорта `PACKED` и `HOLEY`

Пока что мы рассмотрели только случаи плотных (dense), или упакованных (packed), массивов. Создание в массиве "дырок" (к примеру, удаление элемента из середины) преобразует массив в разреженный (sparse), или "дырявый" (holey):

const array = [1, 2, 3, 4.56, "x"];
// сорт элементов: PACKED_ELEMENTS
array.length; // 5
array[9] = 1; // от array[5] до array[9] теперь дырки
// сорт элементов: HOLEY_ELEMENTS

Движок V8 оптимизирует работу с плотными массивами более агрессивно, чем с разреженными. Те операции, что выполняются эффективно для плотных массивов, требуют прохода по цепочке прототипов для разреженных.

Каждый из основных сортов элементов (SMI_ELEMENTS, DOUBLE_ELEMENTS и обычные ELEMENTS) могут быть как упакованными (PACKED), так и дырявыми (HOLEY), причем второй считается более общим сортом. Таким образом, PACKED_SMI_ELEMENTS могут быть преобразованы как в PACKED_DOUBLE_ELEMENTS, так и в HOLEY_SMI_ELEMENTS.

Подытожим:

Все основные сорта элементов могут быть как плотными (PACKED), так и дырявыми (HOLEY).
Работать с плотными элементами быстрее, чем с дырявыми.
Элементы могут быть преобразованы из PACKED-сорта в соответствующий HOLEY-сорт (но не наоборот).

Решетка сортов элементов

Правила преобразования сортов элементов движка V8 могут быть представлены в виде решетки. Часть этой решетки может быть изображена так:

решетка сортов элементов

По решетке можно перемещаться исключительно вдоль стрелок. Как только в массив небольших целых добавляется дробное число, этот массив отмечается как DOUBLE. Если перезаписать дробный элемент целым, массив все еще останется отмечен как DOUBLE. Аналогично, массив, когда-то отмеченный как HOLEY, никогда не сможет стать PACKED.

На данный момент, в V8 определено 29 сортов элементов (на момент выхода статьи их было 22 — прим. пер.). Для каждого из них доступны свои оптимизации.

Говоря грубо, более конкретные сорта оптимизируются лучше, чем более общие. Чем дальше сорт элементов в решетке, тем медленнее с ними работать. Для оптимизации производительности следует избегать преобразований элементов к более общим сортам.

Советы по оптимизации производительности

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

Избегайте чтения элементов дальше длины массива

Честно говоря, этот совет не относится к сортам элементов напрямую, но механика его работы довольно схожа. Чтение элементов по индексам, превосходящим длину массива, может ощутимо сказаться на производительности. К примеру, допустим, что мы читаем array[42], хотя array.length === 5. В этом случае индекса 42 нет в самом массиве, и движок вынужден проходить по цепочке его прототипов, чтобы искать этот индекс в них. Более того, движок V8 запоминает, что в этом коде может случиться промах мимо массива, и этот код уже никогда не будет оптимизирован так хорошо, как мог бы.

В частности, избегайте циклов вида:

for (let i = 0, item; (item = items[i]) != null; i++) {
  doSomething(item);
}

Этот код всегда обращается к элементу items[items.length], который находится за пределами массива.

Вместо этого паттерна следует использовать обычные циклы со счетчиком:

for (let index = 0; index < items.length; index++) {
  const item = items[index];
  doSomething(item);
}

В случае, если items — iterable-коллекция (к примеру, массив), лучше использовать цикл for-of:

for (const item of items) {
  doSomething(item);
}

Конкретно для массивов доступен также метод forEach:

items.forEach((item) => {
  doSomething(item);
});

На сегодняшний день, for-of и forEach по скорости сравнимы с обычным циклом for.

Еще хуже то, что чтение несуществующего элемента может негативно сказаться на производительности последующего кода! К примеру:

function maximum(array) {
  let max = 0;
  for (let i = 0; i <= array.length; i++) {
    // опечатка в сравнении
    if (array[i] > max) max = array[i];
  }
  return max;
}

Данный код читает несуществующий элемент array[array.length], что не только медленно само по себе, но еще и замедляет последующее сравнение: вместо того, чтобы соптимизировать его как сравнение чисел, движок V8 должен учитывать случай с undefined. Такое полиморфное сравнение может быть в шесть раз медленнее, чем сравнение чисел.

Избегайте преобразований сортов элементов

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

Это не всегда так просто, как кажется. К примеру, добавление -0 к массиву небольших целых преобразует его элементы в сорт PACKED_DOUBLE_ELEMENTS.

const array = [3, 2, 1, +0];
// PACKED_SMI_ELEMENTS
array.push(-0);
// PACKED_DOUBLE_ELEMENTS

В результате, все последующие операции над этим массивом будут оптимизированы хуже, чем могли бы.

Избегайте значения -0, если вам не нужно явно различать -0 и +0 (что, скорее всего, не так).

Аналогичный совет применим к значениям NaN и Infinity. Они представлены как числа с плавающей точкой, что значит, что добавление их в массив SMI_ELEMENTS превращает их в DOUBLE_ELEMENTS.

const array = [3, 2, 1];
// PACKED_SMI_ELEMENTS
array.push(NaN, Infinity);
// PACKED_DOUBLE_ELEMENTS

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

Более того, если вам необходимы именно массивы чисел, стоит использовать типизированные массивы. Для них определены особые сорта элементов.

Используйте массивы вместо array-like objects

В JavaScript, некоторые объекты — в первую очередь, из DOM API — выглядят как массивы, но таковыми не являются. Такой "похожий на массив" (array-like) объект нетрудно создать самому:

const arrayLike = {};
arrayLike[0] = "a";
arrayLike[1] = "b";
arrayLike[2] = "c";
arrayLike.length = 3;

У этого объекта есть свойство length. К нему можно обращаться по индексу. На нем даже будут работать методы массивов:

Array.prototype.forEach.call(arrayLike, (value, index) => {
  console.log(`${index}: ${value}`);
});
// Вывод: '0: a', '1: b', '2: c'.

Но такой вызов forEach будет намного медленнее, чем для настоящего массива. Поэтому, в случае, если с array-like объектом нужно сделать что-то сложнее однократного использования, стоит преобразовать его в настоящий массив:

const actualArray = Array.prototype.slice.call(arrayLike, 0);
actualArray.forEach((value, index) => {
  console.log(`${index}: ${value}`);
});
// Вывод: '0: a', '1: b', '2: c'.

Такое однократное преобразование может привести к заметному ускорению дальнейшей обработки массива.

К примеру, объект arguments — это не настоящий массив. На нем можно вызывать методы массивов, но они не будут оптимизированы так же хорошо, как для настоящего массива:

const logArgs = function () {
  Array.prototype.forEach.call(arguments, (value, index) => {
    console.log(`${index}: ${value}`);
  });
};
logArgs("a", "b", "c");
// Вывод: '0: a', '1: b', '2: c'.

Вместо arguments следует использовать rest parameters, доступные, начиная с ECMAScript 2015. Они являются настоящими массивами, и к тому же выглядят более читаемо.

function logArgs(...args) {
  args.forEach((value, index) => {
    console.log(`${index}: ${value}`);
  });
}
logArgs("a", "b", "c");
// Вывод: '0: a', '1: b', '2: c'.

На сегодняшний день нет причин использовать объект arguments.

В целом, следует избегать использования array-like объектов, заменяя их настоящими массивами.

Избегайте полиморфизма

Код, работающий с несколькими сортами элементов, будет использовать полиморфные операции, что замедлит код. Рассмотрим в качестве примера гипотетическую библиотечную функцию для работы с массивами:

const each = (array, callback) => {
  for (let index = 0; index < array.length; ++index) {
    const item = array[index];
    callback(item);
  }
};
const doSomething = (item) => console.log(item);

each([], () => {});

each(["a", "b", "c"], doSomething);
// `each` вызывается для массива с сортом элементов `PACKED_ELEMENTS`.
// Движок V8 запоминает в inline-кэше (inline cache, IC), что `each`
// была вызвана именно с этим сортом элементов. V8 оптимизирует
// оптимистично, поэтому он предполагает, что выражения `array.length`
// и `array[index]` мономорфны - работают только с одним сортом элементов,
// до тех пор, пока не попадется массив с другим. При каждом последующем
// вызове `each` движок проверяет сорт элементов массива. Если это сорт
// `PACKED_ELEMENTS`, то V8 переиспользует сгенерированный код. Если нет,
// необходима деоптимизация.

each([1.1, 2.2, 3.3], doSomething);
// `each` вызывается для массива с сортом элементов `PACKED_DOUBLE_ELEMENTS`.
// Из-за того, что теперь V8 увидел вызовы `each` с разными сортами,
// выражения `array.length` и `array[index]` отмечаются как полиморфные.
// Теперь движку приходится при каждом вызове проверять сорт элементов
// массива, что влечет за собой падение производительности.

each([1, 2, 3], doSomething);
// `each` вызывается для массива с сортом элементов `PACKED_SMI_ELEMENTS`.
// Это влечет за собой появление еще одной проверки при вызове `each`,
// что замедляет код еще больше.

Встроенные методы вроде Array.prototype.forEach справляются с полиморфизмом намного лучше, поэтому в местах, где производительность критична, стоит использовать их вместо сторонних библиотек.

Еще один хороший пример того, как полиморфизм влияет на производительность V8, можно увидеть в статье Вячеслава Егорова про скрытые классы объектов.

Избегайте разреженных массивов

Для большинства реального кода нет заметной разницы в производительности между плотными и разреженными массивами. Но если вам важно выжать последние капли скорости из движка V8, стоит пытаться избегать разреженных массивов. К примеру, давайте зададим массив:

const array = new Array(3);
// Сейчас массив разреженный, поэтому он отмечается сортом
// `HOLEY_SMI_ELEMENTS`, то есть, наиболее узким сортом
// разреженных массивов

array[0] = "a";
// Постойте, это не целое число, это строка!
// Массив отмечается как `HOLEY_ELEMENTS`.

array[1] = "b";
array[2] = "c";
// Теперь в массиве не осталось дырок, но он не может перейти
// из более общего сорта `HOLEY_ELEMENTS` в более конкретный
// `PACKED_ELEMENTS`.

Массив, однажды отмеченный как разреженный, навсегда остается разреженным — даже если в нем не осталось дырок!

Задавать подобные массивы лучше в виде литералов:

const array = ["a", "b", "c"];
// сорт элементов: PACKED_ELEMENTS

Если элементы массива неизвестны заранее, стоит создать пустой массив, и добавлять в него элементы методом push.

const array = [];
// ...
array.push(someValue);
// ...
array.push(someOtherValue);

Отладка сортов элементов

Чтобы понять, какой сорт элементов содержит объект, понадобится отладочный билд d8 (собранный из исходников или полученный с помощью jsvu). Его следует запустить с параметром:

out/x64.debug/d8 --allow-natives-syntax

Эта команда запустит REPL d8, в котором будут доступны особые встроенные функции. Функция %DebugPrint(object) позволит нам понять сорт элементов объекта (поле elements):

d8> const array = [1, 2, 3]; %DebugPrint(array);
DebugPrint: 0x1fbbad30fd71: [JSArray]
 - map = 0x10a6f8a038b1 [FastProperties]
 - prototype = 0x1212bb687ec1
 - elements = 0x1fbbad30fd19 <FixedArray[3]> [PACKED_SMI_ELEMENTS (COW)]
 - length = 3
 - properties = 0x219eb0702241 <FixedArray[0]> {
    #length: 0x219eb0764ac9 <AccessorInfo> (const accessor descriptor)
 }
 - elements= 0x1fbbad30fd19 <FixedArray[3]> {
           0: 1
           1: 2
           2: 3
 }
[...]

В отладочных билдах также доступен флаг --trace-elements-transitions. При его использовании, V8 будет уведомлять о каждом преобразовании сорта элементов.

$ cat my-script.js
const array = [1, 2, 3];
array[3] = 4.56;

$ out/x64.debug/d8 --trace-elements-transitions my-script.js
elements transition [PACKED_SMI_ELEMENTS -> PACKED_DOUBLE_ELEMENTS] in ~+34 at x.js:2 for 0x1df87228c911 <JSArray[3]> from 0x1df87228c889 <FixedArray[3]> to 0x1df87228c941 <FixedDoubleArray[22]>