C++ dynamic dispatch without vtables

Question

As far as I know, C++ standard doesn't require the dynamic dispatch to be implemented using virtual method tables (a.k.a. vtables). Nevertheless, I have gotten the impression that vtables are the de facto standard implementation. I wonder whether there are C++ compilers that use a different mechanism or at least allow a different mechanism.

Answer 1

The C++ standard places few constraints on the implementation of virtual functions and the calling mechanism. Since it does however list a lot of things that cannot be virtual, that in effect adds to the freedom.

From n3797 10.3/1:

Virtual functions support dynamic binding and object-oriented programming.

Then lots of stuff about what constitutes overriding and final overrider.

From 5.2.2/1:

Otherwise [function is virtual], its final overrider (10.3) in the dynamic type of the object expression is called; such a call is referred to as a virtual function call. [ Note: the dynamic type is the type of the object referred to by the current value of the object expression...]

So the C++ standard defines a restricted kind of dynamic dispatch based on the dynamic type of the object, and nothing much else. As long as each object carries around a mechanism by which any virtual function can be called, everything else is up for grabs.

Yes, vtables are common but they are not the last word. They are a significant memory and speed cost, particularly for multiple inheritance. I can easily come up with a mechanism that is not a vtable but is just as fast and uses less object memory, but takes more space in code or static memory. Various researchers have devised a wealth of techniques, and some have even been patented. There are techniques that provide better type safety, or better branch prediction or even faster lookup. I don't see much point providing links -- you can easily find them too.

But no, I am not aware of any production C++ compilers that use any of these mechanisms. Maybe it's time to think about one?