Implementation of pure abstract classes and interfaces

Question

Although this isn't mandatory in the C++ standard, it seems the way GCC for example, implements parent classes, including pure abstract ones, is by including a pointer to the v-table for that abstract class in every instantiation of the class in question.

Naturally this bloats the size of every instance of this class by a pointer for every parent class it has.

But I've noticed that many C# classes and structs have lots of parent interfaces, which are basically pure abstract classes. I would be surprised if every instance of say Decimal, was bloated with 6 pointers to all it's various interfaces.

So if C# does do interfaces differently, how does it do them, at least in a typical implementation (I understand the standard itself may not define such an implementation)? And do any C++ implementations have a way of avoiding object size bloat when adding pure virtual parents to classes?

Answer 1

In C# and Java implementations, the objects typically have a single pointer to its class. This is possible because they are single-inheritance languages. The class structure then contains the vtable for the single-inheritance hierarchy. But calling interface methods has all the problems of multiple inheritance as well. This is typically solved by putting additional vtables for all implemented interfaces into the class structure. This saves space compared to typical virtual inheritance implementations in C++, but makes interface method dispatch more complicated – which can be partially compensated by caching.

E.g. in the OpenJDK JVM, each class contains an array of vtables for all implemented interfaces (an interface vtable is called an itable). When an interface method is called, this array is searched linearly for the itable of that interface, then the method can be dispatched through that itable. Caching is used so that each call site remembers the result of the method dispatch, so this search only has to be repeated when the concrete object type changes. Pseudocode for method dispatch:

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

(Compare the real code in the OpenJDK HotSpot interpreter or x86 compiler.)

C# (or more precisely, the CLR) uses a related approach. However, here the itables don't contain pointers to the methods, but are slot maps: they point to entries in the main vtable of the class. As with Java, having to search for the correct itable is only the worst case scenario, and it is expected that caching at the call site can avoid this search nearly always. The CLR uses a technique called Virtual Stub Dispatch in order to patch the JIT-compiled machine code with different caching strategies. Pseudocode:

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
}

The main difference to the OpenJDK-pseudocode is that in OpenJDK each class has an array of all directly or indirectly implemented interfaces, whereas the CLR only keeps an array of slot maps for interfaces that were directly implemented in that class. We therefore need to walk the inheritance hierarchy upwards until a slot map is found. For deep inheritance hierarchies this results in space savings. These are particularly relevant in CLR due to the way how generics are implemented: for a generic specialization, the class structure is copied and methods in the main vtable may be replaced by specializations. The slot maps continue to point at the correct vtable entries and can therefore be shared between all generic specializations of a class.

As an ending note, there are more possibilities to implement interface dispatch. Instead of placing the vtable/itable pointer in the object or in the class structure, we can use fat pointers to the object, that are basically a (Object*, VTable*) pair. The drawback is that this doubles the size of pointers and that upcasts (from a concrete type to an interface type) are not free. But it's more flexible, has less indirection, and also means that interfaces can be implemented externally from a class. Related approaches are used by Go interfaces, Rust traits, and Haskell typeclasses.

References and further reading:

• Interface dispatch. An expanded version of this answer, complete with diagrams and in-depth discussion.
• Wikipedia: Inline caching. Discusses caching approaches that can be used to avoid expensive method lookup. Typically not needed for vtable-based dispatch, but very desirable for more expensive dispatch mechanisms like the above interface dispatch strategies.
• OpenJDK Wiki (2013): Interface Calls. Discusses itables.
• Pobar, Neward (2009): SSCLI 2.0 Internals. Chapter 5 of the book discusses slot maps in great detail. Was never published but made available by the authors on their blogs. The PDF link has since moved. This book probably no longer reflects the current state of the CLR.
• CoreCLR (2006): Virtual Stub Dispatch. In: Book Of The Runtime. Discusses slot maps and caching to avoid expensive lookups.
• Kennedy, Syme (2001): Design and Implementation of Generics for the .NET Common Language Runtime. (PDF link). Discusses various approaches to implement generics. Generics interact with method dispatch because methods might be specialized so vtables might have to be rewritten.

Answer 2

Naturally this bloats the size of every instance of this class by a pointer for every parent class it has.

If by 'parent class' you mean 'base class' then this is not the case in gcc (nor I expect in any other compiler).

In the case of C derives from B derives from A where A is a polymorphic class, the C instance will have exactly one vtable.

The compiler has all the information it needs to merge the data in A's vtable into B's and B's into C's.

Here is an example: https://godbolt.org/g/sfdtNh

You will see that there is only one initialisation of a vtable.

I've copied the assembly output for the main function here with annotations:

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

Complete source for reference:

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);
}