Думаю, ни для кого не секрет, что все популярные 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 <SharedFunctionInfo getX>)] 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 <Map(FIXED_ARRAY_TYPE)> - length: 1 0: 0x0b7500002b91 <String[1]: #x> Handler Table (size = 0) Source Position Table (size = 0) // Далее информация о переданном объекте DebugPrint: 0xb75001c9475: [JS_OBJECT_TYPE] - map: 0x0b75000d9d81 <Map[16](HOLEY_ELEMENTS)> [FastProperties] - prototype: 0x0b75000c4b11 <Object map = 0xb75000c414d> - elements: 0x0b75000006cd <FixedArray[0]> [HOLEY_ELEMENTS] - properties: 0x0b75000006cd <FixedArray[0]> - All own properties (excluding elements): { 0xb7500002b91: [String] in ReadOnlySpace: #x: 1 (const data field 0), location: in-object } 0xb75000d9d81: [Map] in OldSpace - map: 0x0b75000c3c29 <MetaMap (0x0b75000c3c79 <NativeContext[285]>)> - type: JS_OBJECT_TYPE - instance size: 16 - inobject properties: 1 - unused property fields: 0 - elements kind: HOLEY_ELEMENTS - enum length: invalid - stable_map - back pointer: 0x0b75000d9d59 <Map[16](HOLEY_ELEMENTS)> - prototype_validity cell: 0x0b7500000a31 <Cell value= 1> - instance descriptors (own) #1: 0x0b75001c9485 <DescriptorArray[1]> - prototype: 0x0b75000c4b11 <Object map = 0xb75000c414d> - constructor: 0x0b75000c4655 <JSFunction Object (sfi = 0xb7500335385)> - dependent code: 0x0b75000006dd <Other heap object (WEAK_ARRAY_LIST_TYPE)> - construction counter: 0Итак, в сущности, скомпилированный байткод функции 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 // / \ // <obj1> <obj2>По мере добавления свойств объекту, его дерево скрытых классов увеличивается.
const obj1 = {} obj1.x = 1; obj1.y = 2; obj1.z = 3; // {} -> { x } -> { x, y } -> { x, y, z } -> <obj1>Давайте вернемся к функции, с которой мы начали. Предположим, мы передали ей объект следующего вида.
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 <Map[24](HOLEY_ELEMENTS)> [FastProperties] - prototype: 0x2034000c4b11 <Object map = 0x2034000c414d> - elements: 0x2034000006cd <FixedArray[0]> [HOLEY_ELEMENTS] - properties: 0x2034000006cd <FixedArray[0]> - All own properties (excluding elements): { 0x203400002ba1: [String] in ReadOnlySpace: #y: 1 (const data field 0), location: in-object 0x203400002b91: [String] in ReadOnlySpace: #x: 2 (const data field 1), location: in-object 0x203400002bb1: [String] in ReadOnlySpace: #z: 3 (const data field 2), location: in-object } 0x2034000d9cf9: [Map] in OldSpace - map: 0x2034000c3c29 <MetaMap (0x2034000c3c79 <NativeContext[285]>)> - type: JS_OBJECT_TYPE - instance size: 24 - inobject properties: 3 - unused property fields: 0 - elements kind: HOLEY_ELEMENTS - enum length: invalid - stable_map - back pointer: 0x2034000d9cd1 <Map[24](HOLEY_ELEMENTS)> - prototype_validity cell: 0x203400000a31 <Cell value= 1> - instance descriptors (own) #3: 0x2034001c9491 <DescriptorArray[3]> - prototype: 0x2034000c4b11 <Object map = 0x2034000c414d> - constructor: 0x2034000c4655 <JSFunction Object (sfi = 0x203400335385)> - dependent code: 0x2034000006dd <Other heap object (WEAK_ARRAY_LIST_TYPE)> - construction counter: 0В примере выше скрытый класс расположен по адресу 0x2034000d9cd1 (back pointer).
d8> %DebugPrintPtr(0x2034000d9cd1) DebugPrint: 0x2034000d9cd1: [Map] in OldSpace - map: 0x2034000c3c29 <MetaMap (0x2034000c3c79 <NativeContext[285]>)> - type: JS_OBJECT_TYPE - instance size: 24 - inobject properties: 3 - unused property fields: 1 - elements kind: HOLEY_ELEMENTS - enum length: invalid - back pointer: 0x2034000d9c89 <Map[24](HOLEY_ELEMENTS)> - prototype_validity cell: 0x203400000a31 <Cell value= 1> - instance descriptors #2: 0x2034001c9491 <DescriptorArray[3]> - transitions #1: 0x2034000d9cf9 <Map[24](HOLEY_ELEMENTS)> 0x203400002bb1: [String] in ReadOnlySpace: #z: (transition to (const data field, attrs: [WEC]) @ Any) -> 0x2034000d9cf9 <Map[24](HOLEY_ELEMENTS)> - prototype: 0x2034000c4b11 <Object map = 0x2034000c414d> - constructor: 0x2034000c4655 <JSFunction Object (sfi = 0x203400335385)> - dependent code: 0x2034000006dd <Other heap object (WEAK_ARRAY_LIST_TYPE)> - construction counter: 0 0x2034000c3c29: [MetaMap] in OldSpace - map: 0x2034000c3c29 <MetaMap (0x2034000c3c79 <NativeContext[285]>)> - type: MAP_TYPE - instance size: 40 - native_context: 0x2034000c3c79 <NativeContext[285]>Из которого мы можем получить массив дескрипторов по адресу 0x2034001c9491 (instance descriptors).
d8> %DebugPrintPtr(0x2034001c9491) DebugPrint: 0x2034001c9491: [DescriptorArray] - map: 0x20340000062d <Map(DESCRIPTOR_ARRAY_TYPE)> - enum_cache: 3 - keys: 0x2034000daaa9 <FixedArray[3]> - indices: 0x2034000daabd <FixedArray[3]> - 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 <MetaMap (0x20340000007d <null>)> - type: DESCRIPTOR_ARRAY_TYPE - instance size: variable - elements kind: HOLEY_ELEMENTS - enum length: invalid - stable_map - non-extensible - back pointer: 0x203400000061 <undefined> - prototype_validity cell: 0 - instance descriptors (own) #0: 0x203400000701 <DescriptorArray[0]> - prototype: 0x20340000007d <null> - constructor: 0x20340000007d <null> - dependent code: 0x2034000006dd <Other heap object (WEAK_ARRAY_LIST_TYPE)> - 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%1LoadIC Grouped by category: 1# >100.00%1Load Grouped by functionName: 1# >100.00%1~getX Grouped by script: 1# >100.00%1Script(3): index.js Grouped by sourcePosition: 1# >100.00%1index.js:3:14 Grouped by code: 1# >100.00%1Code(JS~) Grouped by state: 1# >100.00%10 → 1 Grouped by key: 1# >100.00%1x Grouped by map: 1# >100.00%1Map(0x3cd2000d9e61) Grouped by reason: 1# >100.00%1В списке IC List мы видим нотацию типа LoadIC, которая говорит о получении доступа к свойству объекта из кэша. Здесь же указана сама функция functionName: ~getX, адрес скрытого класса Map(0x3cd2000d9e61) и название свойства key: x. Но наибольший интерес представляет state: 0 -> 1.
Существует несколько типов IC. Полный список выглядит следующим образом:
// 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
ссылка на оригинал статьи https://habr.com/ru/articles/810543/
Добавить комментарий