Оптимизация JavaScript. Inline Caches
Думаю, ни для кого не секрет, что все популярные JavaScript движки имеют схожий пайплайн выполнения кода. Выглядит он примерно следующим образом. Интерпретатор быстро компилирует JS-код в байт «на лету». Полученный байт код начинает исполняться и параллельно обрабатывается оптимизатором. Оптимизатору требуется время на такую обработку, но в итоге может получиться высоко-оптимизорованный код, который будет работать в разы быстрее. В движке V8 роль интерпретатора выполняет Ignition, а оптимизатором является Turbofan. В движке Chakra, который используется в Edge, вместо одного оптимизатора целых два, SimpleJIT и FullJIT. А в JSC (Safari), аж три Baseline, DFG и FTL. Конкретная реализация в разных движка может отличаться, но принципиальная схема, в целом одинакова.
Сегодня мы будем говорить об одном из множества механизмов оптимизации, который называется Inline Caches.
Итак, давайте возьмем самую обычную функцию и попробуем понять, как она будет работать в «runtime».
function getX(obj) {
return obj.x;
}Наша функция довольно примитивна. Простой геттер, который в качестве аргумента принимает объект, а на выходе возвращает значение свойства x этого объекта. С точки зрения JS-разработчика функция выглядит абсолютно атомарно. Однако, давайте заглянем под капот движка и посмотрим, что она представляет из себя в скомпилированном виде.
Для экспериментов, как обычно, будем использовать самый популярный JS-движок V8 (на момент написания статьи версия 12.6.72). Для полноценного дебага, кроме тела самой функции нам нужна её вызвать с реальным аргументом. Также, добавим вывод информации об объекте, он понадобится нам чуть ниже.
function getX(obj) {
%DebugPrint(obj);
return obj.x;
}
getX({ x: 1 });Напомню, %DebugPrint является строенной функцией V8, чтобы использовать её в коде, нужно запустить рантайм d8 с флагом --allow-natives-syntax. Долнительно, выведем в консоль байткод исполняемого скрипта (флаг --print-bytecode).
%> d8 --print-bytecode --allow-natives-syntax index.js
...
// байткод функции getX
[generated bytecode for function: getX (0x0b75000d9c29 )]
Bytecode length: 10
Parameter count 2
Register count 0
Frame size 0
0x28c500002194 @ 0 : 65 af 01 03 01 CallRuntime [DebugPrint], a0-a0
0x28c500002199 @ 5 : 2d 03 00 00 GetNamedProperty a0, [0], [0]
0x28c50000219d @ 9 : ab Return
Constant pool (size = 1)
0xb75000d9dcd: [FixedArray] in OldSpace
- map: 0x0b7500000565
- length: 1
0: 0x0b7500002b91
Handler Table (size = 0)
Source Position Table (size = 0)
// Далее информация о переданном объекте
DebugPrint: 0xb75001c9475: [JS_OBJECT_TYPE]
- map: 0x0b75000d9d81 [FastProperties]
- prototype: 0x0b75000c4b11 Итак, в сущности, скомпилированный байткод функции getX выглядит следующим образом.
0x28c500002194 @ 0 : 65 af 01 03 01 CallRuntime [DebugPrint], a0-a0
0x28c500002199 @ 5 : 2d 03 00 00 GetNamedProperty a0, [0], [0]
0x28c50000219d @ 9 : ab ReturnПервая строчка, это вызов функции %DebugPrint. Она носит исключительно вспомогательный характер и на исполняемый код не влияет, мы можем её спокойно опустить. Следующая инструкция GetNamedProperty. Её задача — получить значение указанного свойства из переданного объекта. На вход инструкция получает три параметра. Первый — ссылка на объект. В нашем случае, ссылка на объект хранится в a0 — первом аргументе функции getX. Второй и третий параметры, это адрес скрытого класса и offset нужно свойства в массиве дескрипторов.
Форма объекта
Что такое скрытые классы, массив дескрипторов и как вообще устроены объекты в JavaScript я подробно рассказывал в статье Структура объекта в JavaScript движках. Не буду пересказывать всю статью, обозначу только нужные нам факты. Каждый объект имеет один или несколько скрытых классов (Hidden Classes). Скрытые классы являются исключительно внутренним механизмом движка и JS-разработчику не доступны, ну, по крайней мере, без применения специальных встроенных методов движка. Скрытый класс представляет, так называемую, форму объекта и всю необходимую информацию о свойствах объекта. Сам же объект хранит только значения свойств и ссылку на скрытый класс. Если два объекта имеют одинаковую форму, у них будет ссылка на один и тот же скрытый класс.
const obj1 = { x: 1 }
const obj2 = { x: 2 }
// {} <- empty map
// |
// { x } <- common map
// / \
// По мере добавления свойств объекту, его дерево скрытых классов увеличивается.
const obj1 = {}
obj1.x = 1;
obj1.y = 2;
obj1.z = 3;
// {} -> { x } -> { x, y } -> { x, y, z } -> Давайте вернемся к функции, с которой мы начали. Предположим, мы передали ей объект следующего вида.
function getX(obj) {
return obj.x;
}
getX({ y: 1, x: 2, z: 3 });Что получить значение свойства x, интерпретатор должен знать: а) адрес последнего скрытого класса объекта; б) offset этого свойства в массиве десктрипторов.
d8> const obj = { y: 1, x: 2, z: 3};
d8>
d8> %DebugPrint(obj);
DebugPrint: 0x2034001c9435: [JS_OBJECT_TYPE]
- map: 0x2034000d9cf9 [FastProperties]
- prototype: 0x2034000c4b11 В примере выше скрытый класс расположен по адресу 0x2034000d9cd1 (back pointer).
d8> %DebugPrintPtr(0x2034000d9cd1)
DebugPrint: 0x2034000d9cd1: [Map] in OldSpace
- map: 0x2034000c3c29 )>
- type: JS_OBJECT_TYPE
- instance size: 24
- inobject properties: 3
- unused property fields: 1
- elements kind: HOLEY_ELEMENTS
- enum length: invalid
- back pointer: 0x2034000d9c89
- prototype_validity cell: 0x203400000a31
- instance descriptors #2: 0x2034001c9491
- transitions #1: 0x2034000d9cf9
0x203400002bb1: [String] in ReadOnlySpace: #z: (transition to (const data field, attrs: [WEC]) @ Any) -> 0x2034000d9cf9
- prototype: 0x2034000c4b11 | Из которого мы можем получить массив дескрипторов по адресу 0x2034001c9491 (instance descriptors).
d8> %DebugPrintPtr(0x2034001c9491)
DebugPrint: 0x2034001c9491: [DescriptorArray]
- map: 0x20340000062d
- enum_cache: 3
- keys: 0x2034000daaa9
- indices: 0x2034000daabd
- nof slack descriptors: 0
- nof descriptors: 3
- raw gc state: mc epoch 0, marked 0, delta 0
[0]: 0x203400002ba1: [String] in ReadOnlySpace: #y (const data field 0:s, p: 2, attrs: [WEC]) @ Any
[1]: 0x203400002b91: [String] in ReadOnlySpace: #x (const data field 1:s, p: 1, attrs: [WEC]) @ Any
[2]: 0x203400002bb1: [String] in ReadOnlySpace: #z (const data field 2:s, p: 0, attrs: [WEC]) @ Any
0x20340000062d: [Map] in ReadOnlySpace
- map: 0x2034000004c5 )>
- type: DESCRIPTOR_ARRAY_TYPE
- instance size: variable
- elements kind: HOLEY_ELEMENTS
- enum length: invalid
- stable_map
- non-extensible
- back pointer: 0x203400000061
- prototype_validity cell: 0
- instance descriptors (own) #0: 0x203400000701
- prototype: 0x20340000007d
- constructor: 0x20340000007d
- dependent code: 0x2034000006dd
- construction counter: 0 Где интерпретатор может найти нужное свойство по его имени и получить offset, в нашем случае равный 1.
Таким образом, путь интерпретатора будет выглядеть примерно следующим образом.
Наш случай довольно простой. Здесь значения свойств хранятся внутри самого объекта (in-object), что делает доступ к ним довольно быстрым. Но, тем не менее, определение позиции свойства в массиве дескрипторов все равно будет пропорционально количеству самих свойств. Более того, в статье Структура объекта в JavaScript движках я говорил, что значения не всегда хранятся таким «быстрым» образом. В ряде случаев тип хранилища может быть изменен на медленный «словарь».
Inline Cache
Конечно, в единичных случаях для JS-движка это все не вызывает больших трудностей, а время доступа к значению свойств вряд ли можно заметить невооруженным глазом. Но что, если наш случай не единичный? Допустим, нам требуется выполнить функцию сотни или тысячи раз в цикле? Суммарное время работы тут приобретает критическую важность. При том, что функция, фактически выполняет одни и те же операции, разработчики JavaScript предложили оптимизировать процесс поиска свойства и не выполнять его каждый раз. Все, что для этого требуется, сохранить адрес скрытого класса объекта и offset нужного свойства.
Вернемся к самому началу статьи и к инструкции GetNamedProperty, которая имеет три параметра. Мы уже выяснили, что первый параметр — это ссылка на объект. Второй параметр — адрес скрытого класса. Третий параметр — найденный offset свойства. Определив эти параметры единожды, функция может их запомнить и при следующем запуске не выполнять процедуру поиска значения снова. Такое кэширование и называется Inline Cache (IC).
TurboFan
Однако, стоит учитывать, что мемоизация параметров тоже требует памяти и некоторого процессорного времени. Это делает механизм эффективным только при интенсивном выполнении функции (так называемая, hot-функция). Насколько интенсивно выполняется функция зависит от количества и частоты её вызовов. Оценкой интенсивности занимается оптимизатор. В случае с V8 в роли оптимизатора выступает TurboFan. Прежде всего, оптимизатор собирает граф из AST и байткода и отправляет его на фазу «inlining», где собираются метрики вызовов, загрузок и сохранений в кэш. Далее, если функция пригодна для inline-кэширования, она встает в очередь на оптимизацию. После того как очередь заполнена оптимизатор должен определить самую «горячую» из них и произвести кэширование. Потом взять следующую и так далее. В отличие, кстати, от его предшественника Crankshaft, который брал функции по очереди начиная с первой. Вообще, данная тема довольно большая и заслуживает отдельной статьи, сейчас рассматривать все подробности и особенности эвристики TurboFan смысла не имеет. Перейдем лучше к примерам.
Типы IC
Чтобы проанализировать работу IC, нужно включить логирование в runtime-среде. В случае с d8 это можно сделать, указав флаг --log-ic.
%> d8 --log-ic
function getX(obj) {
return obj.x;
}
for (let i = 0; i < 10; i++) {
getX({ x: i });
}Как я уже говорил, TurboFan начинает кэшировать свойства объектов только в hot-функциях. Чтобы сделать нашу функцию таковой, нам потребуется запустить её в цикле несколько раз подряд. В моем простом скрипте в среде d8 понадобилось минимум 10 итераций. На практике, в других условиях и при наличии других функций, это число может варьироваться и, скорее всего, будет больше. Полученный лог теперь можно прогнать через System Analyzer.
Grouped by type: 1#
>100.00% 1 LoadIC
Grouped by category: 1#
>100.00% 1 Load
Grouped by functionName: 1#
>100.00% 1 ~getX
Grouped by script: 1#
>100.00% 1 Script(3): index.js
Grouped by sourcePosition: 1#
>100.00% 1 index.js:3:14
Grouped by code: 1#
>100.00% 1 Code(JS~)
Grouped by state: 1#
>100.00% 1 0 → 1
Grouped by key: 1#
>100.00% 1 x
Grouped by map: 1#
>100.00% 1 Map(0x3cd2000d9e61)
Grouped by reason: 1#
>100.00% 1 В списке IC List мы видим нотацию типа LoadIC, которая говорит о получении доступа к свойству объекта из кэша. Здесь же указана сама функция functionName: ~getX, адрес скрытого класса Map(0x3cd2000d9e61) и название свойства key: x. Но наибольший интерес представляет state: 0 -> 1.
Существует несколько типов IC. Полный список выглядит следующим образом:
/src/common/globals.h#1481
// State for inline cache call sites. Aliased as IC::State.
enum class InlineCacheState {
// No feedback will be collected.
NO_FEEDBACK,
// Has never been executed.
UNINITIALIZED,
// Has been executed and only one receiver type has been seen.
MONOMORPHIC,
// Check failed due to prototype (or map deprecation).
RECOMPUTE_HANDLER,
// Multiple receiver types have been seen.
POLYMORPHIC,
// Many DOM receiver types have been seen for the same accessor.
MEGADOM,
// Many receiver types have been seen.
MEGAMORPHIC,
// A generic handler is installed and no extra typefeedback is recorded.
GENERIC,
};В системном анализаторе эти типы обозначаются символами
0: UNINITIALIZED
X: NO_FEEDBACK
1: MONOMORPHIC
^: RECOMPUTE_HANDLER
P: POLYMORPHIC
N: MEGAMORPHIC
D: MEGADOM
G: GENERICНапример, тип X (NO_FEEDBACK) говорит о тои, что оптимизатор пока не собрал достаточной статистики, чтобы поставить функцию на оптимизацию. В нашем же случае мы видим state: 0 -> 1 означает, что функция перешла в состояние «мономорфного IC».
Monomorphic
Я уже говорил, что на практике, одна и та же функция может принимать объект в качестве аргумента. Форма этого объекта на конкретном вызове функции может отличаться от предыдущего. Что несколько усложняет жизнь оптимизатору. Меньше всего проблем возникает в случае, когда мы передаем в функцию только одинаковый по форме объекты, как в нашем последнем примере.
function getX(obj) {
return obj.x; // Monomorphic IC
}
for (let i = 0; i < 10; i++) {
getX({ x: i }); // все объекты имеют одинаковую форму
}В этом случае, оптимизатору надо просто запомнить адрес скрытого класса и offset свойства. Такой тип IC называется мономорфным.
Polymorphic
Давайте теперь попробуем добавить вызов функции с объектами разной формы.
function getX(obj) {
return obj.x; // Polymorphic IC
}
for (let i = 0; i < 10; i++) {
getX({ x: i, y: 0 });
getX({ y: 0, x: i });
}
В «IC List» теперь мы видим:
50.00% 1 0 → 1
50.00% 1 1 → PФункция в рантайме получила несколько разных форм объекта. Доступ к свойству x у каждой формы будет отличаться. У каждой свой адрес скрытого класса и свой offset этого свойства. В этом, случае оптимизатор выделяет по два слота для каждой формы объекта, куда и сохраняет нужные параметры. Условно представить такую структура можно в виде массива наборов параметров.
[
[Map1, offset1],
[Map2, offset2],
...
]Такой тип IC называется полиморфным. У полиморфного IC есть ограничение на количество допустимых форм.
/src/wasm/wasm-constants.h#192
// Maximum number of call targets tracked per call.
constexpr int kMaxPolymorphism = 4;По умолчанию, полиморфный тип может от 2 до 4 форм на функцию. Но этот параметр можно регулировать флагом --max-valid-polymorphic-map-count.
Megamorphic
Если же форм объекта больше, чем может переварит Polymorphic, тип меняется на мегаморфный.
function getX(obj) {
return obj.x; // Megamorphic IC
}
for (let i = 0; i < 10; i++) {
getX({ x: i });
getX({ prop1: 0, x: i });
getX({ prop1: 0, prop2: 1, x: i });
getX({ prop1: 0, prop2: 1, prop3: 2, x: i });
getX({ prop1: 0, prop2: 1, prop3: 2, prop4: 3, x: i });
}Результат IC List:
40.00% 2 P → P
20.00% 1 0 → 1
20.00% 1 1 → P
20.00% 1 P → NПоиск нужного набора параметров в таком случае нивелирует экономию процессорного времени и, следовательно, не имеет никакого смысла. Поэтому оптимизатор просто сохраняет в кэш символ MegamorphicSymbol. Для следующих вызовов фукнции это будет означать, что закэшированных параметров тут нет, их придется брать обычным способом. Равно как и нет смысла дальше ставить функцию на оптимизацию и собирать её метрики.
Заключение
Вы наверняка заметили, что в списке типов IC присутствует еще MEGADOM. Этот тип используется для кэширования нод DOM-дерева. Дело в том, что механизм инлайн-кэширования не ограничивается только функциями и объектами. Он активно применяется и во многих других местах, в том числе и за пределами V8.Ввесь объем информации о кэшировании за один раз мы физически покрыть не сможем. А раз уж мы сегодня говорим об объектах JavaScript, то и тип MegaDom рассматривать в этой статье не будем.
Давайте проведем пару тестов и посмотрим, на сколько эффективно работает оптимизация Turbofan в V8. Эксперимент будем ставить в среде Node.js (последняя стабильная версия на момент написания статьи v20.12.2).
Экспериментальный код:
const N = 1000;
//===
function getXMonomorphic(obj) {
let sum = 0;
for (let i = 0; i < N; i++) {
sum += obj.x;
}
return sum;
}
console.time('Monomorphic');
for (let i = 0; i < N; i++) {
getXMonomorphic({ x: i });
getXMonomorphic({ x: i });
getXMonomorphic({ x: i });
getXMonomorphic({ x: i });
getXMonomorphic({ x: i });
}
console.timeLog('Monomorphic');
//===
function getXPolymorphic(obj) {
let sum = 0;
for (let i = 0; i < N; i++) {
sum += obj.x;
}
return sum;
}
console.time('Polymorphic');
for (let i = 0; i < N; i++) {
getXPolymorphic({ x: i, y: 0 });
getXPolymorphic({ y: 0, x: i });
getXPolymorphic({ x: i, y: 0 });
getXPolymorphic({ y: 0, x: i });
getXPolymorphic({ x: i, y: 0 });
}
console.timeEnd('Polymorphic');
//===
function getXMegamorphic(obj) {
let sum = 0;
for (let i = 0; i < N; i++) {
sum += obj.x;
}
return sum;
}
//===
console.time('Megamorphic');
for (let i = 0; i < N; i++) {
getXMegamorphic({ x: i });
getXMegamorphic({ prop1: 0, x: i });
getXMegamorphic({ prop1: 0, prop2: 1, x: i });
getXMegamorphic({ prop1: 0, prop2: 1, prop3: 2, x: i });
getXMegamorphic({ prop1: 0, prop2: 1, prop3: 2, prop4: 3, x: i });
}
console.timeLog('Megamorphic');Для начала запустим скрипт с отключенной оптимизацией и посмотрим «чистую» скорость работы функций.
%> node --no-opt test.js
Monomorphic: 68.55ms
Polymorphic: 69.939ms
Megamorphic: 85.045msДля чистоты эксперимента я повторил тесты несколько раз. Скорость работы мономорфных и полиморфных объектов примерно одинакова. Полиморфные иногда могу оказываться даже быстрее. Связано это уже не столько с работой самого V8, сколько с системными ресурсами. А вот скорость мегаморфных объектов несколько ниже в силу того, что на этом тапе образуется дерево скрытых классов и доступ к свойствам этих объектов априори сложнее, чем в первых двух случаях.
Теперь запустим тот же скрипт с включенной оптимизацией:
%> node test.js
Monomorphic: 9.313ms
Polymorphic: 9.673ms
Megamorphic: 29.104msСкорость работы мономорфных и полиморфных функций увеличилась примерно в 7 раз. Как и в предыдущем случае, разница между этими двумя типами незначительна и при повторных испытаниях полиморфные иногда бывают даже быстрее. А вот скорость мегаморфной функции увеличилась всего в 3 раза. Вообще, исходя из теории, описанной выше, мегаморфные функции не должны были показать прирост скорости на оптимизации. Однако, не все так просто. Во-первых, у них все же имеется побочный эффект от оптимизации, поскольку такие функции исключаются из процесса дальнейшего сбора метрик. Это хоть и не большое, но все же преимущество перед остальными типами. Во-вторых, оптимизация работы JS не ограничена инлайн-кэшированием доступа к свойствам объекта. Существует еще ряд других видов оптимизаций, которые в этой статье мы не рассматривали.
Более того, в 2023-м году Google выпустил релиз «Chromium M117», в который был включен новый оптимизатор Maglev. Он был встроен как промежуточное звено между Ignition (интерпретатором) и Turbofan (оптимизатором). Теперь процесс оптимизации приобрел трех-ступенчатую архитектуру и выглядит как Ignition -> Maglev -> Turbofan. Maglev вносит свой вклад в оптимизацию функций, в частности, он работает с аргументами функции. Подробнее об этом поговорим в другой раз. А пока можем сделать вывод, что мегаморфные функции примерно в два раза медленнее мономорфных и полиморфных.
Эту и другие мои статьи, так же, читайте в моем канале:
RU: https://t.me/frontend_almanac_ru
EN: https://t.me/frontend_almanac
