Как язык Аргентум делает быстрый dynamic_cast и диспетчеризацию методов интерфейсов четырьмя инструкциями процессора

Зачем вообще искать методы в рантайме

Полиморфизм - один из трёх столпов объектно-ориентированного программирования  - требует, чтобы объекты разных классов по-разному реагировали на одни и те же запросы. Например, вызов метода to_string у объекта Animal и объекта Engine будет приводить к кардинально разным результатам. В общем случае, имея ссылку на объект, мы не знаем точный код который будет реагировать на вызов to_string у объекта по ссылке.

Получается, что код приложения и runtime-библиотека языка должны найти правильную точку входа в правильный метод соответствующий этому классу и методу. 

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

Как вызываются виртуальные методы

Для вызова виртуального метода компилятор строит таблицы указателей на методы и применяет разные алгоритмы вычисления индексов в этих таблицах. Случай одиночного наследования и древовидной иерархии классов самый быстрый и прямолинейный.

Рассмотрим пример на псевдокоде немного напоминающем С++):

struct Base {
    virtual void a_method() { puts("hello from Base::a_method"); }
    // virtual ~Base(){}  // эта строка не нужна для псевдокода
};
struct Derived : Base {
    void a_method() override {
        puts("hello from Derived::a_method");
    }
    virtual void additional_method() { puts("hello from additional_method"); }
};
 
// Somewhere at the caller site
void some_function(Base& b) {
   b.a_method();                          // {1}
}

В строке {1} компилятор делает колдунство: В зависимости от настоящего типа объекта на который ссылается переменная b может вызываться или базовый Base::a_method или производный метод Derived::a_method. Это достигается с помощью таблиц указателей на методы и пары инструкций процессора. Например, для процессора x86-64 в Windows ABI этот код выглядит так (пардон за интеловский синтаксис):

mov rcx, b
mov rax, [rcx + offset_to_vmt_ptr]  ; {2}  offset_to_vmt обычно 0
call [rax + offset_to_a_method]     ; {3}

Этот код работает потому что где-то внутри объекта на который ссылается b существует невидимое поле, которое обычно называется vmt_ptr. Это указатель на статическую структуру данных которая содержит указатели на виртуальные методы этого класса.

В строке {2} мы достаем указатель на таблицу виртуальных методов и строке {3} мы загружаем адрес точки входа в метод и вызываем его.

Чтобы все работало, нам потребуются также две таблицы (по одной на каждый класс) с указателями на методы:

Base_VMT   dq Base_a_method
Drived_VMT dq Derived_a_method, Derived_added_method

Вся приведенная схема требует, чтобы где-то при создании любого экземпляра класса кто-то положил в поле vmt_ptr адрес одной из двух таблиц. Обычно это делается в конструкторе.

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

Сложное наследование

К сожалению в реальных приложениях каждый класс распадается на несколько ортогональных ролей (serializable, drawable, physical, collidable, evaluable), иногда роли образуют группы с другими ролями (SceneItem: drawable, collidable). И все эти роли, классы и группы не складываются в единую древовидную иерархию наследования классов: Не всякий графический элемент сериализуемый, но есть и такие. Не всякий элемент поддерживающий коллизии работает с физикой, но некоторые - да. Поэтому Все современные языки программирования так или иначе разрешили разные виды множественного наследования в своих иерархиях классов.

В Java, Swift, C# вы можете унаследовать реализацию от одного класса и реализовать множество интерфейсов. С++ разрешает множественное наследование хотя это и вносит дополнительную сложность, когда один и тот же базовый класс может быть унаследован по разным веткам, поэтому в языке появились виртуальные базовые классы. Rust реализует множественное наследование как реализацию трейтов. Go формально не использует термин наследование и заменяет его делегацией интерфейса и композицией состояния, но если это крякает как наследование... В общем, сегодня мы можем сказать что все современные языки программирования отступили от принципа одиночного наследования и древовидной организации классов.

Как сегодня реализуется вызов метода при сложном наследовании

В разных языках пошли разными путями:

В Swift и Rust ссылка на реализацию протокола/трейта - это структура,состоящая из двух сырых указателей - один указывает на структуру с данными, а другой на таблицу виртуальных методов (witness table in Swift, vtable in Rust). За счет удвоения размера каждой ссылки Rust и Swift позволяют вызывать методы интерфейсов с той же скоростью что и обычные виртуальные методы классов.

Go - тоже хранит каждую ссылку на интерфейс как два указателя, но строит таблицы методов динамически при первом использовании и складывает результаты в глобальный хеш-мап.

В Java и Kotlin при первом вызове метода производятся линейный поиск в списке реализованных интерфейсов, результат поиска кэшируется. Если в какой-то точке вызова встречается небольшое количество (1-2) разных классов, JIT компилятор строит специальный оптимизированный код диспетчера, но если появляется новый класс, происходит возврат к линейному поиску.

Пожалуй самый замороченный подход используется в C++: каждый экземпляр класса содержит множество указателей на таблицы виртуальных методов. Каждый каст к базовому классу или производному классу, если они не могут быть сведены в дерево, приводит к перемещению указателя по памяти, с тем чтобы указатель на объект приведенный к типу T указывал на таблицу виртуальных методов этого типа T в этом объекте. Это позволяет вызывать виртуальные методы с одинаковой скоростью и при одиночном и при множественном наследовании.

Каждый подход является компромиссом между занимаемой памятью, сложностью вызова метода и сложностью работы с указателями.

Подход Java/Kotlin позволяет оптимизировать прохождение бенчмарков, кешируя последние вызванные методы и выполнять "рантайм-девиртуализацию" там, где это возможно. Для общего случая настоящей динамической диспетчеризации сильно полиморфных методов интерфейсов все сводится к линейному поиску в списках имен интерфейсов. Это оправдано, если класс реализует один-два интерфейса, но в общем случае весьма затратно.

Go, Rust и Swift вызывают методы быстро, но за счет удвоения размера каждого указателя, что может быстро исчерпать регистровый файл, предназначенный для передачи параметров при вызовах методов и при работе с локальными/временными ссылками. А это в свою очередь приведет к разливу регистров в стек. К тому же это усложняет касты ссылок между типами (трейтами/протоколами/интерфейсами), которые в Swift делаются унаследованным из Objective C кодом динамической диспетчеризации (с поиском по словарям идентификаторов протоколов), а в Rust такой каст отсутствует вовсе и реализуется написанным вручную методами `as_trait_NNN`. Swift имеет механизм подавления виртуализации через инстанцирование шаблонной функции для каждой реализации протокола (ключевые слова "some" против "any") этот механизм не работает для настоящих полиморфных контейнеров. В Rust механизм подавления виртуализации включен постоянно и выключается ключевым словом "dyn". 

C++ не расходует дополнительную память в каждом сыром указателе, и непосредственно вызов метода при множественном наследовании так же быстр, как при одиночном наследовании, однако сложность никуда не делась: такой подход приводит к существенному усложнению структуры объекта, усложнению кода методов - нужны thunks, к усложнению кода конструкторов и всех операций приведения типов. В парадигме С++ эти операции не столь часты, их сложностью можно пренебречь, но если попытаться перенять этот подход в системах с интроспекцией, или автоматическим управлением памятью, то каждая операция с объектом требующая доступа к заголовку объекта, хранящему маркерные слова, счетчики и флаги потребуют static_cast<void*> который во-первых, не бесплатен, во-вторых, несовместим с виртуальным наследованием. А такая операция потребуется при каждом копировании и удалении ссылки на объект, или при каждом сканировании объекта в случае GC. Именно поэтому в С++ смарт-поинтеры хранят отдельный указатель на счетчики и маркеры, расходуя память совсем как в Rust/Swift. Кстати, безопасный dynamic_cast в C++ требует поиска в RTTI данных, то есть по сложности сравним с таковым в Swift/Java/Go.

Подводя итог раздела - проблемы диспетчеризации методов при множественном наследовании есть, и существующие решения оставляют желать лучшего.

Подход Аргентума

Пример программы на Аргентуме с классами и интерфейсами (синтаксис напоминает Java)

//
// Объявляем какой-то интерфейс
//
interface Drawable {
    width() int;
    height() int;
    paint(c Canvas);
}

//
// Реализуем этот интерфейс в каком-нибудь классе
//
class Rectangle {
    + Drawable{
        width() int { right - left }
        height() int { bottom - top }
        paint(c Canvas) {
            c.setFill(color);
            c.drawRect(left, top, right, bottom);
        }
    }
    + Serializable { ... }  // Реализуем еще...
    + Focusable { ... }    // ...несколько интерфейсов
    left = 0;       // Поля
    right = 0;
    top = 0;
    bottom = 0;
}

// Создаем экземпляр.
r = Rectangle;

// Вызываем методы интерфейса
w = Window.initCentered("Hello", r.width(), r.height());
r.paint(w);

В точке вызова r.paint(w); компилятор построит код:

; rdx - pointer to `w`
; rcx - pointer to `r`
mov rax, Drawable_interface_id + Drawable_paint_method_index
call [rсx]

У каждого класса первое поле - это указатель на диспетчерскую функцию. У нашего Rectangle эта функция будет такой:

Rectangle_dispatch:
	movzx r10, ax
	pext rax, rax, Rectangle_magic_number
	mov rax, Rectangle_interface_table[rax*8]
	jmp [rax + r10*8]

Не все современные процессоры умеют в pext, поэтому пока заменяем на bextr или:

    and rax, Rectangle_magic_mask
    shr rax, Rectangle_magic_offset

Кроме диспетчерской функции, Rectangle будет иметь набор таблиц:

Rectangle_interface_table:
    dq Rectangle_Drawable_method_table
    dq empty
    dq Rectangle_Serializable_method_table
    dq Rectangle_Focusable_method_table

Rectangle_Drawable_method_table:
    dq Rectangle_Drawable_width   ; method entry points
    dq Rectangle_Drawable_height
    dq Rectangle_Drawable_paint
Rectangle_Serializable_method_table dq ...
Rectangle_Focusable_method_table    dq ...

Как и почему это работает

На стадии компиляции каждый интерфейс получает случайно выбранный уникальный 48-битный идентификатор (он хранится в 48 битах 64-битного машинного слова с нулями в младших 16 битах - для индекса метода).

При вызове метода интерфейса вызывающая сторона вызывает диспетчер корректного класса, передавая в качестве параметра идентификатор интерфейса и 16-битный индекс метода в интерфейсе.

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

Если интерфейс один, диспетчер пропускает выбор интерфейса и сразу передает управление по индексу метода.

MyClass1_dispatcher:
	movzx rax, ax
    jmp MyClass1_InterfaceX_methods[rax*8]

Если класс реализует два интерфейса, их идентификаторы гарантировано будут различаться одним битом в одном из 48 разрядов их идентификаторов. Задача компилятора найти этот разряд и построить диспетчер, который проверяет этот бит:

MyClass2_dispatcher:
	movzx r10, ax              ; забираем индекс метода в r10
	shr rax, BIT_POSITION  ; можно заметить одной ...
	and RAX, 1             ; ...инструкцией pext/bextr
    ; загружаем указатель на одну из двух таблиц методов
	mov rax, MyClass2_itable[rax*8]
	jmp [rax + r10*8]      ; переходим к началу метода
MyClass2_itable:
	dq MyClass2_InterfaceX_mtable
	dq MyClass2_InterfaceY_mtable
MyClass2_InterfaceX_mtable:
	dq MyClass2_InterfaceX_methodA
	dq MyClass2_InterfaceX_methodB
MyClass2_InterfaceY_mtable:
	dq MyClass2_InterfaceY_methodA

В случае трёх методов нам понадобится двухбитный селектор. При выборе трёх случайных 48-битных чисел в среднем будет присутствовать 17.6 уникальных селекторов из двух смежных битов. Таким образом, вышеупомянутый подход будет работать с очень большой вероятностью. Большее количество интерфейсов потребует большего размера селектора.

Пример:

Допустим у нас есть класс, реализующий пять разных интерфейсов Идентификаторы этих интерфейсов имеют уникальную последовательность из трех бит по смещению 4.

Диспетчер такого класса будет иметь вид:

class_N_disp:
   movzx r10, ax
   shr rax, 4
   and rax, 7
   mov rax, class_N_itable[rax*8]
   jmp [rax + r10*8]
class_N_itable dq clN_IE, clN_IA, clN_IC, clN_IB, empty, empty, empty, clN_ID
clN_IE dq classN_interfaceIE_method1...
clN_IA...

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

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

• Используя более широкие таблицы (+1 бит)

• Или разрешив селекторам не быть непрерывными  

• Или введя новые уровни таблиц.

Широкие таблицы

Пример класса с восемью интерфейсами:

Среди идентификаторов интерфейсов нет 3-битного уникального селектора, но есть 4-битный в позиции 1.

За счет роста размера таблицы на в среднем 15 машинных слов мы получаем значительно лучшие вероятности нахождения подходящих селекторов вплоть до случая когда класс реализует 13 интерфейсов.

Разрывы в селекторах

Зачастую 48-битные идентификаторы интерфейсов содержат необходимые селекторы, но они находятся не в смежных битах. Идеальным вариантом было бы использовать инструкцию pext, которая может выдергивать произвольные биты из регистра по маске, но такая инструкция присутствует не во всех процессорах а кое-где исполняется за неприличные 300 тактов. Поэтому попробуем обойтись более дешевым и распространенным вариантом: N смежных бит + один отдельно стоящий бит.

Такая последовательность может быть выделена добавлением всего одной операции add:

Код, выполняющий такое выделение битов:

movzx r10, ax
and rax, 184h
add rax, 1ch  ; extra `add` instruction
shr rax, 5
mov rax, class_N_itable[rax*8]
jmp [rax + r10*8]

Одновременное использование дополнительной инструкции add и +1bit, позволяет уверенно строить диспетчеры для классов с 20+ интерфейсами, что превышает все практические сценарии диспетчеризаци.

Применение инструкции pext позволит еще поднять вероятности и уменьшить размеры таблиц не выходя за лимит четырех инструкций.

Вообще, задача поиска perfect hash function вычисляющейся с минимальными затратами ресурсов может иметь множество решений, но выделение битовой маски - является самым простым из них.

Как этот подход ускоряет dynamic_cast в языке Аргентум.

Каждая таблица методов в элементе с индексом 0 имеет метод, который сравнивает идентификатор интерфейса, использованного для диспетчеризации с реальным интерфейсом, реализованным этой таблицей, и возвращает или this-объект или null.

Если нам надо проверить наличие интерфейса X у какого-то объекта, мы вызываем метод с индексом 0 и 48-битным идентификатором интерфейса X у этого объекта.

Если интерфейс реализован в данном классе, то пройдя через выделение селектора и обращение к таблице интерфейсов, он попадет в метод с индексом 0, где его идентификатор совпадает с константной закодированной в этом методе. И поэтому для него метод с индексом 0 вернет this.

Если же интерфейс не реализован, то пройдя через выделение селектора, он попадает в единственную интерфейсную таблицу и единственный метод проверки, в котором он вообще мог быть. И следовательно единственное сравнение идентификаторов позволяет установить неудачность dynamic_cast-а.

Кстати, поэтому неиспользованные входы талиц интерфейсов заполнены не нулями, а ссылками на специальную таблицу методов с единственным элементом, который всегда возвращает nullptr.

Таким образом dynamic_cast к интерфейсу в Аргентуме всегда занимает 3 машинные инструкции и выполняется за 10 машинных инструкций:

• 3 инструкции вызова метода 0 указанного интерфейса с передачей параметра (может быть сокращен до 2)

• 4 инструкции диспетчера

• 3 инструкции метода0: сравнение, cmov, ret. (может быть сокращен до 2 если возвращать zf)

Сравнение с существующими языками

Любая ссылка в Аргентуме - это просто указатель на начало объекта. Одно машинное слово.

• По сравнению с Swift/Rust нет оверхеда связанного с указателями удвоенной ширины, нет переполнения и разливания регистровых файлов.

• По сравнению с static_cast в С++ нет оверхеда на перемещение this-указателя по объекту (с проверками на nullptr).

В каждом объекте есть только одно связанное с диспетчеризацией поле - это указатель на диспетчер.

• По сравнению с C++ нет оверхеда на многочисленные указатели на разные VMT и смещения виртуальных баз внутри данных объекта, и нет оверхеда при создании таких объектов.

По сравнению с простым вызовом виртуального метода с одиночным наследованием мы имеем четыре дополнительные инструкции.

• Это на порядки дешевле диспетчеризации в Java.

• Это близко к С++, в котором при множественном наследовании мы часто попадаем на необходимость корректировать this на величину смещения, хранящегося в VMT. Такая коррекция выполняется в С++ автоматически сгенерированным thunk-кодом, который сравним по сложности с четырьмя инструкциями диспетчера.

• Rust, Go и Swift выигрывают эти четыре инструкции в операции вызова, но проигрывают по две инструкции в каждой операции передачи, сохранения и загрузки ссылки из-за ее удвоенного размера. А эти операции выполняются чаще чем вызов.

Аргентум поддерживает dynamic_cast к интерфейсам, который занимает три машинные инструкции в коде программы и выполняется за 10 инструкций.

• Это на порядки дешевле, чем в Swift, Java, Go и dynamic_cast в C++.

• Rust такой инструкции не имеет.

Кстати, этот метод диспетчеризации подходит и для случая динамической дозарузки модулей, приносящих в AppDomain новые классы и интерфейсы:

• При добавлении нового интерфейса он получит следующий случайно сгенерированный уникальный 48-битный идентификатор. Перестраивать существующие диспетчеры и таблицы не потребуется.

• То же самое можно сказать про классы: их добавление в приложение потребует только генерации их собственных диспетчеров и таблиц, и не затронет уже существующие.

В отличие от многих других особенностей Аргентума обусловленных архитектурой языка (отсутствие утечек памяти, отсутствия GC, отсутствие шареного изменяемого состояния, гонок, дедлоков и т.д), описанный здесь способ диспетчеризации интерфейсных методов может быть позаимствован и применен в других языках.

Ссылки:

• Язык программирования Аргентум: https://aglang.org

• Windows demo: https://github.com/karol11/argentum/releases