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,
Catdefines 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
and the following memory layout for the object
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
Dis implemented by duplicating the virtual method table of
B2and replacing the pointer to
B2::f2()with a pointer to
The g++ compiler implements the multiple inheritance of the classes
Dusing 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:
b1will point to the same memory location after execution of this code,
b2will point to the location
d+8(eight bytes beyond the memory location of
b2points to the region within
dwhich "looks like" an instance of
B2, i.e., has the same memory layout as an instance of
A call to
d->f1()is handled by dereferencing
D::B1vpointer, looking up the
f1entry 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
dare 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
f1above may not require a vtable lookup because the compiler may be able to tell that
dcan only hold a
Dat this point, and
Ddoes not override
f1. Or the compiler (or optimizer) may be able to detect that there are no subclasses of
B1anywhere in the program that override
f1. The call to
B2::f2will probably not require a vtable lookup because the implementation is specified explicitly (although it does still require the this-pointer fixup).