HOME

TheInfoList



OR:

In
computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as ana ...
, a virtual method table (VMT), virtual function table, virtual call table,
dispatch table In computer science, a dispatch table is a table of pointers or memory addresses to functions or methods. Use of such a table is a common technique when implementing late binding in object-oriented programming. Perl implementation The followin ...
, vtable, or vftable is a mechanism used in a
programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...
to support
dynamic dispatch In computer science, dynamic dispatch is the process of selecting which implementation of a polymorphic operation (method or function) to call at run time. It is commonly employed in, and considered a prime characteristic of, object-oriented ...
(or run-time method binding). Whenever a
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differentl ...
defines a
virtual function In object-oriented programming, in languages such as C++, and Object Pascal, a virtual function or virtual method is an inheritable and overridable function or method for which dynamic dispatch is facilitated. This concept is an important part o ...
(or
method Method ( grc, μέθοδος, methodos) literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In recent centuries it more often means a prescribed process for completing a task. It may refer to: *Scien ...
), most
compiler In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
s add a hidden
member variable In object-oriented programming, a member variable (sometimes called a member field) is a variable that is associated with a specific object, and accessible for all its methods (''member functions''). In class-based programming languages, these are ...
to the class that points to an array of pointers to (virtual) functions called the virtual method table. These pointers are used at runtime to invoke the appropriate function implementations, because at compile time it may not yet be known if the base function is to be called or a derived one implemented by a class that inherits from the base class. There are many different ways to implement such dynamic dispatch, but use of virtual method tables is especially common among
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
and related languages (such as D and C#). Languages that separate the programmatic interface of objects from the implementation, like
Visual Basic Visual Basic is a name for a family of programming languages from Microsoft. It may refer to: * Visual Basic .NET (now simply referred to as "Visual Basic"), the current version of Visual Basic launched in 2002 which runs on .NET * Visual Basic (cl ...
and
Delphi Delphi (; ), in legend previously called Pytho (Πυθώ), in ancient times was a sacred precinct that served as the seat of Pythia, the major oracle who was consulted about important decisions throughout the ancient classical world. The oracle ...
, also tend to use this approach, because it allows objects to use a different implementation simply by using a different set of method pointers. Suppose a program contains three classes in an inheritance hierarchy: a superclass, , and two subclasses, and . Class defines a
virtual function In object-oriented programming, in languages such as C++, and Object Pascal, a virtual function or virtual method is an inheritable and overridable function or method for which dynamic dispatch is facilitated. This concept is an important part o ...
named , so its subclasses may provide an appropriate implementation (e.g. either or ). When the program calls the function on a reference (which can refer to an instance of , or an instance of or ), the code must be able to determine which implementation of the function the call should be ''dispatched'' to. This depends on the actual class of the object, not the class of the reference to it (). The class cannot generally be determined ''statically'' (that is, at
compile time In computer science, compile time (or compile-time) describes the time window during which a computer program is compiled. The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concept ...
), so neither can the compiler decide which function to call at that time. The call must be dispatched to the right function ''dynamically'' (that is, at
run time Run(s) or RUN may refer to: Places * Run (island), one of the Banda Islands in Indonesia * Run (stream), a stream in the Dutch province of North Brabant People * Run (rapper), Joseph Simmons, now known as "Reverend Run", from the hip-hop group ...
) instead.


Implementation

An object's virtual method table will contain the addresses 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. The
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
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 constructors 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. For example, g++ previously placed the pointer at the end of the object.


Example

Consider the following class declarations in
C++ syntax C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
: class B1 ; class B2 ; used to derive the following class: class D : public B1, public B2 ; and the following piece of C++ code: B2 *b2 = new B2(); D *d = new D(); g++ 3.4.6 from GCC produces the following 32-bit memory layout for the object b2: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.
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
default constructor In computer programming languages, the term default constructor can refer to a constructor that is automatically generated by the compiler in the absence of any programmer-defined constructors (e.g. in Java), and is usually a nullary constructor. I ...
. Also note the virtual destructors 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. 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().


Multiple inheritance and thunks

The g++ compiler implements the
multiple inheritance Multiple inheritance is a feature of some object-oriented computer programming languages in which an object or class can inherit features from more than one parent object or parent class. It is distinct from single inheritance, where an object or ...
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
thunk In computer programming, a thunk is a subroutine used to inject a calculation into another subroutine. Thunks are primarily used to delay a calculation until its result is needed, or to insert operations at the beginning or end of the other subr ...
s, when
casting Casting is a manufacturing process in which a liquid material is usually poured into a mold, which contains a hollow cavity of the desired shape, and then allowed to solidify. The solidified part is also known as a ''casting'', which is ejected ...
. 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.


Invocation

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) )(d) Where *d refers to the virtual method table of D and /code> refers to the first method in the virtual method table. The parameter d becomes the "this" pointer 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)*/) )(d) /* Call d->f1() */ (*(*(d 8*pointer to virtual method table of D (for B2)*/) )(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)


Efficiency

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%. The cost of virtual functions may not be so high on modern architectures due to much larger caches and better
branch prediction In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g., an if–then–else structure) will go before this is known definitively. The purpose of the branch predictor is to improve the flow ...
. Furthermore, in environments where JIT compilation is not in use, virtual function calls usually cannot be inlined. 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
compile time In computer science, compile time (or compile-time) describes the time window during which a computer program is compiled. The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concept ...
. 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).


Comparison with alternatives

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 but different costs.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)
However, virtual method tables only allow for
single dispatch In computer science, dynamic dispatch is the process of selecting which implementation of a polymorphic operation (method or function) to call at run time. It is commonly employed in, and considered a prime characteristic of, object-oriented ...
on the special "this" parameter, in contrast to
multiple dispatch Multiple dispatch or multimethods is a feature of some programming languages in which a function or method can be dynamically dispatched based on the run-time (dynamic) type or, in the more general case, some other attribute of more than one of ...
(as in
CLOS Clos may refer to: People * Clos (surname) Other uses * CLOS, Command line-of-sight, a method of guiding a missile to its intended target * Clos network, a kind of multistage switching network * Clos (vineyard), a walled vineyard; used in Fran ...
, Dylan, or
Julia Julia is usually a feminine given name. It is a Latinate feminine form of the name Julio and Julius. (For further details on etymology, see the Wiktionary entry "Julius".) The given name ''Julia'' had been in use throughout Late Antiquity (e.g ...
), 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
duck typing Duck typing in computer programming is an application of the duck test—"If it walks like a duck and it quacks like a duck, then it must be a duck"—to determine whether an object can be used for a particular purpose. With nominative t ...
languages (such as
Smalltalk Smalltalk is an object-oriented, dynamically typed reflective programming language. It was designed and created in part for educational use, specifically for constructionist learning, at the Learning Research Group (LRG) of Xerox PARC by Alan Ka ...
,
Python Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...
or
JavaScript JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
). Languages that provide either or both of these features often dispatch by looking up a string in a
hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
, or some other equivalent method. There are a variety of techniques to make this faster (e.g., interning/tokenizing method names, caching lookups,
just-in-time compilation In computing, just-in-time (JIT) compilation (also dynamic translation or run-time compilations) is a way of executing computer code that involves compilation during execution of a program (at run time) rather than before execution. This may cons ...
).


See also

*
Virtual function In object-oriented programming, in languages such as C++, and Object Pascal, a virtual function or virtual method is an inheritable and overridable function or method for which dynamic dispatch is facilitated. This concept is an important part o ...
*
Virtual inheritance Virtual inheritance is a C++ technique that ensures only one copy of a base classs member variables are inherited by grandchild derived classes. Without virtual inheritance, if two classes B and C inherit from a class A, and a class D inherits fr ...
*
Branch table In computer programming, a branch table or jump table is a method of transferring program control ( branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch or jump instruction ...


Notes


References

* Margaret A. Ellis and
Bjarne Stroustrup Bjarne Stroustrup (; ; born 30 December 1950) is a Danish computer scientist, most notable for the invention and development of the C++ programming language. As of July 2022, Stroustrup is a professor of Computer Science at Columbia University. ...
(1990) The Annotated C++ Reference Manual. Reading, MA: Addison-Wesley. () {{DEFAULTSORT:Virtual Method Table Method (computer programming) Articles with example C++ code