Диспетчеризация интерфейса

Динамическая и статическая диспетчеризация
Диспетчеризация интерфейса

Перевод/заметки Interface Dispatch

Вызвать виртуальный метод очень просто: вы находите слот метода в vtable и вызываете указатель функции. Легко! Ну, не совсем: интерфейсы представляют собой разновидность множественного наследования, и все быстро становится сложным.

Рассмотрим вызовы методов интерфейса в C++ (GCC), Java (OpenJDK/HotSpot), C# (CLR), Go и Rust.

Vtables

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

void call_the_method(StaticType& object) {
  // call target unknown at compile time
  object.method(42);
}

// will call DynamicType::method() at run time
DynamicType object {};
call_the_method(object)

Для этого необходимо, чтобы информация о реализациях методов хранилась внутри объекта. Обычно для этого используется VTable (virtual method table). По сути, это структура указателей на функции.

Если перепишем код на C, то вызов метода будет выглядеть следующим образом:

void call_the_method(StaticType* object) {
  object->vtable.StaticType_method(object, 42);
}

(Обратите внимание, что указатель объекта передается в качестве неявного аргумента this).

Эквивалентно структуре указателей на функции мы можем представить массив указателей на функции, где индекс должен быть известен во время компиляции:

void call_the_method(StaticType* object) {
  object->vtable[SLOT_StaticType_method](object, 42);
}

object указывает на vtable, который заполнен правильными реализациями методов для его динамического типа.

Обычно указатель vtable находится непосредственно в начале объекта, поэтому если мы проигнорируем систему типов и UB (как это может сделать компилятор), то получим что-то вроде:

void call_the_method(StaticType* object) {
    ((SLOT*)(*object) + SLOT_StaticType_method)(object, 42);
}

This is an image

Важно, чтобы все подклассы, такие как DynamicType, по-прежнему соответствовали object и vtable layout своих базовых классов, таких как StaticType. Это важно для абстракции: место вызова метода может быть скомпилировано еще до появления динамического типа!

Несколько базовых классов? Несколько VTables.

При множественном наследовании у нас есть несколько базовых классов, с которыми мы должны оставаться совместимыми. И каждый базовый класс ожидает, что указатель vtable будет находиться в самом начале объекта. Конечно, все они не могут быть в начале! Поэтому мы помещаем дополнительные указатели vtable в середину. Как следствие, апкастинг(upcasting) к другому базовому типу означает, что нам придется корректировать указатель объекта.

Рассмотрим иерархию классов в C++:

class FirstBase {
	int a;
	public:
		virtual int first_method();
};

class SecondBase {
	int b;
	public:
		virtual int second_method();
};

class Derived : public FirstBase, public SecondBase {
	int c;
	public:
		int first_method() override;
		int second_method() override;
};

Запустив g++ -fdump-class-hierarchy, мы получим вот такой загадочный результат:

Vtable for FirstBase
FirstBase::_ZTV9FirstBase: 3 entries
0     (int (*)(...))0
8     (int (*)(...))(& _ZTI9FirstBase)
16    (int (*)(...))FirstBase::first_method

Class FirstBase
   size=16 align=8
   base size=12 base align=8
FirstBase (0x0x7fb98760c960) 0
    vptr=((& FirstBase::_ZTV9FirstBase) + 16)

Vtable for SecondBase
SecondBase::_ZTV10SecondBase: 3 entries
0     (int (*)(...))0
8     (int (*)(...))(& _ZTI10SecondBase)
16    (int (*)(...))SecondBase::second_method

Class SecondBase
   size=16 align=8
   base size=12 base align=8
SecondBase (0x0x7fb98760c9c0) 0
    vptr=((& SecondBase::_ZTV10SecondBase) + 16)

Vtable for Derived
Derived::_ZTV7Derived: 6 entries
0     (int (*)(...))0
8     (int (*)(...))(& _ZTI7Derived)
16    (int (*)(...))Derived::first_method
24    (int (*)(...))-16
32    (int (*)(...))(& _ZTI7Derived)
40    (int (*)(...))SecondBase::second_method

Class Derived
   size=32 align=8
   base size=28 base align=8
Derived (0x0x7fb9874c82a0) 0
    vptr=((& Derived::_ZTV7Derived) + 16)
  FirstBase (0x0x7fb98760ca20) 0
      primary-for Derived (0x0x7fb9874c82a0)
  SecondBase (0x0x7fb98760ca80) 16
      vptr=((& Derived::_ZTV7Derived) + 40)

Здесь показаны классы и vtable со всеми смещениями. Обратите внимание, что vtable содержат не только слоты методов, но и две дополнительные записи:

Одна запись указывает на саму vtable. Это позволяет определять динамический тип объекта во время runtime (RTTI).
Другая запись содержит смещение от upcasted указателя this к исходному указателю this. Это необходимо для исправления (fix up) указателя объекта при вызове метода через SecondBase, если этот метод был реализован в классе Derived.

This is an image

Множественное наследование в стиле C++.

V: указатель vtable
O: смещение объекта
T: информация о типе во время выполнения (RTTI)
S: слот метода.

Что можно сказать об этом решении?

vtable является частью объекта, поэтому для передачи объектов достаточно простого указателя на объект.
Однако это не очень хорошо масштабируется при большом количестве базовых классов/интерфейсов: Каждый дополнительный базовый класс требует добавления к объекту еще одной vtable.
Upcasting не бесплатен и может изменить указатель объекта. Это может потребовать fix up в дальнейшем.
Вызовы виртуальных методов требуют трех уровней переадресации указателей и никаких ветвлений.
Все это сопряжено с небольшими, постоянными, но неизбежными накладными расходами.

itables в Java

Когда создавалась Java, они посмотрели на C++, сказали «нет, это слишком сложно» и сделали язык с одинарным наследованием. Но сложность не может полностью исчезнуть, ее можно только переместить. Поддержка наследования интерфейсов - это все равно разновидность множественного наследования. Как же удалось решить эту проблему?

Каждый объект Java имеет заголовок объекта(object header), который содержит указатель на его класс. Этот класс используется как vtable и применяется во время обычных вызовов виртуальных методов. Когда мы апкастим ссылку на объект в тип интерфейса, никаких изменений не происходит. Поэтому JVM не может использовать диспетчеризацию vtable для интерфейсных вызовов.

Для вызова виртуального метода нужен только индекс метода в vtable.

Для интерфейсных вызовов требуется ID интерфейса и индекс метода для vtable интерфейса, который называется itable.

Как же найти нужный itable? В HotSpot runtime буквально перебирает массив itables, пока не будет найден тот, который соответствует ID интерфейса (source: interpreter, x86 assembler).

В виде псевдокода:

// Dispatch SomeInterface.method
Method const* resolve_method(
    Object const* instance,
    Klass const* interface,
    uint itable_slot)
{
  Klass const* klass = instance->klass;

  for (Itable const* itable : klass->itables()) {
    if (itable->klass() == interface)
      return itable[itable_slot];
  }

  throw ...;  // class does not implement required interface
}

Таким образом, место вызова будет выглядеть так:

// SomeInterface object = ...;
// object.method(42);
Method* m = resolve_method(
    object, typeid(SomeInterface), SLOT_SomeInterface_method);
m(object, 42);

Диаграмма указателя этой структуры немного громоздка и может выглядеть следующим образом:

This is an image

Inline caching

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

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

// SomeInterface object = ...;
// object.method(42);

static Klass* cached_type = nullptr;
static Method* cached_method = nullptr;

// guard condition
if (LIKELY(object->klass == cached_type)) {
  // call the cached method
  cached_method(object, 42);
}
else {
  // patch this call site with the resolved type
  cached_type = object->klass;
  cached_method = resolve_method(
      object, typeid(SomeInterface), SLOT_SomeInterface_method);
  // call the patched method
  cached_method(object, 42);
}

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

В статье Википедии о Inline caching эта и другие связанные с ней техники рассматриваются более подробно.

Какова оценка этой диспетчеризации на основе itable с встроенным кэшированием? Мы должны различать наихудшее поведение (при промахах кэша и во время прогрева ВМ) и типичное поведение.

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

slotmaps в C#

В целом C# придерживается того же подхода, что и Java, но старается проводить более агрессивную оптимизацию. Например, диспетчеризацию интерфейсов в C# следует понимать в первую очередь через инлайн-кэширование (которое в CLR называется Virtual Stub Dispatch). Поиск метода в vtable является лишь стратегией последней надежды и обычно происходит только во время прогрева виртуальной машины.

У C# есть одно очень важное отличие от Java: способ реализации generics. В Java параметры типа стираются во время выполнения. ArrayList<Integer> - это то же самое, что и ArrayList<?> во время выполнения. В C# все иначе: для каждого набора параметров типа копируется структура класса, которая иногда специализируется для этих параметров. List и List<int> - это разные типы. Отношения между специализированным классом и общим классом похожи на наследование. В результате в памяти C# оказывается гораздо больше структур классов.

Разработчики C# отметили, что itables и массивы itable в стиле Java занимают много места, и искали способы их сжатия. В Java каждый класс, переопределяющий метод интерфейса, должен иметь собственную копию itable. CLR избегает этого с помощью более сложных структур vtable.

Вместо того чтобы использовать обычные itables, которые являются vtables для интерфейсов, CLR использует концепцию slot maps. В них хранится не указатель метода, а индекс в vtable. Преимущество заключается в том, что slot map не нужно переписывать при переопределении метода (или его специализации для дженериков) - достаточно обновить vtable. Это также позволяет заменить указатель метода на оптимизированную версию, поскольку обновлять нужно только vtable.

Псевдокод для диспетчеризации на основе slot map будет выглядеть следующим образом:

Method const* resolve_method(
    Object const* instance,
    Klass const* interface,
    uint interface_slot)
{
  Klass const* klass = instance->klass;

  // Walk all base classes to find slot map
  for (Klass const* base = klass; base != nullptr; base = base->base()) {
    for (SlotMap const* slot_map : base->slot_maps()) {
      if (slot_map->klass() == interface) {
        // Note the extra slot index indirection
        uint vtable_slot = slot_map[interface_slot];
        return klass->vtable[vtable_slot];
      }
    }
  }

  throw ...;  // class does not implement required interface
}

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

CoreCLR (2006): Virtual Stub Dispatch. In: Book Of The Runtime. Обсуждает slot maps и кэширование, чтобы избежать дорогостоящих поисков. Большая часть соответствующего кода находится в src/vm/methodtable.h и связанных с ним файлах.
Pobar, Neward (2009): SSCLI 2.0 Internals. В главе 5 книги подробно рассматриваются slot maps.
Kennedy, Syme (2001): Design and Implementation of Generics for the .NET Common Language Runtime. (PDF link).

Fat pointers

Где-то должен быть интерфейсный vtable. C++ помещает его в объект, Java - в класс. Но есть и третий вариант: мы можем отслеживать vtable с помощью указателя объекта:

This is an image

vtable в fat-указателе всегда содержит соответствующую vtable для текущего статического типа. Это имеет ряд интересных последствий. Например, виртуальный вызов теперь требуют на одну разыменованную ссылку на указатель меньше. Вызовы интерфейсов теперь достаточно эффективны, чтобы не требовать инлайнинга для получения сносной производительности (хотя он все еще может быть полезен).

game-changing преимуществом является то, что интерфейсы могут быть имплементированы и вне объекта. Интерфейсам не нужно знать заранее, когда реализуется класс. Поскольку компоновка объекта не затрагивается, мы можем реализовать интерфейсы даже для POD-типов и примитивных типов, таких как небоксовые целые числа! (Приведение к интерфейсу будет эффективно боксировать примитивный тип). И в принципе, можно предоставить несколько различных реализаций для каждой комбинации типа/интерфейса, с выбором одной реализации в месте апкаста.

Поэтому неудивительно, что эта стратегия используется, например, для интерфейсов в Go, в Rust dyn Traits и в некоторой степени в Haskell. Возможность реализовывать интерфейсы извне хорошо соответствует typeclasses в Haskell.

Если это так великолепно, почему все не используют это? Есть три общие проблемы:

fat-указатели - это не обычные указатели,
апкастинг может быть дорогим,
это может усложнить компилятор.

Накладные расходы на размер fat-указателей

Fat-указатель требует указателя vtable в дополнение к указателю данных, и поэтому он вдвое больше. Для перемещения ссылки на объект теперь требуется более одного регистра. Для хранения ссылки на объект нам нужно два машинных слова, поэтому, например, массив, содержащий ссылки на интерфейс, теперь вдвое больше. Но в этом массиве многие элементы, скорее всего, будут иметь один и тот же конкретный тип, а значит, мы теряем много места ради небольшого выигрыша. При таком допущении подходы, как в C# или Java, могут быть гораздо более эффективными с точки зрения памяти и, следовательно, кэша.

Накладные расходы на преобразование fat-указателя

Когда конкретный тип апкастится в интерфейсный тип, это больше не является бесплатной операцией (в Java это no-op, в C++ - максимум смещение указателя). Вместо этого нам нужно найти правильный vtable. Таким образом, часть затрат на динамическую диспетчеризацию была перенесена с места вызова на место приведения. Обычно это не является большой проблемой, так как конкретный тип статически известен в месте приведения, поэтому правильная vtable может быть найдена во время компиляции.

Немного интереснее обстоят дела с приведениями между интерфейсами (например, в Go) или при объединении нескольких interfaces/traits/typeclasses. Здесь нет элегантного решения.

В настоящее время Rust не разрешает использовать комбинации трейтов в объектах трейтов. В качестве обходного пути вам придется ввести adapter типы, оборачивающие объект, или добавить новый трейт, описывающий ваше использование.

Для приведения интерфейсов Go обращается к runtime library, которая ищет itable в глобальной хэш-таблице и создает новый itable, если в хэш-таблице его не оказалось. Для создания нового itable методы ищутся по имени в глобальной vtable конкретного типа. Это довольно гибко, но влечет за собой ужасающие затраты runtime, даже на «счастливом пути», где itable уже существует. Как только в дело вступают интерфейсы, Go становится больше похожим на Python, чем на C или C++.

Комментарий Russ Cox

Я не совсем понимаю, почему вы говорите, что это «ужасающие затраты на runtime». Ключевым моментом для Go было то, что в статически типизированном языке преобразования типов происходят гораздо реже, чем вызовы методов, поэтому работа по преобразованию типов на самом деле довольно дешевая. Кроме того, «счастливый путь» для преобразования интерфейс->интерфейс - это один поиск в хэш-таблице с использованием ключа, который является XOR двух значений, извлеченных из соответствующих типов (конкретного исходного типа и целевого интерфейса). Это дешево и не требует блокировки. Конечно, при первом выполнении преобразования необходимо создать таблицу, но все, что влияет на производительность, должно выполняться много-много раз, и только первое преобразование чего-то стоит. И даже это первое преобразование имеет O(n) по количеству методов.

Эмпирически, в наших рабочих системах в Google, где мы используем continuous profiling, на runtime.convI2I приходится менее 0,007% (то есть менее 70ppm) нашего процессорного времени, затрачиваемого на выполнение программ на Go. По крайней мере, для нас это не является «ужасающими затратами runtime».

Соображения по реализации компилятора

Наконец, fat-указатели могут усложнить разработку компилятора.

Во-первых, существует проблема ABI, связанная с тем, что интерфейсные типы (объекты) и обычные указатели имеют разные размеры. Обычно это не является проблемой, но, например, для C++ такая стратегия не подходит.

Из-за проблем с размером указателя мы можем захотеть использовать обычную диспетчеризацию vtable, как в C++/Java, для наследования классов и fat-указатели для наследования интерфейсов. Теперь компилятору нужно управлять двумя совершенно независимыми типами объектов. Однако в Java это уже происходит, поскольку вызовы интерфейсов используют другой опкод VM. (На самом деле спецификация Java явно предполагает реализацию с использованием fat-указателей).

Другой вопрос - как управлять информацией о типе при рефлексии и во время выполнения, если объект больше не содержит vtable, который можно использовать для определения его типа. Верно, что это больше не позволяет нам взять произвольный указатель и узнать, на какой тип объекта он ссылается. Но в этом и не должно быть необходимости: либо у нас есть простой указатель на статически известный тип, либо fat-указатель. vtable fat-указателя может содержать дополнительную информацию, например, ссылку на конкретный тип. Это может быть использовано для возврата от ссылочного типа к конкретному типу.

Заключение

Мы рассмотрели различные способы интерфейсных вызовов, что является разновидностью множественного наследования: хранение нескольких vtables для каждого объекта, как в C++, хранение itables в структуре класса, как в Java или C#, или хранение itables как части fat-указателя в Go или Rust.

Ни одно из этих решений по своей сути не лучше других. Все они добавляют некоторые накладные расходы во время runtime (пространство или время), и все они имеют последствия для семантики языка. В некоторых случаях накладные расходы могут быть амортизированы за счет кэширования.

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

Комментарии в Telegram-группе!

Vtables#

Несколько базовых классов? Несколько VTables.#

itables в Java#

Inline caching#

slotmaps в C##

Fat pointers#

Накладные расходы на размер fat-указателей#

Накладные расходы на преобразование fat-указателя#

Комментарий Russ Cox#

Соображения по реализации компилятора#

Заключение#

Vtables

Несколько базовых классов? Несколько VTables.

itables в Java

Inline caching

slotmaps в C#

Fat pointers

Накладные расходы на размер fat-указателей

Накладные расходы на преобразование fat-указателя

Комментарий Russ Cox

Соображения по реализации компилятора

Заключение