Sunday, December 2, 2007

A virtual method table, virtual function table, dispatch table, or vtable, is a mechanism used in programming language implementations in order to support dynamic polymorphism, i.e., run-time method binding.
Suppose a program contains several classes in an inheritance hierarchy: a superclass, Cat, and two subclasses, HouseCat and Lion. Class Cat defines a virtual function named "speak" but provides no implementation. Instead, its subclasses must provide an appropriate implementation (i.e., either meow or roar). Recall that such a function is called pure virtual function.
When the program calls the "speak" method on a Cat pointer (which can point to a Cat class, or any subclass of Cat), the run-time environment must be able to determine which version to call.
There is a variety of different ways to implement such dynamic dispatch, but the vtable solution is especially common among C++ and related languages (such as D and C#). Languages which separate the programmatic interface of objects from the implementation, like Visual Basic and Delphi, also tend to use the vtable approach, because it allows objects to use a different implementation simply by using a different set of method pointers.

Consider the following class declarations in C++ syntax:
used to derive the following class:
and the following piece of C++ code:
g++ 3.4.6 from the GNU Compiler Collection produces the following 32bit memory layout for the object b2:

and the following memory layout for the object d:
Note that non-virtual functions (such as f0) do not generally appear in the vtable, but there are exceptions in some special cases (such as the default constructor).
Overriding of the method f2() in class D is implemented by duplicating the virtual method table of B2 and replacing the pointer to B2::f2() with a pointer to D::f2().

Virtual table Example
The g++ compiler implements the multiple inheritance of the classes B1 and B2 in class D using two virtual method tables, one for each base class. (There are other ways to implement multiple inheritance, but this is the most common.) This leads to the necessity for "pointer fixups" when casting.
Consider the following C++ code:
While d and b1 will point to the same memory location after execution of this code, b2 will point to the location d+8 (eight bytes beyond the memory location of d). Thus, b2 points to the region within d which "looks like" an instance of B2, i.e., has the same memory layout as an instance of B2.

Multiple inheritance
A call to d->f1() is handled by dereferencing d's D::B1 vpointer, looking up the f1 entry in the vtable, and then dereferencing that pointer to call the code.
In the case of single inheritance (or in a language with only single inheritance), if the vpointer is always the first element in d (as it is with many compilers), this reduces to the following pseudo-C++:
In the more general case, as above, calling f1(), D::f2(), and B2::f2() on d are more complicated:
By comparison, a call to d->f0() is much simpler:

Note that a virtual call requires at least an extra indexed dereference, and sometimes a "fixup" addition, compared to a non-virtual call, which is simply a jump to a compiled-in pointer. So, calling virtual functions is inherently slower than calling non-virtual functions. Measurements estimate that around 6-13% of execution time is spent simply dispatching to the correct function, though the overhead can be as high as 50%.
In addition, in environments where JIT compilation is not in use, virtual function calls usually cannot be inlined. While a compiler could replace the lookup and indirect call with, e.g., a conditional execution of each inlined body, such optimizations are not common.
To avoid this overhead, compilers usually avoid using vtables whenever the call can be resolved at compile time.
Thus, the call to f1 above may not require a vtable lookup because the compiler may be able to tell that d can only hold a D at this point, and D does not override f1. Or the compiler (or optimizer) may be able to detect that there are no subclasses of B1 anywhere in the program that override f1. The call to B1::f1 or B2::f2 will probably not require a vtable lookup because the implementation is specified explicitly (although it does still require the this-pointer fixup).