Problem for Dynamic Dispatch

• New methods now exist
• Original apply() code existed and was compiled long before class Circle was created
• The original apply() code in this case must call Circle::draw()

How?

• At compile time, the virtual table or vtable is created to store the information required for the dynamic dispatch of virtual methods for a class
• For every object of a class that has a vtable, the object has a pointer to the class vtable
• Method calls go through the vtable for the class of an object

Fundamental Theorem of Software Engineering (FTSE)

We can solve any problem by introducing an extra level of indirection

All problems in computer science can be solved by another level of indirection, except for the problem of too many layers of indirection

• Original quote David Wheeler
• Addendum possibly by Andrew Koenig
• namespace alias
• typedef
• Use of references
• Use of pointers

vtable for class Shape with Added Methods

vtable for class Shape

• A vtable has:
• typeInfo
• Array of pointers to virtual methods
• Virtual method calls for dynamic dispatch are stored in the program as an array index, i.e., method[0] for the first virtual method, method[1] for the second virtual method, etc.

vtable for class Circle

Base class Shape vtable & functions

Derived class Circle vtable & functions

Combined vtables & functions

Shape* to Shape Object

Shape* to Circle Object

Shape* p = new Shape(); p->draw();

• Shape* p points to the new Shape object
• The Shape object points to the vtable for Shape
• The method draw() is the first entry in the vtable
• The first entry in the vtable points to the function for Shape::draw()

Shape* p = new Circle(); p->draw();

• Shape* p points to the new Circle object
• The Circle object points to the vtable for Circle
• The method draw() is the first entry in the vtable
• The first entry in the vtable points to the function for Circle::draw()

p->draw()

Combined

Notes

• There is a dependency of class Derived on class Base because changes to the class Base vtable (e.g., add or remove virtual methods) changes the layout of the class Derived vtable
• Code compiled with the Base class (e.g., apply()) can only call class Base methods

Conclusion

• vtable mechanism supports polymorphism and virtual method calls, even when the derived class methods are not defined yet
• Overhead of a pointer indirection
• Overhead of preventing inlining
• But it is worth it in terms of code flexibility