Реализация чистых абстрактных классов и интерфейсов

Хотя это не является обязательным в стандарте C ++, похоже, что GCC, например, реализует родительские классы, в том числе чисто абстрактные, путем включения указателя на v-таблицу для этого абстрактного класса в каждом экземпляре рассматриваемого класса. ,

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

Но я заметил, что многие классы и структуры C # имеют множество родительских интерфейсов, которые в основном являются чисто абстрактными классами. Я был бы удивлен, если бы каждый случай, скажем Decimal, был раздут с 6 указателями на все его различные интерфейсы.

Так что, если C # делает интерфейсы по-другому, как он это делает, по крайней мере, в типичной реализации (я понимаю, что сам стандарт может не определять такую ​​реализацию)? И есть ли у любых реализаций C ++ способ избежать раздувания размера объекта при добавлении чистых виртуальных родителей в классы?

В реализациях C # и Java объекты обычно имеют единственный указатель на свой класс. Это возможно, потому что это языки с одним наследованием. Структура класса тогда содержит vtable для иерархии с одним наследованием. Но вызов методов интерфейса имеет все проблемы множественного наследования. Обычно это решается добавлением дополнительных vtables для всех реализованных интерфейсов в структуру класса. Это экономит пространство по сравнению с типичными реализациями виртуального наследования в C ++, но усложняет диспетчеризацию метода интерфейса - что может быть частично компенсировано кэшированием.

Например, в JVM OpenJDK каждый класс содержит массив vtables для всех реализованных интерфейсов (vtable-интерфейс называется itable ). Когда вызывается метод интерфейса, этот массив ищется в линейном поиске для этого интерфейса, а затем метод может передаваться через этот интерфейс. Кэширование используется для того, чтобы каждый сайт вызова запоминал результат отправки метода, поэтому этот поиск нужно повторять только при изменении конкретного типа объекта. Псевдокод для отправки метода:

// 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
}

(Сравните реальный код в интерпретаторе OpenJDK HotSpot или компиляторе x86 .)

C # (или, точнее, CLR) использует связанный подход. Однако в данном случае itables не содержат указателей на методы, а являются картами слотов: они указывают на записи в основной vtable класса. Как и в случае с Java, поиск правильного itable - это только наихудший сценарий, и ожидается, что кэширование на сайте вызовов может избежать этого поиска почти всегда. CLR использует технику, называемую Virtual Stub Dispatch, для исправления JIT-скомпилированного машинного кода с помощью различных стратегий кэширования. псевдокод:

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()) {
    // I think the CLR actually uses hash tables instead of a linear search
    for (SlotMap const* slot_map : base->slot_maps()) {
      if (slot_map->klass() == interface) {
        uint vtable_slot = slot_map[interface_slot];
        return klass->vtable[vtable_slot];
      }
    }
  }

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

Основное отличие от OpenJDK-псевдокода состоит в том, что в OpenJDK каждый класс имеет массив всех прямо или косвенно реализованных интерфейсов, в то время как CLR сохраняет только массив карт слотов для интерфейсов, которые были непосредственно реализованы в этом классе. Поэтому нам нужно пройти иерархию наследования вверх, пока не будет найдена карта слотов. Для глубокой иерархии наследования это приводит к экономии места. Они особенно актуальны в CLR благодаря способу реализации обобщений: для обобщенной специализации структура класса копируется, и методы в основной таблице могут быть заменены специализациями. Карты слотов продолжают указывать на правильные записи vtable и поэтому могут быть разделены между всеми общими специализациями класса.

В завершение, есть больше возможностей для реализации диспетчеризации интерфейса. Вместо размещения указателя vtable / itable в объекте или в структуре класса мы можем использовать жирные указатели на объект, которые в основном являются (Object*, VTable*)парой. Недостаток состоит в том, что это удваивает размер указателей и что апкастинг (от конкретного типа к типу интерфейса) не является бесплатным. Но он более гибкий, имеет меньшую косвенность, а также означает, что интерфейсы могут быть реализованы извне из класса. Связанные подходы используются интерфейсами Go, чертами Rust и классами типов Haskell.

Ссылки и дальнейшее чтение:

• Википедия: встроенное кэширование . Обсуждаются подходы кеширования, которые можно использовать, чтобы избежать поиска дорогостоящих методов. Обычно не требуется для диспетчеризации на основе таблиц, но очень желательно для более дорогих механизмов диспетчеризации, таких как описанные выше стратегии диспетчеризации интерфейса.
• OpenJDK Wiki (2013): интерфейсные вызовы . Обсуждает itables.
• Побар, Ньюард (2009): SSCLI 2.0 Internals. В главе 5 книги подробно рассматриваются карты слотов. Никогда не был опубликован, но размещен авторами в своих блогах . С тех пор ссылка PDF переместилась. Эта книга, вероятно, больше не отражает текущее состояние CLR.
• CoreCLR (2006): отправка виртуальной заглушки . В: Книга времени выполнения. Обсуждает карты слотов и кэширование, чтобы избежать дорогостоящих поисков.
• Кеннеди, Сайм (2001): разработка и реализация обобщений для .NET Common Language Runtime . ( PDF ссылка ). Обсуждаются различные подходы к реализации дженериков. Обобщения взаимодействуют с диспетчеризацией методов, потому что методы могут быть специализированными, поэтому, возможно, придется переписывать таблицы.

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

Если под «родительским классом» вы имеете в виду «базовый класс», то в gcc это не так (как и в любом другом компиляторе).

В случае, когда C наследуется от B, наследуется от A, где A - полиморфный класс, экземпляр C будет иметь ровно одну vtable.

Компилятор имеет всю информацию, необходимую для слияния данных из v-таблицы A в B и B в C.

Вот пример: https://godbolt.org/g/sfdtNh

Вы увидите, что существует только одна инициализация vtable.

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

main:
        push    rbx

# allocate space for a C on the stack
        sub     rsp, 16

# initialise c's vtable (note: only one)
        mov     QWORD PTR [rsp+8], OFFSET FLAT:vtable for C+16

# use c    
        lea     rdi, [rsp+8]
        call    do_something(C&)

# destruction sequence through virtual destructor
        mov     QWORD PTR [rsp+8], OFFSET FLAT:vtable for B+16
        lea     rdi, [rsp+8]
        call    A::~A() [base object destructor]

        add     rsp, 16
        xor     eax, eax
        pop     rbx
        ret
        mov     rbx, rax
        jmp     .L10

Полный источник для справки:

struct A
{
    virtual void foo() = 0;
    virtual ~A();
};

struct B : A {};

struct C : B {

    virtual void extrafoo()
    {
    }

    void foo() override {
        extrafoo();
    }

};

int main()
{
    extern void do_something(C&);
    auto c = C();
    do_something(c);
}