Карты (Скрытые классы) в V8

Давайте покажем, как V8 строит свои скрытые классы. Основные структуры данных таковы:

Map: сам скрытый класс. Это первый указатель в объекте и, следовательно, позволяет легко сравнивать, имеют ли два объекта один и тот же класс.
DescriptorArray: Полный список свойств, которые имеет этот класс, а также информация о них. В некоторых случаях значение свойства даже находится в этом массиве.
TransitionArray: Массив "переходов" от этого Map к родственным картам. Каждый переход — это имя свойства, и его следует рассматривать как "если я добавлю свойство с этим именем к текущему классу, к какому классу я перейду?"

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

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

Зачем нужны скрытые классы?

V8 мог бы обойтись без скрытых классов, конечно. Он рассматривал бы каждый объект как мешок свойств. Однако очень полезный принцип был бы упущен: принцип разумного проектирования. V8 предполагает, что вы создадите только определенное количество различных видов объектов. И каждый вид объектов будет использоваться в определенных сценариях, которые можно будет увидеть как шаблоны. Я говорю "которые можно будет увидеть", потому что язык JavaScript является скриптовым, а не предварительно скомпилированным. Таким образом, V8 никогда не знает, что будет дальше. Чтобы использовать разумное проектирование (т.е. предположение, что за входным кодом стоит разум), V8 необходимо следить и ждать, пока структура не станет очевидной. Механизм скрытого класса — главный способ сделать это. Конечно, это предполагает сложный механизм наблюдения, а это те самые Inline Caches (ICs), о которых много написано.

Так что, если вы убеждены, что это хорошая и необходимая работа, следуйте за мной!

Пример

function Peak(name, height, extra) {
  this.name = name;
  this.height = height;
  if (isNaN(extra)) {
    this.experience = extra;
  } else {
    this.prominence = extra;
  }
}

m1 = new Peak("Маттерхорн", 4478, 1040);
m2 = new Peak("Вендельштейн", 1838, "хорошо");

С этим кодом у нас уже есть интересное древо карт от корневой карты (также известной как начальная карта), которая привязана к функции Peak:

Каждый синий блок — это карта, начиная с начальной карты. Это карта объекта, возвращенного, если каким-то образом, у нас получилось запустить функцию Peak, не добавляя ни одного свойства. Последующие карты — это те, которые появляются в результате добавления свойств, указанных именами на переходах между картами. Каждая карта имеет список свойств, связанных с объектом этой карты. Кроме того, она описывает точное местоположение каждого свойства. Наконец, начиная с одной из этих карт, например, Map3, которая является скрытым классом объекта, полученного, если вы передали число для аргумента extra в Peak(), можно следовать обратной ссылке вверх до самой начальной карты.

Давайте нарисуем это снова с этой дополнительной информацией. Аннотация (i0), (i1) означает расположение поля в объекте — 0, 1 и т.д.:

Теперь, если вы потратите время на исследование этих карт до того, как создали хотя бы 7 объектов Peak, вы столкнетесь с слэк-трекингом, который может быть запутанным. У меня есть другая статья об этом. Просто создайте еще 7 объектов, и процесс будет завершен. На данный момент ваши объекты Peak будут иметь ровно 3 свойства в объекте, без возможности добавления дополнительных напрямую. Любые дополнительные свойства будут переноситься в резервный хранилище свойств объекта. Это всего лишь массив значений свойств, индекс которого берется из карты (точнее, из DescriptorArray, прикрепленного к карте). Давайте добавим свойство к m2 на новой строке и снова посмотрим на древо карт:

m2.cost = "одна рука, одна нога";

Я кое-что здесь подкинул. Заметьте, что все свойства аннотированы как "const", что с точки зрения V8 означает, что никто их не изменял с момента конструктора, поэтому их можно считать константами после инициализации. TurboFan (оптимизирующий компилятор) это очень ценит. Если m2 используется как глобальная константа функцией, то доступ к m2.cost может быть выполнен на этапе компиляции, поскольку поле помечено как константное. Я вернусь к этому позже в статье.

Обратите внимание, что свойство "cost" помечено как const p0, что означает, что это константное свойство, хранящееся на нулевом индексе в хранилище свойств (properties backing store), а не в самом объекте. Это потому, что в объекте больше нет места. Эта информация видна в %DebugPrint(m2):

d8> %DebugPrint(m2);
DebugPrint: 0x2f9488e9: [JS_OBJECT_TYPE]
 - map: 0x219473fd <Map(HOLEY_ELEMENTS)> [FastProperties]
 - prototype: 0x2f94876d <Object map = 0x21947335>
 - elements: 0x419421a1 <FixedArray[0]> [HOLEY_ELEMENTS]
 - properties: 0x2f94aecd <PropertyArray[3]> {
    0x419446f9: [String] in ReadOnlySpace: #name: 0x237125e1
        <String[11]: #Wendelstein> (const data field 0)
    0x23712581: [String] in OldSpace: #height:
        1838 (const data field 1)
    0x23712865: [String] in OldSpace: #experience: 0x237125f9
        <String[4]: #good> (const data field 2)
    0x23714515: [String] in OldSpace: #cost: 0x23714525
        <String[16]: #one arm, one leg>
        (const data field 3) properties[0]
 }
 ...
{name: "Wendelstein", height: 1, experience: "good", cost: "one arm, one leg"}
d8>

Вы можете заметить, что у нас 4 свойства, все помечены как const. Первые 3 находятся внутри объекта, а последнее в properties[0], что означает первую ячейку в хранилище свойств. Давайте посмотрим:

d8> %DebugPrintPtr(0x2f94aecd)
DebugPrint: 0x2f94aecd: [PropertyArray]
 - map: 0x41942be9 <Map>
 - length: 3
 - hash: 0
         0: 0x23714525 <String[16]: #one arm, one leg>
       1-2: 0x41942329 <undefined>

Дополнительные свойства присутствуют на случай, если вы вдруг захотите их добавить.

Реальная структура

Мы могли бы сделать разные вещи на этом этапе, но поскольку вам, должно быть, действительно интересен V8, раз вы дочитали до этого места, я хотел бы попробовать нарисовать реальные структуры данных, которые мы используем, те, которые упоминались в начале: Map, DescriptorArray и TransitionArray. Теперь, когда у вас есть некоторое представление о концепции скрытых классов, создающихся за кулисами, вы можете привязать своё мышление кода к правильным именам и структурам. Попробую воспроизвести предыдущую схему в представлении V8. Для начала я нарисую DescriptorArrays, которые содержат список свойств для определенного Map. Эти массивы могут быть общими — ключ к этому в том, что сам Map знает, сколько свойств он может рассматривать в DescriptorArray. Поскольку свойства добавляются в порядке времени, эти массивы могут быть общими для нескольких Map. Смотрите:

Заметьте, что Map1, Map2 и Map3 все указывают на DescriptorArray1. Число рядом с полем "descriptors" в каждом Map указывает, сколько полей в DescriptorArray принадлежит этому Map. Таким образом, Map1, который знает только о свойстве "name", смотрит только на первое свойство, перечисленное в DescriptorArray1. А Map2 имеет два свойства, "name" и "height". Таким образом, он рассматривает первый и второй элементы в DescriptorArray1 (name и height). Такое разделение экономит много места.

Естественно, мы не можем делиться, когда есть разделение. Имеется переход от Map2 к Map4, если добавляется свойство "experience", и к Map3, если добавляется свойство "prominence". Вы можете увидеть, как Map4 и Map5 разделяют DescriptorArray2 таким же образом, как DescriptorArray1 использовался тремя Maps.

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

Диаграмма вознаграждает усердное изучение. Вопрос: что произойдет, если новое свойство "rating" будет добавлено после "name" вместо перехода к "height" и другим свойствам?

Ответ: Map1 получит настоящий TransitionArray, чтобы отслеживать разветвление. Если добавляется свойство height, мы должны перейти к Map2. Однако, если добавляется свойство rating, мы должны перейти к новой карте, Map6. Этой карте потребуется новый DescriptorArray, упоминающий name и rating. У объекта на этом этапе есть дополнительные свободные слоты (используется только один из трех), поэтому свойству rating будет выделен один из этих слотов.

Я проверил свой ответ с помощью %DebugPrintPtr() и нарисовал следующую диаграмму:

Не нужно умолять меня остановиться, я вижу, что это верхний предел таких диаграмм! Но, думаю, вы можете понять, как движутся части. Представьте, что после добавления этого суррогатного свойства rating мы продолжили с height, experience и cost. Ну, нам пришлось бы создавать карты Map7, Map8 и Map9. Так как мы настаивали на добавлении этого свойства в середину установленной цепочки карт, мы будем дублировать большую часть структуры. У меня не хватает духа сделать этот рисунок -- хотя если вы отправите его мне, я добавлю его в этот документ :).

Я использовал удобный проект DreamPuf для легкого создания диаграмм. Вот ссылка к предыдущей диаграмме.

TurboFan и неизменяемые свойства

До сих пор все эти поля помечены в DescriptorArray как const. Давайте поиграем с этим. Запустите следующий код на сборке с диагностикой:

// запустите как:
// d8 --allow-natives-syntax --no-lazy-feedback-allocation --code-comments --print-opt-code
function Peak(name, height) {
  this.name = name;
  this.height = height;
}

let m1 = new Peak("Matterhorn", 4478);
m2 = new Peak("Wendelstein", 1838);

// Убедитесь, что slack tracking завершилась.
for (let i = 0; i < 7; i++) new Peak("blah", i);

m2.cost = "одна рука, одна нога";
function foo(a) {
  return m2.cost;
}

foo(3);
foo(3);
%OptimizeFunctionOnNextCall(foo);
foo(3);

Вы получите вывод оптимизированной функции foo(). Код очень короткий. В конце функции вы увидите:

...
mov eax,0x2a812499          ;; объект: 0x2a812499 <String[16]: #одна рука, одна нога>
mov esp,ebp
pop ebp
ret 0x8                     ;; возвращает "одна рука, одна нога"!

TurboFan, будучи хитрым разработчиком, просто напрямую вставил значение m2.cost. Ну как вам это!

Конечно, после последнего вызова foo() вы могли бы вставить эту строку:

m2.cost = "бесценно";

Как вы думаете, что произойдет? Одно ясно, мы не можем позволить foo() оставаться неизменным. Оно будет возвращать неправильный ответ. Перезапустите программу, но добавьте флаг --trace-deopt, чтобы вас уведомили, когда оптимизированный код будет удален из системы. После вывода оптимизированного foo() вы увидите такие строки:

[пометка зависимого кода 0x5c684901 0x21e525b9 <SharedFunctionInfo foo> (opt #0) для деоптимизации,
    причина: field-const]
[деоптимизация помеченного кода во всех контекстах]

Вау.

Если принудительно провести повторную оптимизацию, то вы получите код, который не так хорош, но все равно значительно выигрывает благодаря описанной структуре Map. Помните с наших диаграмм, что свойство cost является первым свойством в хранилище свойств объекта. Ну, оно могло потерять свое обозначение const, но мы все еще имеем его адрес. Фактически, в объекте с картой Map5, что мы определенно проверили, глобальная переменная m2 по-прежнему его имеет, мы только должны--

загрузить хранилище свойств, и
прочитать первый элемент массива.

Давайте посмотрим на это. Добавьте этот код ниже последней строки:

// Принудительная повторная оптимизация foo().
foo(3);
%OptimizeFunctionOnNextCall(foo);
foo(3);

Теперь посмотрите на произведенный код:

...
40  mov ecx,0x42cc8901          ;; объект: 0x42cc8901 <Peak map = 0x3d5873ad>
45  mov ecx,[ecx+0x3]           ;; Загрузить хранилище свойств
48  mov eax,[ecx+0x7]           ;; Получить первый элемент.
4b  mov esp,ebp
4d  pop ebp
4e  ret 0x8                     ;; вернуть его в регистр eax!

Ну что ж. Это именно то, что мы сказали должно произойти. Возможно, мы начинаем понимать.

TurboFan также достаточно умен, чтобы деоптимизировать, если переменная m2 когда-либо изменится на другой класс. Вы можете увидеть последнюю оптимизированную деоптимизацию кода снова с чем-то забавным, например:

m2 = 42;  // хех.

Куда двигаться дальше

Множество вариантов. Миграция карты. Режим словаря (он же "медленный режим"). Здесь много всего, что можно исследовать, и надеюсь, вы будете наслаждаться этим так же, как я -- спасибо за чтение!

Зачем нужны скрытые классы?​

Пример​

Реальная структура​

TurboFan и неизменяемые свойства​

Куда двигаться дальше​

Зачем нужны скрытые классы?

Пример

Реальная структура

TurboFan и неизменяемые свойства

Куда двигаться дальше