Virtual dispatch implementation details

Question

First of all, I want to make myself clear that I do understand that there is no notion of vtables and vptrs in the C++ standard. However I think that virtually all implementations implement the virtual dispatch mechanism in pretty much the same way (correct me if I am wrong, but this isn't the main question). Also, I believe I know how virtual functions work, that is, I can always tell which function will be called, I just need the implementation details.

Suppose someone asked me the following:
"You have base class B with virtual functions v1, v2, v3 and derived class D:B which overrides functions v1 and v3 and adds a virtual function v4. Explain how virtual dispatch works".

I would answer like this:
For each class with virtual functions(in this case B and D) we have a separate array of pointers-to-functions called vtable.
The vtable for B would contain

&B::v1
&B::v2
&B::v3

The vtable for D would contain

&D::v1
&B::v2
&D::v3
&D::v4 

Now the class B contains a member pointer vptr. D naturally inherits it and therefore contains it too. In the constructor and destructor of B B sets vptr to point to B's vtable. In the constructor and destructor of D D sets it to point to D's vtable.
Any call to a virtual function f on an object x of polymorphic class X is interpreted as a call to x.vptr[f's position in vtables]

The questions are:
1. Do I have any errors in the above description?
2. How does the compiler know f's position in vtable (in detail, please)
3. Does this mean that if a class has two bases then it has two vptrs? What is happening in this case? (try to describe in a similar manner as I did, in as much detail as possible)
4. What's happening in a diamond hierarchy with A on top B,C in the middle and D at the bottom? (A is a virtual base class of B and C)

Thanks in advance.

Hermeneutics

Answer 1

1. Do I have any errors in the above description?

All good. :-)

2. How does the compiler know f's position in vtable

Each vendor will have their own way of doing this, but I always think of the vtable as map of the member function signature to memory offset. So the compiler just maintains this list.

3. Does this mean that if a class has two bases then it has two vptrs? What is happening in this case?

Typically, compilers compose a new vtable which consists of all the vtables of the virtual bases appended together in the order they were specified, along with the vtable pointer of the virtual base. They follow this with the vtable functions of the deriving class. This is extremely vendor-specific, but for class D : B1, B2, you typically see D._vptr[0] == B1._vptr.

That image is actually for composing the member fields of an object, but vtables can be composed by the compiler in the exact same way (as far as I understand it).

4. What's happening in a diamond hierarchy with A on top B,C in the middle and D at the bottom? (A is a virtual base class of B and C)

The short answer? Absolute hell. Did you virtually inherit both the bases? Just one of them? Neither of them? Ultimately, the same techniques of composing a vtable for the class are used, but how this is done varies way to wildly, since how it should be done is not at all set in stone. There is a decent explanation of solving the diamond-hierarchy problem here, but, like most of this, it is quite vendor-specific.

Redoubtable

@Travis: Thanks for your answer. 1. I disagree with you on point one: No virtual dispatch is done from the destructor (the standard explicitly mentions this). 2. OK 3. Great. 4. I specifically mentioned that both B and C derived virtually from A. Thanks again for the answer, appreciate it. – Hermeneutics

+1 Overall, but the first point is wrong: the vptr is modified by the destructor. When each of the destructors in the hierarchy from the most derived type to the base completes, it updates the vptr in the inverse way as the constructors did. Your example is good, but the language will not protect you, it is undefined behavior. Many compilers will introduce a pure virtual method thunk that will printout an error message (pure virtual method called). Try it. The rationale on the decision of updating the pointer is that the final overrider for a method cannot be a destroyed object. – Complicacy

@David: Since the example is deleted, I can't remember it in detail, but it shouldn't be undefined behavior. Correct be if I am wrong but the behavior is defined and it just calls the cleanup() of the base class. – Hermeneutics

@Armen: The problem is that I had cleanup as a pure virtual function, which means there is no way to call it. – Redoubtable

@David: If (as I've just learned) destructors don't make virtual calls, then why do they need to use the vptr at all, let alone modify it? – Agan

@Oli Charlesworth: again, can anyone produce a quote from the standard? I have not yet located a quote, but gcc and vs compilers do update the vptr after completing destruction, and calls are dynamically dispatched to the final overrider, which at each stage is the most implementation in the most derived, not yet destroyed object. – Complicacy

@David: This is news to me. What would be rationale behind this? – Agan

@David: Suppose D:B and f is a virt funvtion called from both ~B and ~D and main function contains a single statement D d; MSVC prints D::~D D::f B::~B B::f ... – Hermeneutics

@Armen: That behavior is so because the vptr gets updated after ~D completes and before ~B starts. Consider adding a dispatch method that calls f() (void B::dispatch() { f(); }) in B, and have ~B call dispatch. Now, there is a single definition of B::dispatch and as such there is a single implementation. Because it can be called on an object that is alive it has to call f using the regular virtual dispatch mechanism. Now, if you run the test you will see the same effect as before: B::f is called when dispatch is called from the B destructor. – Complicacy

@Armen: ... I guess I was wrong in my interpretation of §12.4/6, I have reread it a couple of times and I agree that it disables virtual dispatch when the constructor is running: once the destructor starts then no virtual method will be dispatched to an object derived from this, and that needs to be implemented in a vtable system by means of an update of the vptr after the destructor of the most derived object. – Complicacy

@Oli Charlesworth: If the question is what is the rationale for updating the vptr, the answer is that methods that could potentially call virtual methods, and that at the same time can potentially be called from the destructor must not call a more derived class when they are called from the destructor (virtual dispatch will not go down to an already destructed object). To ensure this, the virtual dispatch mechanism must be updated after compleeting each destructor so that the vptrs point to the immediately less derived object. – Complicacy

@David: I see. So it's not that dynamic dispatch doesn't occur, it's that it won't dispatch to a child override relative to the destructor that's currently in progress? – Agan

@Armen, @Oli: I have written a small snippet in codepad. It is my first post there, so if it does not work tell me and I will produce the code somewhere else. – Complicacy

BTW with regards to point 2, you can have some fun (or pain) by playing around with the order of virtual functions in the header file; compile the implementation, re order something, compile the usage, link... kerboom. (The point being that most compilers are very brittle in that regards.) – Cornu

Base1 is called the "primary base" – Lacombe

Answer 2

1. Looks good to me

2. Implementation specific, but most are just in source code order -- meaning the order they appear in the class -- starting with the base class, then adding on new virtual functions from the derived. As long as the compiler has a deterministic way of doing this, then anything it wants to do is fine. However, on Windows, to create COM compatible V-Tables, it has to be in source order

3. (not sure)

4. (guess) A diamond just means that you could have two copies of a base class B. Virtual inheritance will merge them into one instance. So if you set a member via D1, you can read it via D2. (with C derived from D1, D2, each of them derived from B). I believe that in both cases, the vtables would be identical, as the function pointers are the same -- the memory for data members is what is merged.

Tabshey

Sorry, but I don't have definitive answers for 3 and 4. I think that there's a step to make sure you have the right vtable, but I don't know the details. – Tabshey

Thanks, order for COM was exactly what I needed. – Rayburn

Answer 3

Comments:

• I don't think destructors come into it!

• A call such as e.g. D d; d.v1(); will probably not be implemented via the vtable, as the compiler can resolve the function address at compile/link-time.

• The compiler knows f's position because it put it there!

• Yes, a class with multiple base classes will typically have multiple vptrs (assuming virtual functions in each base class).

• Scott Meyers' "Effective C++" books explain multiple inheritance and diamonds better than I can; I'd recommend reading them for this (and many other) reasons. Consider them essential reading!

Agan

@Oli: about the first point - they do, otherwise how do you explain that when in Base's destructor a virtual function f is called, Base::f is called and not Derived::f? – Hermeneutics

He's right that destructors don't make virtual calls. In order to do this in a call from a call, it probably would replace the vtable as he described (with caveats that this is all implementation specific) – Tabshey

@Armen: The same as a virtual call from inside any other member function of Base. – Agan

@Oli: I am afraid you are completely wrong. If you call a virtual function from any other base member, the derived's override may be called depending on the dynamic type of the object – Hermeneutics

@Armen: I was not aware of that! (Although after a moment's thought, the reason is obvious.) But nevertheless, the explanation of this is surely pretty simple? The compiler can make this one exception, and resolve the address at compile-time. – Agan

@Oli: The compiler can do anything. My question is about what it actually does :) – Hermeneutics

@Armen: Ok, well clearly it actually does this! If you want the precise details, just peruse some disassembler... – Agan

@Oli: Btw I have read Meyers, and consulted the relevant chapter before posting this, but he doesn't quite give the answer to my specific question – Hermeneutics

@Armen: In "More Effective C++", item 24, he gives one possible implementation of vptrs for inheritance diamonds. There is no one definitive answer, because implementers will all do it slightly differently! – Agan

@Armen: On the derived's override may be called depending on the dynamic type of the object In a hierarchy base <- derived <- rederived, with an object of type rederived after ~rederived has completed, the dynamic type of the object is derived. – Complicacy