Virtual method table

The object coordinating table contains the addresses of the dynamically linked methods of the object. The method is called when the method address is selected from the table. The coordinating table will be the same for all objects belonging to the same class, therefore its sharing is allowed. Objects belonging to classes that are compatible by type (for example, standing at the same level in the inheritance hierarchy) will have similar coordinating tables: the address of this method will be fixed with the same offset for all classes that are compatible by type. Thus, choosing the address of the method from this coordinating table by offset, we get the method associated with the current class of the object. ^[one]

C ++ standards do not clearly define how dynamic coordination should be implemented, but compilers often use some variations of the same base model.

Typically, the compiler creates a separate vtable for each class. After creating an object, a pointer to this vtable, called a virtual table pointer or vpointer (also sometimes called vptr or vfptr), is added as a hidden member of the object (and often as the first member). The compiler also generates "hidden" code in the constructor of each class to initialize vpointer'ov its objects with the addresses of the corresponding vtable.

Consider the following class declarations in C ++:

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

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

use to create the following class:

  class D : public B1 , public B2
 {
 public :
   void d () {}
   void f2 () {} // redefine 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 the GCC set creates the following 32-bit memory scheme for the b2 (здесь и далее ТВМ - таблица виртуальных методов) object b2 (здесь и далее ТВМ - таблица виртуальных методов) : ^{[nb 1]}

  b2:
   +0: ​​pointer to TBM B2
   +4: int_in_b2 value

 TBM B2:
   +0: ​​B2 :: f2 ()   

and for the object d the memory scheme will be like this:

  d:
   +0: ​​pointer to TBM D (for B1)
   +4: int_in_b1 value
   +8: pointer to TBM D (for B2)
  +12: int_in_b2 value
  +16: int_in_d value

 Total size: 20 bytes.

 TBM D (for B1):
   +0: ​​B1 :: f1 () // B1 :: f1 () is not redefined

 TBM D (for B2):
   +0: ​​D :: f2 () // B2 :: f2 () is replaced by D :: f2 ()

It should be noted that non-virtual functions (such as f0 ) in general cannot appear in vtable, but in some cases there are exceptions (such as the default constructor).

The redefinition of the method f2() in class D is implemented by duplicating TBM B2 and replacing the pointer on B2::f2() pointer on D::f2() .

Multiple inheritance of classes B1 and B2 to 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 need for " pointers to an address entry " (bundles) when creating.

Consider the following C ++ code:

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

While d and b1 point to one place in memory after executing this code, b2 will point to memory location d+8 (eight bytes offset relative to location d ). Thus, b2 indicates a memory area inside d that “looks” like an entity B2 , i.e. has the same layout in memory as the B2 entity.

A call to d->f1() occurs when dereferencing vpointer D::B1 from d : looking at the entry for f1 in vtable, and then dereferencing this pointer invokes the code.

In the case of single inheritance (or in the case of a language with support for only single inheritance), if vpointer is always the first element in d (as happens with many compilers), then this is solved by the following pseudo-C ++ code:

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

In the more general case, as mentioned above, calling f1() , D::f2() and B2::f2() on d will be more difficult

  * (( d -> / * TBM pointer D (for B1) * / ) [ 0 ]) ( d ) // d-> f1 ();
 * (( d -> / * TBM pointer D (for B2) * / ) [ 0 ]) ( d + 8 ) // d-> f2 ();
 * (( / * TBM address B2 * / ) [ 0 ]) ( d + 8 ) // d-> B2 :: f2 ();

For comparison, calling d->f0() much simpler:

  * B1 :: f0 ( d )

A virtual call requires at least an additional indexed dereferencing, and sometimes an additional “fix”, similar to a non-virtual call, which is a simple transition to a compiled pointer. Therefore, calling virtual functions is essentially slower than calling non-virtual ones. An experiment conducted in 1996 showed that approximately 6–13% of the execution time is spent simply on searching for the corresponding function, while the overall increase in the execution time can reach 50% ^[2] . The cost of using virtual functions on modern processor architectures may not be so high due to the presence of significantly larger caches and better transition prediction .

In an environment where JIT compilation is not used, calls to virtual functions usually cannot be internal . While the compiler can replace viewing and indirect calling, for example, by conditionally executing each internal body, such optimization is not common.

To avoid such losses, compilers usually avoid using vtable whenever a call can be made at compile time.

Thus, the above call to f1 may not require viewing vtable, since the compiler can report that d can have only D at this point, and D does not redefine f1 . Or the compiler (as an option, the optimizer) can detect the absence of subclasses of B1 in a program that overrides f1 . A call to B1::f1 or B2::f2 probably not require a vtable scan due to an implementation defined explicitly (although binding on the 'this' pointer is still required).

Vtable generally sacrifices performance to achieve a dynamic choice, but there are many alternatives to it, such as binary tree selection, which has higher performance but different execution speed ^[3] .

However, vtable is provided only for single dispatch by the special "this" parameter, as opposed to multiple dispatch (as in CLOS or Dylan ), where the types of all parameters can be assigned during dispatch.

Vtable also works only if dispatching is limited to a known set of methods, so many vtable can be placed in a simple array at compile time, unlike languages ​​that support duck typing (for example, Smalltalk , Python or JavaScript ).

Languages ​​that support one or both of these options often dispatch by searching for a row in a hash table or another equivalent method. There are a fairly large number of tricks to increase speed (for example, tokenization of method names, application of caching, JIT compilation), and dispatch time often does not significantly affect the overall processing time, but despite this, viewing vtable is noticeably faster. Vtable is also easier to implement and debug, and also closer to the "C language philosophy" than hash tables of strings.

• Virtual inheritance
• Branch table

1. ↑ The G ++ -fdump-class-hierarchy argument can be used to reset TBM (for “manual” checking. For the AIX VisualAge XlC compiler, use -qdump_class_hierarchy to reset the class hierarchy and the TVF schema.

1. ↑ Ellis & Stroustrup 1990, pp. 227–232
2. ↑ Driesen, Karel and Hölzle, Urs, "The Direct Cost of Virtual Function Calls in C ++" , OOPSLA 1996
3. ↑ 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)

• Virtual Functions - Low Level View (article)
• Margaret A. Ellis and Bjarne Stroustrup (1990) The Annotated C ++ Reference Manual. Reading, MA: Addison-Wesley. ( ISBN 0-201-51459-1 )
• Lecture. Virtual functions and polymorphism / Summaries of the course on C ++ 2010/11, St. Petersburg Department of Mathematical Institute. V.A. Steklova RAS
• 5.4.4. Virtual Function Table (p. 43) / Object-Oriented Programming (Tutorial). Shahgeldyan K.I., ed. Alexandrova L.I. Vladivostok State University of Economics and Service