Virtual method table

<h2 id="implementation">Implementation</h2>
An object's virtual method table will contain the <a href="/facts/Memory_address/7EsUmbea">addresses</a> of the object's dynamically bound methods. Method calls are performed by fetching the method's address from the object's virtual method table. The virtual method table is the same for all objects belonging to the same class, and is therefore typically shared between them. Objects belonging to type-compatible classes (for example siblings in an inheritance hierarchy) will have virtual method tables with the same layout: the address of a given method will appear at the same offset for all type-compatible classes. Thus, fetching the method's address from a given offset into a virtual method table will get the method corresponding to the object's actual class.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
The <a href="/facts/C%252B%252B/Et0F2qn9">C++</a> standards do not mandate exactly how dynamic dispatch must be implemented, but compilers generally use minor variations on the same basic model.
Typically, the compiler creates a separate virtual method table for each class. When an object is created, a pointer to this table, called the virtual table pointer, vpointer or VPTR, is added as a hidden member of this object. As such, the compiler must also generate "hidden" code in the <a href="/facts/Constructor_(object-oriented_programming)/8JNHsH5H">constructors</a> of each class to initialize a new object's virtual table pointer to the address of its class's virtual method table.
Many compilers place the virtual table pointer as the last member of the object; other compilers place it as the first; portable source code works either way.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
For example, <a href="/facts/G%252B%252B/t07jh01k">g++</a> previously placed the pointer at the end of the object.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="example">Example</h2>
Consider the following class declarations in <a href="/facts/C%252B%252B_syntax/Et0F2qn9">C++ syntax</a>:

class B1 {
public:
 virtual ~B1() {}
 void fnonvirtual() {}
 virtual void f1() {}
 int int_in_b1;
};

class B2 {
public:
  virtual ~B2() {}
  virtual void f2() {}
  int int_in_b2;
};

used to derive the following class:

class D : public B1, public B2 {
public:
 void d() {}
 void f2() override {}
 int int_in_d;
};

and the following piece of C++ code:

B2 *b2 = new B2();
D *d = new D();

g++ 3.4.6 from <a href="/facts/GNU_Compiler_Collection/t07jh01k">GCC</a> produces the following 32-bit memory layout for the object b2:<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

b2:
 +0: pointer to virtual method table of B2
 +4: value of int_in_b2

virtual method table of B2:
  +0: B2::f2()

and the following memory layout for the object d:

d:
 +0: pointer to virtual method table of D (for B1)
 +4: value of int_in_b1
 +8: pointer to virtual method table of D (for B2)
 +12: value of int_in_b2
 +16: value of int_in_d

Total size: 20 Bytes.

virtual method table of D (for B1):
  +0: B1::f1()  // B1::f1() is not overridden

virtual method table of D (for B2):
  +0: D::f2()   // B2::f2() is overridden by D::f2()
                // The location of B2::f2 is not in the virtual method table for D

Note that those functions not carrying the keyword virtual in their declaration (such as fnonvirtual() and d()) do not generally appear in the virtual method table. There are exceptions for special cases as posed by the <a href="/facts/Default_constructor/UnyxDE4K">default constructor</a>.
Also note the <a href="/facts/Virtual_function/cnxckyHy">virtual destructors</a> in the base classes, B1 and B2. They are necessary to ensure delete d can free up memory not just for D, but also for B1 and B2, if d is a pointer or reference to the types B1 or B2. They were excluded from the memory layouts to keep the example simple. <a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
<a href="/facts/Method_overriding/B1AwBgUF">Overriding of the method</a> 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().

<h2 id="multiple-inheritance-and-thunks">Multiple inheritance and thunks</h2>
The g++ compiler implements the <a href="/facts/Multiple_inheritance/kFvNb9rY">multiple inheritance</a> 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", also called <a href="/facts/Thunk_(programming)/2JFXex4w">thunks</a>, when <a href="/facts/Type_conversion/FuPD945T">casting</a>.
Consider the following C++ code:

D *d = new D();
B1 *b1 = d;
B2 *b2 = d;

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 that "looks like" an instance of B2, i.e., has the same memory layout as an instance of B2.

<h2 id="invocation">Invocation</h2>
A call to d->f1() is handled by dereferencing d's D::B1 vpointer, looking up the f1 entry in the virtual method table, and then dereferencing that pointer to call the code.
Single inheritance
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++:

(*((*d)[0]))(d)

Where *d refers to the virtual method table of D and [0] refers to the first method in the virtual method table. The parameter d becomes the <a href="/facts/This_(computer_science)/DYW7Snl3">"this" pointer</a> to the object.
Multiple inheritance
In the more general case, calling B1::f1() or D::f2() is more complicated:

(*(*(d[0]/*pointer to virtual method table of D (for B1)*/)[0]))(d) /* Call d->f1() */
(*(*(d[8]/*pointer to virtual method table of D (for B2)*/)[0]))(d+8) /* Call d->f2() */

The call to d->f1() passes a B1 pointer as a parameter. The call to d->f2() passes a B2 pointer as a parameter. This second call requires a fixup to produce the correct pointer. The location of B2::f2 is not in the virtual method table for D.
By comparison, a call to d->fnonvirtual() is much simpler:

(*B1::fnonvirtual)(d)

<h2 id="efficiency">Efficiency</h2>
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. Therefore, calling virtual functions is inherently slower than calling non-virtual functions. An experiment done in 1996 indicates that approximately 6–13% of execution time is spent simply dispatching to the correct function, though the overhead can be as high as 50%.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> The cost of virtual functions may not be so high on modern CPU architectures due to much larger caches and better <a href="/facts/Branch_predictor/pGPhFMj5">branch prediction</a>.
Furthermore, in environments where <a href="/facts/Just-in-time_compilation/rEYDsd8l">JIT compilation</a> is not in use, virtual function calls usually cannot be <a href="/facts/Inline_expansion/jhQsJwLX">inlined</a>. In certain cases it may be possible for the compiler to perform a process known as devirtualization in which, for instance, the lookup and indirect call are replaced with a conditional execution of each inlined body, but such optimizations are not common.
To avoid this overhead, compilers usually avoid using virtual method tables whenever the call can be resolved at <a href="/facts/Compile_time/yCdI3oqn">compile time</a>.
Thus, the call to f1 above may not require a table 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 table lookup because the implementation is specified explicitly (although it does still require the 'this'-pointer fixup).

<h2 id="comparison-with-alternatives">Comparison with alternatives</h2>
The virtual method table is generally a good performance trade-off to achieve dynamic dispatch, but there are alternatives, such as binary tree dispatch, with higher performance in some typical cases, but different trade-offs.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
However, virtual method tables only allow for <a href="/facts/Single_dispatch/211NC5eu">single dispatch</a> on the special "this" parameter, in contrast to <a href="/facts/Multiple_dispatch/eCYSSjGE">multiple dispatch</a> (as in <a href="/facts/Common_Lisp_Object_System/dDAH0cu9">CLOS</a>, <a href="/facts/Dylan_(programming_language)/VVQGkShF">Dylan</a>, or <a href="/facts/Julia_(programming_language)/AoB0PJ9C">Julia</a>), where the types of all parameters can be taken into account in dispatching.
Virtual method tables also only work if dispatching is constrained to a known set of methods, so they can be placed in a simple array built at compile time, in contrast to <a href="/facts/Duck_typing/tcuo8Ywq">duck typing</a> languages (such as <a href="/facts/Smalltalk/Ru2UPVDE">Smalltalk</a>, <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a> or <a href="/facts/JavaScript/XhhIIEsl">JavaScript</a>).
Languages that provide either or both of these features often dispatch by looking up a string in a <a href="/facts/Hash_table/Ht4ptDPF">hash table</a>, or some other equivalent method. There are a variety of techniques to make this faster (e.g., <a href="/facts/String_interning/CN0x3jsd">interning</a>/tokenizing method names, caching lookups, <a href="/facts/Just-in-time_compilation/rEYDsd8l">just-in-time compilation</a>).

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Virtual_function/cnxckyHy">Virtual function</a></li>
<li><a href="/facts/Virtual_inheritance/BK3PVanG">Virtual inheritance</a></li>
<li><a href="/facts/Branch_table/LcfPVyQS">Branch table</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Margaret A. Ellis and <a href="/facts/Bjarne_Stroustrup/Be1Yq6rn">Bjarne Stroustrup</a> (1990) The Annotated C++ Reference Manual. Reading, MA: Addison-Wesley. (<a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-201-51459-1)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Zendra, Olivier; Colnet, Dominique; Collin, Suzanne (1997). Efficient Dynamic Dispatch without Virtual Function Tables: The SmallEiffel Compiler -- 12th Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'97), ACM SIGPLAN, Oct 1997, Atlanta, United States. pp.125-141. inria-00565627. Centre de Recherche en Informatique de Nancy Campus Scientifique, Bâtiment LORIA. p. 16. <a href="https://hal.inria.fr/inria-00565627/document" target="_blank">https://hal.inria.fr/inria-00565627/document</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Ellis & Stroustrup 1990, pp. 227–232 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Danny Kalev.
"C++ Reference Guide: The Object Model II".
2003.
Heading "Inheritance and Polymorphism" and "Multiple Inheritance". <a href="http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=196" target="_blank">http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=196</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"C++ ABI Closed Issues". Archived from the original on 25 July 2011. Retrieved 17 June 2011.{{cite web}}: CS1 maint: bot: original URL status unknown (link) <a href="https://web.archive.org/web/20110725153606/http://www.codesourcery.com/public/cxx-abi/cxx-closed.html" target="_blank">https://web.archive.org/web/20110725153606/http://www.codesourcery.com/public/cxx-abi/cxx-closed.html</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">G++'s -fdump-class-hierarchy (starting with version 8: -fdump-lang-class) argument can be used to dump virtual method tables for manual inspection. For AIX VisualAge XlC compiler, use -qdump_class_hierarchy to dump class hierarchy and virtual function table layout. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"C++ - why there are two virtual destructor in the virtual table and where is address of the non-virtual function （gcc4.6.3）". <a href="https://stackoverflow.com/questions/17960917/why-there-are-two-virtual-destructor-in-the-virtual-table-and-where-is-address-o" target="_blank">https://stackoverflow.com/questions/17960917/why-there-are-two-virtual-destructor-in-the-virtual-table-and-where-is-address-o</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Driesen, Karel and Hölzle, Urs, "The Direct Cost of Virtual Function Calls in C++", OOPSLA 1996 <a href="https://dl.acm.org/doi/10.1145/236338.236369" target="_blank">https://dl.acm.org/doi/10.1145/236338.236369</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Zendra, Olivier; Colnet, Dominique; Collin, Suzanne (1997). Efficient Dynamic Dispatch without Virtual Function Tables: The SmallEiffel Compiler -- 12th Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'97), ACM SIGPLAN, Oct 1997, Atlanta, United States. pp.125-141. inria-00565627. Centre de Recherche en Informatique de Nancy Campus Scientifique, Bâtiment LORIA. p. 16. <a href="https://hal.inria.fr/inria-00565627/document" target="_blank">https://hal.inria.fr/inria-00565627/document</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Zendra, Olivier and Driesen, Karel, "Stress-testing Control Structures for Dynamic Dispatch in Java", pp. 105–118, Proceedings of the USENIX 2nd Java Virtual Machine Research and Technology Symposium, 2002 (JVM '02) <a href="http://www.usenix.org/event/jvm02/full_papers/zendra/zendra_html/index.html" target="_blank">http://www.usenix.org/event/jvm02/full_papers/zendra/zendra_html/index.html</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Virtual method table open-in-new

Virtual method table