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?

  • 1
    C# objects usually have quite a lot of metadata attached, maybe the vtables are not that big compared to that – max630 Jul 9 at 6:57
  • you could start with examining the compiled code with idl disassembler – max630 Jul 9 at 6:57
  • C++ does a significant fraction of it's "interfaces" statically. Compare IComparer to Compare – Caleth Jul 9 at 8:26
  • 4
    GCC, for example, uses a vtable table pointer (a pointer to a table of vtables, or a VTT) per object for classes with multiple base classes. So, each object has only a single extra pointer rather than the collection you're imagining. Perhaps that means in practice it's not a problem even when the code is poorly designed and there is a massive class hierarchy involved. – Stephen M. Webb Jul 9 at 15:09
  • 1
    @StephenM.Webb As far as I understood from this SO answer, VTTs are only used for ordering construction/destruction with virtual inheritance. They do not participate in method dispatch and don't end up saving any space in the object itself. Since C++ upcasts effectively perform object slicing, it is not possible to put the vtable pointer anywhere else but in the object (which for MI adds vtable pointers in the middle of the object). I verified by looking at g++-7 -fdump-class-hierarchy output. – amon Jul 9 at 18:39
up vote 31 down vote accepted

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:

  • 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.
  • Thanks @amon great answer looking forward to the extra details both on how Java and the CLR achieve this! – Clinton Jul 9 at 8:23
  • @Clinton I updated the post with some references. You can also read the source code of the VMs, but I found it difficult to follow. My references are a bit old, if you find anything newer I'd be quite interested. This answer is basically an excerpt of notes I had lying around for a blog post, but I never got around to publish it :/ – amon Jul 9 at 9:38
  • 1
    callvirt AKA CEE_CALLVIRT in CoreCLR is the CIL instruction that handles calling interface methods, if anyone wants to read more about how the runtime handles this setup. – jrh Jul 9 at 13:22
  • Note that the call opcode is used for static methods, interestingly callvirt is used even if the class is sealed. – jrh Jul 9 at 13:31
  • I had never thought about all this complexity. Makes me think that the fat-pointer approach used by "traits" has really nice benefits here. – Matthieu M. Jul 9 at 15:32

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.