Some Ideas for Dynamic Vtables in D

In my last two posts, I’ve written about things I’d like to see added to the D programming language. The first is a non-fragile ABI, where you don’t need to recompile every subclasses when you’re changing the base class. The second is to implement a class extension system where you can attach new functions to existing classes without recompiling them. Now it’s time to look at how it can be implemented.

In the current vtable system, each D object begins with a pointer to the virtual function table (vtable for short), followed by the monitor pointer (used for locking), followed by the object’s members. The vtable contains a list of pointers to the implementations of virtual functions of that class in the order they were declared. When you call a virtual method, the compiler generate code that will grab the pointer to the function implementation at the right offset, and then call the function.

Then, when you create a subclass, a new vtable is created, starting with all the pointers from the base class’ vtable (except for overriden functions where the pointer is replaced with the new implementation) and added with pointers to any virtual function from the derived class.

Now, suppose that in a new version of a library we’re adding a function to the base class. This will offset by one all the function pointers in the vtable that comes after the function we’re adding. Since functions are added to the vtable in the lexical order they appear in the source file, we may avoid changing any of the base class’ offsets by placing the function at the end of the class declaration, but we can’t avoid offseting all of the derived class function pointers. This means that all derived classes need to be recompiled, and that’s the first thing we’ll try to avoid to allow libraries to keep their ABI compatible when adding functions to classes.

Note that this problem also occurs with member variables, which are accessed by adding an offset to the pointer to the start of the class. But that’s less of a problem since you can always reserve an opaque pointer for keeping the new data you may want in the future.

Interfaces are not the solution

D has the concept of interfaces. Implementing an interface in a class adds a new pointer to the memory layout of the object pointing to a special vtable for the interface. This makes interfaces more robust when it comes to the undesirable offset problem when creating a subclass in another library. That’s only true for interfaces declared final though, as any interface derived from another will break when you add a function to the base.

The problem with interfaces is that it doesn’t solve any part of this problem. If you build a library by exposing only interfaces, you can’t create a subclass of anything to override the default behaviour. At this rate, using static functions from the library owning the class is even safer: in both cases you lose the possibility of creating a subclass, but in the later at least you aren’t dependent on the lexical order of declaration in the interface source file.

Dynamic vtables

The solution I’m proposing would be to build vtables dynamically, either while linking, while initializing the program, or at runtime before the first use of a class. The vtable builder, whether it’s in the linker or in the runtime, needs two things for each class: a list of function names properly decorated with their argument types (so each function signature has a unique string) and a corresponding list of pointers. This allows the creation of the vtable at runtime.

Any code calling a virtual function would be required to check a global variable containing the vtable offset for the desired function. Once the vtable is built for a given class, all these global variables are set to the right offset for each function and the rest of the code can start using them to access the vtable.

Dynamic Indirect vtables

With another change, dynamic vtables could allows us to add functions at runtime while loading a new library containing some class extensions. When doing this, vtables of the extended classes and subclasses need to be extended to account for the new virtual functions being added. Once that is done, the global offsets variables are updated to match the new vtables, and subsequent calls to functions from that vtable will use the updated offsets.

This process could cause vtables to be relocated in memory. To solve this, we could fix each object’s vtable pointer using the GC type information about each memory block could be used.

Another approach to relocated vtables would be to have the vtable be accessed using a second level of indirection. This is what I call Dynamic Indirect: the object contains a pointer to a pointer to the vtable. When relocating the vtable, you update the second pointer and all objects are now using it.

A general problem to updating the virtual tables while the program is running has to do with thread safety. If any other thread is using the offset global variables or the vtable while you’re updating you could easily get a wrongly dispatched function call. I’m not sure how to solve this currently. Updating the vtable would need to be an atomic operation, but how to do this without imposing a lock at each function call?

Effects on performance

Calling each virtual function would require fetching the vtable offset from a global variable instead of it being part of the code.

If we add a second level of indirection for vtable pointers, then it means we’re fetching another value from a remote location. This value could be put in close proximity to the vtable offsets to improve cache efficiency though.

I’m currently preparing some benchmarks to check the performance impacts, but saving the result for another post as I’ll have a lot to say about them.