Virtual method table

Virtual method table

A virtual method table, virtual function table, dispatch table, or vtable, is a mechanism used in programming language to support dynamic dispatch (or 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, so its subclasses may provide an appropriate implementation (i.e., either meow or roar).

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 implementation to call, depending on the actual type of object that is pointed to.

There are 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.

Implementation

An object's dispatch 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 dispatch table. The dispatch 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 dispatch 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 dispatch table offset will get the method corresponding to the object's actual class. [Ellis & Stroustrup 1990, pp. 227–232]

The C++ 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 vtable for each class. When an object is created, a pointer to this vtable, called the virtual table pointer or vpointer, is added as a hidden member of this object (often the first member). The compiler also generates "hidden" code in the constructor of each class to initialize the vpointers of its objects to the address of the corresponding vtable.

Example

Consider the following class declarations in C++ syntax:class B1{public: void f0() {} virtual void f1() {} int int_in_b1;};

class B2{public: 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 B2::f2() int int_in_d;};

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 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() +4: B2::~B2()

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) +16: value of int_in_b2 +20: value of int_in_d

virtual method table of D (for B1): +0: B1::f1() +4: D::~D() +8: D::d() +12: D::f2()

virtual method table of D (for B2): +0: D::f2() // B2::f2() is overridden by D::f2() +4: D::~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().

Multiple inheritance and thunks

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" (thunks) when casting.

Consider the following C++ code:D *d = new D();B1 *b1 = dynamic_cast(d);B2 *b2 = dynamic_cast(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 which "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 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++:


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

In the more general case, as above, calling f1(), D::f2(), and B2::f2() on d are more complicated:


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

By comparison, a call to d->f0() is much simpler:


*B1::f0(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. Experiments indicate that approximately 6-13% of execution time is spent simply dispatching to the correct function, though the overhead can be as high as 50% [Driesen, Karel and Hölzle, Urs, [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf "The Direct Cost of Virtual Function Calls in C++"] , OOPSLA 1996] .

Furthermore, 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, for instance, 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).

Comparison with alternatives

The vtable 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, [http://www.sagecertification.org/events/javavm02/full_papers/zendra/zendra_html/index.html "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, vtables only allow for single dispatch on the special "this" parameter, in contrast to multiple dispatch (as in CLOS or Dylan), where the types of all parameters can be taken into account in dispatching.

Vtables 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 languages (such as Smalltalk, Python or JavaScript).

Languages that provide either or both of these features often dispatch by looking up a string in a hash table, or some other equivalent method. There are a variety of tricks to speed this up (e.g., interning/tokenizing method names, caching lookups, just-in-time compilation), and dispatch time often does not have a significant effect on total processing time, but nonetheless, vtable lookup is obviously faster. Vtables are also simpler to implement and debug, and closer to the "C spirit" than hash tables of strings.

See also

*Virtual inheritance

Notes

References

* Margaret A. Ellis and Bjarne Stroustrup (1990) The Annotated C++ Reference Manual. Reading, MA: Addison-Wesley. (ISBN 0-201-51459-1)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Virtual function table — Таблица виртуальных методов (англ. virtual method table, VMT) координирующая таблица или vtable механизм, используемый в языках программирования для поддержки динамического соответствия (или метода позднего связывания). Допустим, программа… …   Википедия

  • Dispatch table — In computer science, a dispatch table is a table of pointers to functions or methods. Use of such a table is a common technique when implementing late binding in object oriented programming. Perl implementation The following shows one way to… …   Wikipedia

  • Branch table — In computer programming, a branch table (sometimes known as a jump table) is a term used to describe an efficient method of transferring program control (branching) to another part of a program (or a different program that may have been… …   Wikipedia

  • Virtual finite state machine — The virtual finite state machine (VFSM) is a concept promoted by [http://www.stateworks.com SW Software] and implemented in their StateWORKS product. A VFSM is a finite state machine (FSM) defined in a virtual environment. The VFSM concept… …   Wikipedia

  • File Allocation Table — For other uses, see Fat (disambiguation). FAT Developer Microsoft Full Name File Allocation Table FAT12 (12‑bit version) FAT16/FAT16B (16‑bit versions) FAT32 (32‑bit version with 28 bits used) Introduced …   Wikipedia

  • History of virtual learning environments 1990s — In the history of virtual learning environments, the 1990s was a time of growth, primarily due to advent of the affordable computer and of the Internet.1990s1990* Formal Systems Inc. of Princeton, NJ, USA introduces a DOS based Assessment… …   Wikipedia

  • Comparison of platform virtual machines — Platform virtual machines are software packages which emulate the whole physical computer machine, often giving multiple virtual machines on one physical platform. The table below compares basic information about platform virtual machine (VM)… …   Wikipedia

  • Comparison of application virtual machines — This article lists some software virtual machines that are typically used for allowing application bytecode to be portably run on many different computer architectures and operating systems. The application is usually run on the computer using an …   Wikipedia

  • Comparative method — This article is about the comparative method in linguistics. For other kinds of comparative methods, see Comparative (disambiguation). Linguistic map representing a Tree model of the Romance languages based on the comparative method. Here the… …   Wikipedia

  • Monte Carlo method — Not to be confused with Monte Carlo algorithm. Computational physics …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”