Difference in VTBL in single inheritance and multiple inheritance

Question

I was taught in class that in the case of single inheritance the VTBL includes all of the of the virtual functions the class can respond to. The following image should illustrate this.

In multiple inheritance I was taught that the VTBL includes all of the virtual functions that were first defined in that class or the ones which have been overriden in this class. This means that at run time you've got to search for the right method implementation using the dispatch algorithm.

I'm not entirely sure why this difference exists. Why couldn't the VTBL in the case of multiple inheritance consist of all the virtual functions that the class can respond to (just like in the case of single inheritance)? This should speed up the process since we don't have to look for the method implementation at run time throughout the whole inheritance hierarchy.

Can anyone clarify this for me?

Edit: When I refer to the dispatch algorithm for multiple inheritance I'm referring to the following: Just to clarify: notice how we've got to traverse the hierarchy to search for the implementation rather than just going to the current class's VTBL and calling jumping to the method.

Answer 1

If you have to base class A and B of your multiply inherited object D, these have their own vtable layout and D needs to provide vtables which match the vtables of both A and B. Further, if another class derives from D and possibly from another similarly multiple inherited class, the same thing happens again, i.e., there are multiple vtables needed. They can't just simply be merged. As a result, multiply inherited objects typically have multiple vtables around and the compiler inserts code to first determine the function's correct vtable and then call it. I think the code determining the correct vtable based on a pointer to an object with multiple bases is just a simple addition or subtraction if the virtual function is not in a virtual base class and a look-up of the location of the virtual base class otherwise, i.e., there isn't anything really expensive being done but more than just an indirect call is needed.

Answer 2

Here's a translated example from published German notes by Scott Meyers. Consider

class B1 {
public:
     virtual void mf(); // may be overridden in derived classes
};

class B2 {
public:
     virtual void mf(); // may be overridden in derived classes
};

class D: public B1, public B2 {};

void g(B2 *pb2)
{
     pb2->mf(); // requires offset adjustment before calling mf?
} 

The pointer argument being passed to g() needs an offset adjustment is needed only if D overrides mf and pb2 really points to a D. What should a compiler do? When generating code for the call,

• It may not know that D exists. (that's the point of dynamic polymorphism: to be able to call future code without recompiling)
• It can’t know whether pb2 points to a D (it only knows that only at runtime).

Because polymorphic classes need to remain flexible against the unbounded set of possible future further derivations, the problem is typically solved by

• Creating special vtbls that handle offset adjustments.
• For derived class objects, adding new vptrs to these vtbls, one additional vptr for each base class after the first one.

Merging all the virtual functions into a single table would destroy that flexibility. Note that multiple "parallel" inheritance D: B1, B2 {}; is different from "stacked" inheritance D: M: B {};. The latter requires a single substitution chain, the former has two such chains and incompatible B1 and B2.