Virtual table/dispatch table

Question

From what I know of CPP, each class has its own vtable.

However this wikipedia link mentions:

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.

Can someone please shed some light.

Thanks !

Solution 1

It's sometimes easier to understand with an example:

class PureVirtual {
   public:
       virtual void methodA() = 0;
       virtual void methodB() = 0;
};

class Base : public PureVirtual {
   public:
        virtual void methodA();
        void methodC();
   private:
        int x;
 };

 class Derived : public Base {
    public:
         virtual void methodB();
    private:
         int y;
 };

So, given an object of type Derived it might look like:

                         ------------
 Known offset for vtable |  0xblah  | -------> [Vtable for type "Derived"]
                         ------------
 Known offset for x      |  3       |
                         ------------
 Known offset for y      |  2       |
                         ------------

With the Vtable for type "Derived" looking something like:

                            ------------
 Known offset for "methodA" | 0xblah1   | ------> methodA from Base
                            -------------
 Known offset for "methodB" | 0xblah2   | ------> methodB from Derived
                            -------------

Note that since "methodC" was not virtual, it is not in the vtable at all. Also note that all instances of class Derived will have a vtable pointer to the same, shared vtable object (since they have the same type).

Though the implementations for C++ and Java are slightly different, the ideas are not incompatible. The key difference, from a conceptual standpoint, is that Java methods are "virtual" unless declared "final". In C++ the keyword "virtual" must be given explicitly for the function to be in the vtable. Anything not in vtable will be dispatched using the compile-time types rather than the runtime type of the object.

Solution 2

Yes, virtual methods are treated differently by the compiler and the runtime.

Java : All methods in java are virtual by default. That means that any method can be overridden when used in inheritance, unless that method is declared as final or static.

From the VM Specification,

The Java virtual machine does not mandate any particular internal structure for objects. The book mark there states: In some of Sun's implementations of the Java virtual machine, a reference to a class instance is a pointer to a handle that is itself a pair of pointers: one to a table containing the methods of the object and a pointer to the Class object that represents the type of the object, and the other to the memory allocated from the heap for the object data.

---

C++ :

Whenever a class member function is declared as virtual, the compiler creates a virtual table in memory which contains all function pointers that are declared as virtual in that class. This enables run time polymorphism (i.e. finding out the desired function at run time). Virtual function tables also have an additional pointer in the object to the vtable. As this additional pointer and the vtable increases the size of the object, a class designer needs to be judicious about declaring functions virtual.

The sequence of events upon calling a method on the base object pointer is :

• Get vtable pointer (this vtable pointer points to the beginning of the vtable).
• Get the function pointers in the vtable using offset.

Invoke the function indirectly through the vtable pointer.

Solution 3

Every class having virtual functions (i.e. in Java it's just 'every class') has its own vtable. Each object has hidden a reference to it's class vtable. So, objects of the same class have identical references.

When you make call of virtual method compiler usually makes a lookup:

obj.method(args);

is translated into something

obj.vtable[idx_method](obj, args);

Sometimes, if compiler can deduce particular type of object, it can emit static call instead of virtual. So, code

MyObject obj(ctor_args);
....
obj.method(args);

can be translated into

MyObject_method(obj, args);

Which will usually execute faster than virtual call.

Comments

[Štěpán Němejc]

Note - not all classes in C++ have vtables. Only the ones with virtual functions have. When there are no virtual functions, all methods can be statically bound (at compile time), and the dispatch mechanism is not needed at run time.

[codeObserver]

thnx .. you mean the other way round .. each class has a dispatch table that is shared by its instances[objects]