understanding vptr in multiple inheritance?

Question

I am trying to make sense of the statement in book effective c++. Following is the inheritance diagram for multiple inheritance.

Now the book says separate memory in each class is required for vptr. Also it makes following statement

An oddity in the above diagram is that there are only three vptrs even though four classes are involved. Implementations are free to generate four vptrs if they like, but three suffice (it turns out that B and D can share a vptr), and most implementations take advantage of this opportunity to reduce the compiler-generated overhead.

I could not see any reason why there is requirement of separate memory in each class for vptr. I had an understanding that vptr is inherited from base class whatever may be the inheritance type. If we assume that it shown resultant memory structure with inherited vptr how can they make the statement that

B and D can share a vptr

Can somebody please clarify a bit about vptr in multiple inheritance?

• Do we need separate vptr in each class ?
• Also if above is true why B and D can share vptr ?

Answer 1

Your question is interesting, however I fear that you are aiming too big as a first question, so I will answer in several steps, if you don't mind :)

Disclaimer: I am no compiler writer, and though I have certainly studied the subject, my word should be taken with caution. There will me inaccuracies. And I am not that well versed in RTTI. Also, since this is not standard, what I describe are possibilities.

1. How to implement inheritance ?

Note: I will leave out alignment issues, they just mean that some padding could be included between the blocks

Let's leave it out virtual methods, for now, and concentrate on how inheritance is implemented, down below.

The truth is that inheritance and composition share a lot:

struct B { int t; int u; };
struct C { B b; int v; int w; };
struct D: B { int v; int w; };

Are going to look like:

B:
+-----+-----+
|  t  |  u  |
+-----+-----+

C:
+-----+-----+-----+-----+
|     B     |  v  |  w  |
+-----+-----+-----+-----+

D:
+-----+-----+-----+-----+
|     B     |  v  |  w  |
+-----+-----+-----+-----+

Shocking isn't it :) ?

This means, however, than multiple inheritance is quite simple to figure out:

struct A { int r; int s; };
struct M: A, B { int v; int w; };

M:
+-----+-----+-----+-----+-----+-----+
|     A     |     B     |  v  |  w  |
+-----+-----+-----+-----+-----+-----+

Using these diagrams, let's see what happens when casting a derived pointer to a base pointer:

M* pm = new M();
A* pa = pm; // points to the A subpart of M
B* pb = pm; // points to the B subpart of M

Using our previous diagram:

M:
+-----+-----+-----+-----+-----+-----+
|     A     |     B     |  v  |  w  |
+-----+-----+-----+-----+-----+-----+
^           ^
pm          pb
pa

The fact that the address of pb is slightly different from that of pm is handled through pointer arithmetic automatically for you by the compiler.

2. How to implement virtual inheritance ?

Virtual inheritance is tricky: you need to ensure that a single V (for virtual) object will be shared by all the other subobjects. Let's define a simple diamond inheritance.

struct V { int t; };
struct B: virtual V { int u; };
struct C: virtual V { int v; };
struct D: B, C { int w; };

I'll leave out the representation, and concentrate on ensuring that in a D object, both the B and C subparts share the same subobject. How can it be done ?

1. Remember that a class size should be constant
2. Remember that when designed, neither B nor C can foresee whether they will be used together or not

The solution that has been found is therefore simple: B and C only reserve space for a pointer to V, and:

• if you build a stand-alone B, the constructor will allocate a V on the heap, which will be handled automatically
• if you build B as part of a D, the B subpart will expect the D constructor to pass the pointer to the location of V

And idem for C, obviously.

In D, an optimization allow the constructor to reserve space for V right in the object, because D does not inherit virtually from either B or C, giving the diagram you have shown (though we don't have yet virtual methods).

B:  (and C is similar)
+-----+-----+
|  V* |  u  |
+-----+-----+

D:
+-----+-----+-----+-----+-----+-----+
|     B     |     C     |  w  |  A  |
+-----+-----+-----+-----+-----+-----+

Remark now that casting from B to A is slightly trickier than simple pointer arithmetic: you need follow the pointer in B rather than simple pointer arithmetic.

There is a worse case though, up-casting. If I give you a pointer to A how do you know how to get back to B ?

In this case, the magic is performed by dynamic_cast, but this require some support (ie, information) stored somewhere. This is the so called RTTI (Run-Time Type Information). dynamic_cast will first determine that A is part of a D through some magic, then query D's runtime information to know where within D the B subobject is stored.

If we were in case where there is no B subobject, it would either return 0 (pointer form) or throw a bad_cast exception (reference form).

3. How to implement virtual methods ?

In general virtual methods are implemented through a v-table (ie, a table of pointer to functions) per class, and v-ptr to this table per-object. This is not the sole possible implementation, and it has been demonstrated that others could be faster, however it is both simple and with a predictable overhead (both in term of memory and dispatch speed).

If we take a simple base class object, with a virtual method:

struct B { virtual foo(); };

For the computer, there is no such things as member methods, so in fact you have:

struct B { VTable* vptr; };

void Bfoo(B* b);

struct BVTable { RTTI* rtti; void (*foo)(B*); };

When you derive from B:

struct D: B { virtual foo(); virtual bar(); };

You now have two virtual methods, one overrides B::foo, the other is brand new. The computer representation is akin to:

struct D { VTable* vptr; }; // single table, even for two methods

void Dfoo(D* d); void Dbar(D* d);

struct DVTable { RTTI* rtti; void (*foo)(D*); void (*foo)(B*); };

Note how BVTable and DVTable are so similar (since we put foo before bar) ? It's important!

D* d = /**/;
B* b = d; // noop, no needfor arithmetic

b->foo();

Let's translate the call to foo in machine language (somewhat):

// 1. get the vptr
void* vptr = b; // noop, it's stored at the first byte of B

// 2. get the pointer to foo function
void (*foo)(B*) = vptr[1]; // 0 is for RTTI

// 3. apply foo
(*foo)(b);

Those vptrs are initialized by the constructors of the objects, when executing the constructor of D, here is what happened:

• D::D() calls B::B() first and foremost, to initiliaze its subparts
• B::B() initialize vptr to point to its vtable, then returns
• D::D() initialize vptr to point to its vtable, overriding B's

Therefore, vptr here pointed to D's vtable, and thus the foo applied was D's. For B it was completely transparent.

Here B and D share the same vptr!

4. Virtual tables in multi-inheritance

Unfortunately this sharing is not always possible.

First, as we have seen, in the case of virtual inheritance, the "shared" item is positionned oddly in the final complete object. It therefore has its own vptr. That's 1.

Second, in case of multi-inheritance, the first base is aligned with the complete object, but the second base cannot be (they both need space for their data), therefore it cannot share its vptr. That's 2.

Third, the first base is aligned with the complete object, thus offering us the same layout that in the case of simple inheritance (the same optimization opportunity). That's 3.

Quite simple, no ?

Answer 2

If a class has virtual members, one need to way to find their address. Those are collected in a constant table (the vtbl) whose address is stored in an hidden field for each object (vptr). A call to a virtual member is essentially:

obj->_vptr[member_idx](obj, params...);

A derived class which add virtual members to his base class also need a place for them. Thus a new vtbl and a new vptr for them. A call to an inherited virtual member is still

obj->_vptr[member_idx](obj, params...);

and a call to new virtual member is:

obj->_vptr2[member_idx](obj, params...);

If the base is not virtual, one can arrange for the second vtbl to be put immediately after the first one, effectively increasing the size of the vtbl. And the _vptr2 is no more needed. A call to a new virtual member is thus:

obj->_vptr[member_idx+num_inherited_members](obj, params...);

In the case of (non virtual) multiple inheritance, one inherit two vtbl and two vptr. They can't be merged, and calls must pay attention to add an offset to the object (in order for the inherited data members to be found at the correct place). Calls to the first base class members will be

obj->_vptr_base1[member_idx](obj, params...);

and for the second

obj->_vptr_base2[member_idx](obj+offset, params...);

New virtual members can again either be put in a new vtbl, or appended to the vtbl of the first base (so that no offsets are added in future calls).

If a base is virtual, one can not append the new vtbl to the inherited one as it could leads to conflicts (in the example you gave, if both B and C append their virtual functions, how D be able to build its version?).

Thus, A needs a vtbl. B and C need a vtbl and it can't be appended to A's one because A is a virtual base of both. D needs a vtbl but it can be appended to B one as B is not a virtual base class of D.