Деревья переходов, deprecation и миграция

Переходы — это рёбра в общем дереве

Вспомним однострочную версию из browser/03-v8-internals/03-hidden-classes: добавление x затем y приходит в другой лист, чем добавление y затем x, так что порядок важен. Теперь механизм. Каждый Map хранит forward-TransitionArray с ключом {имя свойства, attributes}. Добавление свойства:

1. Ищет ребро {имя, attributes} в TransitionArray текущего Map.
2. Если ребро есть, следует по нему — никакой аллокации, вы переиспользуете существующий дочерний Map и его (общий) DescriptorArray.
3. Если ребра нет, создаёт новый дочерний Map (расширяя DescriptorArray родителя на один дескриптор), записывает ребро и направляет объект на новый Map.

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

const a = {}; a.x = 1; a.y = 2;   // empty -> +x -> +x,y   (создаёт 2 ребра)
const b = {}; b.x = 3; b.y = 4;   // empty -> +x -> +x,y   (следует по ним; 0 новых Map)
const c = {}; c.y = 5; c.x = 6;   // empty -> +y -> +y,x   (новая ветка; 2 новых Map)

Ещё три способа перейти (не только добавление свойств)

Обзор намекал, что переходы приходят лишь от добавления свойств. Это не так. Есть три других триггера, и они кусаются в проде:

• Смена elements kind. Запись float’а в массив PACKED_SMI_ELEMENTS или создание дырки переводит Map массива в более широкий elements kind (PACKED_SMI → PACKED_DOUBLE → PACKED_ELEMENTS и HOLEY-варианты). Односторонне, как и дерево свойств.
• Обобщение representation поля. Это главное. Поле стартует узким — скажем, Smi. Если позже какой-то экземпляр сохранит значение, которое не помещается (2.5 или строку), representation поля должен расшириться до Double или Tagged. Но representation — это свойство Map, общее для всех экземпляров. Так что V8 не может изменить один объект; он должен обобщить Map.
• Потеря constness. Поле const, пока каждый экземпляр присваивал ему одно и то же значение. Первый экземпляр, присвоивший другое значение, переводит дескриптор в mutable, что само по себе переход (скомпилированный код, заинлайнивший константу, должен быть инвалидирован).

Все три «не-добавляющих» триггера объединяет одно: изменение того, что поле может держать, вынуждает менять общий Map, а не отдельные объекты. Без этого понимания можно часами грешить на GC или сеть, когда настоящая причина — одно присваивание float’а двумя фреймами выше.

Deprecation и миграция: как V8 расширяет общее поле

Вот тонкая часть. Пусть 10000 объектов разделяют Map M1, где поле temp имеет representation Smi. Теперь один объект делает obj.temp = 98.6. Поле должно стать Double — но для всей формы, потому что Map общий. V8 не может переписать 10000 объектов в этот миг (у него даже нет их списка). Вместо этого:

1. Он создаёт новый Map M2, идентичный M1, кроме того, что temp — Double (более общий representation). Разделение происходит в нужном месте дерева, потомки перенаправляются.
2. Он помечает M1 как deprecated — мёртвый Map, который больше не следует использовать. Существующие объекты пока всё ещё указывают на M1.
3. Миграция ленива. В следующий раз, когда V8 трогает один из этих объектов по медленному пути (доступ к свойству с промахом inline cache, %DebugPrint и т. п.), он замечает, что Map объекта deprecated, идёт к соответствующему не-deprecated Map (M2) по back-pointer’ам из урока 01, переписывает раскладку объекта на месте (упаковывая целое в double-слот) и обновляет указатель map объекта. Это путь «MigrationMarker» / миграции.

Так что единственное obj.temp = 98.6 может начать deprecation формы, используемой тысячами объектов, каждый из которых платит небольшую стоимость миграции при следующем доступе. Если это поле колеблется между целым и float’ом, можно повторно churn’ить deprecation — настоящий, трудно замечаемый источник деоптов.

Почему перемешанные порядки ключей патологичны

Сложите кусочки. Функция, строящая объекты итерацией ключей входа в произвольном порядке (ре-сериализатор JSON, обобщённый mapper, генерированный код), создаёт новую ветку дерева переходов почти на каждый различный порядок, который видит. Формы никогда не повторяются, поэтому:

• Каждый объект аллоцирует свежие Map и DescriptorArray (раздувание памяти из урока 01).
• Нижестоящий inline cache, читающий эти объекты, видит свежий Map почти каждый раз → он становится polymorphic, затем megamorphic, затем сдаётся (урок 05).
• TurboFan не может специализироваться на стабильной форме, так что горячая функция либо не достигает верхнего яруса, либо повторно деоптится.

Фикс всегда один: строй по фиксированной схеме в постоянном порядке (отсутствующие поля по умолчанию null) или храни действительно динамические наборы ключей в коллекции Map, созданной для произвольных ключей.