Полиморфизм в SOOT

Оглавление

• Полиморфизм в SOOT
  • Оглавление
  • Введение
  • Идея: диспетчеризация через тип
  • Методы у типов в SOOTC
  • Тип basic и информация о типе в рантайме
  • Почему SID, а не указатель
  • Инструкция CallMethod
  • Пример: (-> b len) от Lisp до ассемблера
  • Цена и что мы получили
  • Выводы

Введение

В играх полиморфизм нужен не ради красоты иерархий. Один и тот же вызов (-> entity update) должен работать и для игрока, и для NPC, и для двери, и для триггера. Код, который его вызывает, не знает, что перед ним: это знает сам объект.

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

SOOTC (компилятор SOOT) реализует такую схему. В статье рассказано, почему методы у структур сами по себе полиморфизма не дают, зачем нужен тип basic, почему в заголовке объекта лежит SID, а не указатель, и почему для виртуального вызова пришлось добавить отдельную инструкцию CallMethod.

SOOT — самостоятельный проект. Подход вдохновлён публично описанными схемами диспетчеризации в игровых скриптовых системах (в том числе в играх Naughty Dog и в проекте OpenGOAL). Реализация и формат данных собственные, совместимость с этими проектами не является целью. Названия игр и проектов принадлежат их правообладателям.

Идея: диспетчеризация через тип

Схема, которую использует SOOTC, устроена так:

• у каждого объекта, который может участвовать в полиморфном вызове, в заголовке лежит информация о его типе;
• у каждого типа есть таблица методов: отображение method_id → реализация;
• вызов метода — это четыре шага: прочитать тип из заголовка, найти таблицу, взять реализацию по method_id, вызвать её.

Этого достаточно для полиморфизма, важного в игре: код не знает, что за объект перед ним, а нужная реализация находится по типу.

Методы у типов в SOOTC

SOOTC позволяет объявлять методы у структур:

(deftype my-basic (basic)
  ((x float) (y float) (z float) (w float))
  (:methods (len (my-basic) int)))

(defmethod len my-basic ((self my-basic)) 4)

На первый взгляд это ООП: есть тип, у типа есть метод, метод реализуется отдельно. Но сам по себе deftype полиморфизма не даёт. Причина простая: для обычной структуры компилятор всегда знает точный тип значения и поэтому знает, какую именно реализацию вызвать. Если написать:

(deftype vec3 (structure) ((x float) (y float) (z float))
  (:methods (len (vec3) float)))

(defmethod len vec3 ((self vec3)) 3.0)

то (-> v len) для v : vec3 — это статический вызов vec3-len. Компилятор знает точный тип v и точный method_id и генерирует прямые LookupPointer и Call. Никакой таблицы и никакой косвенности. Для structure-типов это правильно и быстро.

Полиморфизм начинается там, где компилятор не знает точный тип: где obj — «что-то, у чего есть метод len», а что именно, определится только во время выполнения. Для этого нужен базовый тип, у которого в заголовке лежит информация о типе объекта.

Тип basic и информация о типе в рантайме

В SOOTC есть встроенный тип basic. Все типы, которые участвуют в полиморфном вызове, наследуются от него:

(deftype my-basic (basic) ((x float) (y float) (z float) (w float)) ...)

basic устроен так: первые 8 байт любого объекта, производного от basic, — это идентификатор его типа в рантайме. Это не поле, которое объявляет пользователь, а неявное поле, которое вставляет компилятор. TypeSystem регистрирует его при инициализации:

// basic has one implicit field: the runtime type tag.
add_field_to_type(basic_type, "type", make_typespec("sid64"));

Тип my-basic наследует это поле, и все его экземпляры начинаются с 8 байт, в которых лежит sid64 типа my-basic. Поля, объявленные пользователем (x, y, z, w), идут после:

my-basic layout:
  offset 0   : type (sid64, implicit)
  offset 8   : x (float)
  offset 12  : y (float)
  offset 16  : z (float)
  offset 20  : w (float)
  total size : 24

Когда создаётся объект:

(define b (new 'heap 'my-basic :x 1.0 :y 2.0 :z 3.0 :w 4.0))

NewNode::emit для типа, производного от basic, сначала пишет в первые 8 байт SID("my-basic"), а потом инициализирует поля:

; allocate("heap", "my-basic") -> r3
CallFf   r3, r0, 2
; r3[0..8] = SID my-basic
LoadStaticI64Imm r4, <sid my-basic>
StoreI64 r3, r4, 0
; r3[8..12] = 1.0
IAddImm  r5, r3, 8
LoadStaticFloatImm r6, <1.0>
StoreFloat r5, r6, 0
; ... y, z, w

Теперь любой код, у которого есть указатель на b, может прочитать b[0..8] и узнать, что это my-basic. Это и есть основа полиморфизма.

Почему SID, а не указатель

В публично описанной реализации GOAL и OpenGOAL информация о типе в заголовке объекта — это указатель на структуру типа. Указатель быстрее: одно чтение вместо двух (чтение поля и поиск по SID). Но у него есть слабое место: он указывает на конкретный адрес в памяти.

В SOOT модули можно загружать, выгружать и перезагружать. Если бы в заголовке объекта лежал указатель на SsType, то после перезагрузки модуля новый SsType оказался бы по другому адресу, а все ранее созданные объекты продолжали бы указывать на старый. Поэтому в заголовке лежит SID (sid64, хэш имени типа). Он не меняется при перезагрузке и не зависит от адресов. В момент вызова SID превращается в SsType* через Globals:

const sid64 type_sid = *static_cast<const sid64 *>(obj_ptr);
const StringId type_name(type_sid);
void *type_ptr = globals->find_symbol_ptr(type_name);
auto *type = static_cast<SsType *>(type_ptr);

Это дороже на одно чтение, зато:

• модуль можно выгрузить и загрузить снова: SID остаётся прежним;
• модуль можно обновить: новый SsType с тем же SID заменяет старый в Globals, и все объекты, созданные до обновления, видят новый набор методов;
• реализации методов можно менять, не пересоздавая объекты.

Выбор такой: чуть медленнее, но переживает перезагрузку модуля, вместо «быстро, но хрупко».

Инструкция CallMethod

Нужна инструкция, которая делает три вещи:

1. берёт указатель на объект;
2. читает из заголовка SID и превращает его в SsType*;
3. вызывает SsType::m_pMethods[method_id].m_pLambda.

method_id известен на этапе компиляции: компилятор видит (-> obj len), знает, что len — метод с id = 9 у my-basic и у всех его наследников. Значит, id — константа, которую можно положить в регистр.

В инструкции три поля (a, b, c). Поле a — регистр результата, поле c — количество аргументов, включая получателя (receiver). Остаётся одно поле b, а входов для вызова два: объект и method_id.

Эту проблему снимает соглашение о вызовах. Получатель, как и первый аргумент любого вызова, лежит в первом регистре аргументов (r24), поэтому передавать его отдельным операндом не нужно. В поле b указывается регистр, в котором лежит method_id. Формат инструкции не расширяется и диапазон полей не страдает. method_id лежит в регистре, а не в непосредственном значении, потому что он может быть большим (до нескольких сотен).

Пример: (-> b len) от Lisp до ассемблера

Пользователь пишет:

(defmethod len my-basic ((self my-basic)) 4)
(define b (new 'heap 'my-basic :x 1.0 :y 2.0 :z 3.0 :w 4.0))
(-> b len)

Шаг 1: defmethod.

defmethod len my-basic компилируется в FunctionNode с именем my-basic-len, у которого один параметр self : my-basic и тело (return 4). NodeBuilder::build_defmethod регистрирует метод в TypeSystem:

MethodInfo info = m_ts.lookup_method(type_name, method_name);
m_ts.define_method(type_name, method_name, info.type, ...);

info.id для len равен 9: индексы 0–8 заняты девятью встроенными методами basic (new, delete, print, inspect, length, asize-of, copy, relocate, mem-usage). Значит, len — это m_pMethods[9].

Шаг 2: define b.

NewNode::emit для my-basic генерирует код, который мы видели выше: allocate, запись SID типа в [0..8], запись x, y, z, w в [8..24]. Результат — указатель в куче, который сохраняется в слоте b через StoreGlobalNode:

LookupPointer r13, <SID b>
StorePointer  r13, r3, 0    ; slot_b = pointer to b

Шаг 3: (-> b len).

NodeBuilder::build_deref видит (-> b len), определяет, что b — это my-basic, а len — метод с id = 9, и что my-basic производен от basic. Проверка should_use_virtual_methods(my-basic, 9) возвращает true. Создаётся MethodCallNode с m_method_id = 9, объект — VariableNode b.

MethodCallNode::emit:

; 1. получатель (b) в r24 как первый аргумент
LookupPointer     r0, <SID b>    ; slot_b
LoadPointer       r1, r0         ; b = *slot_b
Move              r24, r1        ; arg0 = receiver

; 2. method_id в регистр
LoadStaticI64Imm  r2, <9>

; 3. виртуальный вызов: dst = r3, method_id в r2, argc = 1
CallMethod        r3, r2, 1

; 4. вернуть результат
Return            r3

Что делает CallMethod в VM:

case Opcode::CallMethod: {
    // a = dst, b = регистр с method_id, c = argc
    // receiver = r24 (первый аргумент, фиксированное смещение)
    Variant &receiver = current_frame->get_argument(0);
    Variant &method_id_reg = current_frame->get_register(instr.b);

    // 1. Читаем SID из заголовка объекта.
    const sid64 type_sid = *static_cast<const sid64 *>(receiver.get_ptr());

    // 2. Превращаем SID в SsType* через Globals.
    const StringId type_name(type_sid);
    auto *type = static_cast<SsType *>(globals->find_symbol_ptr(type_name));

    // 3. Берём реализацию по method_id.
    i64 idx = method_id_reg.get_i64();
    ScriptLambda *lambda = static_cast<SsMethod *>(type->m_pMethods)[idx].m_pLambda;

    // 4. Вызываем.
    push_call_frame(lambda, instr.a, instr.c, mode);
    break;
}

Шаг 4: my-basic-len.

FunctionNode my-basic-len скомпилирован в:

Move              r0, r24          ; self = arg0
LoadStaticI64Imm  r1, <4>          ; return 4
Return            r1

Результат: 4. CallMethod кладёт его в r3, и Return r3 возвращает значение вызывающему.

Цена и что мы получили

Архитектура не идеальна. Цена — два дополнительных обращения на каждый виртуальный вызов:

1. чтение SID из заголовка объекта (вместо прямого указателя на таблицу методов);
2. поиск SsType* по SID в Globals (хэш-таблица).

Точных измерений у меня пока нет, поэтому я не буду называть цифры: виртуальный вызов заведомо дороже статического, но для скриптов игры это приемлемо. Скрипты вызываются не в плотном цикле, а в логике на тик, где накладные расходы теряются на общем фоне. Для числодробительных задач никто не запрещает писать в процедурном стиле, например (defun my-len (v) ...), и тогда платы нет.

Зато получается:

• полиморфизм: (-> obj method) работает для любого объекта, производного от basic, независимо от модуля, в котором он создан;
• перезагрузка модулей: обновили SsType, и все существующие объекты видят новый набор методов (это по замыслу; часть сценариев, например переопределение метода в другом модуле, ещё не покрыта тестами, см. статус проекта);
• подмена реализаций без пересоздания объектов;
• предсказуемость во времени: вызов не требует аллокаций и блокировок, а method_id известен при компиляции, поэтому поиск по имени метода не нужен (поиск идёт только по имени типа).

Это честное инженерное решение в духе SOOT: простое, работающее, с понятной ценой.

Выводы

1. Полиморфизм в SOOTC не сводится к «методам у структур». deftype сам по себе его не даёт: компилятор знает точный тип структуры, поэтому для structure-типов используется статический вызов.

2. Полиморфизм начинается с типа basic: в его заголовке лежит sid64 типа в рантайме, и компилятор может генерировать CallMethod, не зная точный тип объекта.

3. SID вместо указателя — сознательный выбор в пользу перезагружаемости модулей. Схема, описанная для GOAL и OpenGOAL, выигрывает одно чтение за счёт указателя, а SOOTC использует SID и получает возможность обновлять типы на лету.

4. CallMethod решает проблему нехватки операндов соглашением о вызовах: получатель всегда в первом регистре аргументов, а в поле b лежит регистр с method_id.

5. Цена: два дополнительных обращения на каждый виртуальный вызов. Для игровых скриптов это приемлемая плата за полиморфизм.

6. Решение не идеально, но честно: простые механизмы, явная цена, никакой магии. И оно работает, а для инженерии это важнее элегантности.

Статус проекта