How Does the C++ Compiler Know Which Implementation of a Virtual Function to Call

How does the C++ compiler know which implementation of a virtual function to call?

Each object (that belongs to a class with at least one virtual function) has a pointer, called a vptr. It points to the vtbl of its actual class (which each class with virtual functions has at least one of; possibly more than one for some multiple-inheritance scenarios).

The vtbl contains a bunch of pointers, one for each virtual function. So at runtime, the code just uses the object's vptr to locate the vtbl, and from there the address of the actual overridden function.

In your specific case, Polygon, Rectangle, and Triangle each has a vtbl, each with one entry pointing to its relevant area method. Your ppoly1 will have a vptr pointing to Rectangle's vtbl, and ppoly2 similarly with Triangle's vtbl. Hope this helps!

How does the compiler know which virtual function to call in this situation?

There are two topics in your question:

How does the compiler know which function to use, given some classes have multiple functions with the same name?

Well, they may have the same name, but they don't have the same signature. There is no ambiguity between eval() and eval(x,y) calls, because there is only one eval that doesn't accept any arguments and only one eval that accepts two arguments.

Given Expression* e how does the compiler know which function to call in e->eval() expression?

The answer is that the compiler does not know. This happens at runtime, not during compilation. Unless an advanced optimization technique, called devirtualization, applies (which is a big topic that I'm not going to talk about here).

Typically¹ when define virtual functions on a class, your compiler will store additional data within each object of that type, so called vtable, which is just an array of function pointers. Then when you do e->eval() on a virtual method, the compiler will replace this call with two steps: (1) get function pointer from the vtable stored in e object corresponding to eval virtual method, (2) call that function pointer with e object (and potentially other arguments).

_{¹: this is an implementation detail, one of the possible strategies, not necessarily what happens exactly.}

How does the compiler know which entry in vtable corresponds to a virtual function?

I'll modify your example a little so it shows more interesting aspects of object orientation.

Suppose we have the following:

#include <iostream>

struct Animal
{
  int age;
  Animal(int a) : age {a} {}
  virtual int setAge(int);
  virtual void sayHello() const;
};

int
Animal::setAge(int a)
{
  int prev = this->age;
  this->age = a;
  return prev;
}

void
Animal::sayHello() const
{
  std::cout << "Hello, I'm an " << this->age << " year old animal.\n";
}

struct Tiger : Animal
{
  int stripes;
  Tiger(int a, int s) : Animal {a}, stripes {s} {}
  virtual void sayHello() const override;
  virtual void doTigerishThing();
};

void
Tiger::sayHello() const
{
  std::cout << "Hello, I'm a " << this->age << " year old tiger with "
            << this->stripes << " stripes.\n";
}

void
Tiger::doTigerishThing()
{
  this->stripes += 1;
}

int
main()
{
  Tiger * tp = new Tiger {7, 42};
  Animal * ap = tp;
  tp->sayHello();         // call overridden function via derived pointer
  tp->doTigerishThing();  // call child function via derived pointer
  tp->setAge(8);          // call parent function via derived pointer
  ap->sayHello();         // call overridden function via base pointer
}

I'm ignoring the good advice that classes with virtual function members should have a virtual destructor for the purpose of this example. I'm going to leak the object anyway.

Let's see how we can translate this example into good old C where there are no member functions, leave alone with virtual ones. All of the following code is C, not C++.

The struct animal is simple:

struct animal
{
  const void * vptr;
  int age;
};

In addition to the age member, we have added a vptr that will be the pointer to the vtable. I'm using a void pointer for this because we'll have to do ugly casts anyway and using void * reduces the ugliness a little.

Next, we can implement the member functions.

static int
animal_set_age(void * p, int a)
{
  struct animal * this = (struct animal *) p;
  int prev = this->age;
  this->age = a;
  return prev;
}

Note the additional 0-th argument: the this pointer that is passed implicitly in C++. Again, I'm using a void * pointer as it will simplify things later on. Note that inside any member function, we always know the type of the this pointer statically so the cast is no problem. (And at the machine level, it doesn't do anything at all anyways.)

The sayHello member is defined likewise except that the this pointer is const qualified this time.

static void
animal_say_hello(const void * p)
{
  const struct animal * this = (const struct animal *) p;
  printf("Hello, I'm an %d year old animal.\n", this->age);
}

Time for the animal vtable. First we have to give it a type, which is straight-forward.

struct animal_vtable_type
{
  int (*setAge)(void *, int);
  void (*sayHello)(const void *);
};

Then we create a single instance of the vtable and set it up with the correct member functions. If Animal had have a pure virtual member, the corresponding entry would have a NULL value and were better not dereferenced.

static const struct animal_vtable_type animal_vtable = {
  .setAge = animal_set_age,
  .sayHello = animal_say_hello,
};

Note that animal_set_age and animal_say_hello were declared static. That's onkay because they will never be referred to by-name but only via the vtable (and the vtable only via the vptr so it can be static too).

We can now implement the constructor for Animal…

void
animal_ctor(void * p, int age)
{
  struct animal * this = (struct animal *) p;
  this->vptr = &animal_vtable;
  this->age = age;
}

…and the corresponding operator new:

void *
animal_new(int age)
{
  void * p = malloc(sizeof(struct animal));
  if (p != NULL)
    animal_ctor(p, age);
  return p;
}

About the only thing interesting is the line where the vptr is set in the constructor.

Let's move on to tigers.

Tiger inherits from Animal so it gets a struct tiger sub-object. I'm doing this by placing a struct animal as the first member. It is essential that this is the first member because it means that the first member of that object – the vptr – has the same address as our object. We'll need this later when we'll do some tricky casting.

struct tiger
{
  struct animal base;
  int stripes;
};

We could also have simply copied the members of struct animal lexically at the beginning of the definition of struct tiger but that might be harder to maintain. A compiler doesn't care about such stylistic issues.

We already know how to implement the member functions for tigers.

void
tiger_say_hello(const void * p)
{
  const struct tiger * this = (const struct tiger *) p;
  printf("Hello, I'm an %d year old tiger with %d stripes.\n",
         this->base.age, this->stripes);
}

void
tiger_do_tigerish_thing(void * p)
{
  struct tiger * this = (struct tiger *) p;
  this->stripes += 1;
}

Note that we are casting the this pointer to struct tiger this time. If a tiger function is called, the this pointer had better point to a tiger, even if we are called through a base pointer.

Next to the vtable:

struct tiger_vtable_type
{
  int (*setAge)(void *, int);
  void (*sayHello)(const void *);
  void (*doTigerishThing)(void *);
};

Note that the first two members are exactly the same as for animal_vtable_type. This is essential and basically the the direct answer to your question. It would have been more explicit, perhaps, if I had placed a struct animal_vtable_type as the first member. I want to emphasize that the object layout would have been exactly the same except that we couldn't play our nasty casting tricks in this case. Again, these are aspects of the C language, not present at machine level so a compiler is not bothered by this.

Create a vtable instance:

static const struct tiger_vtable_type tiger_vtable = {
  .setAge = animal_set_age,
  .sayHello = tiger_say_hello,
  .doTigerishThing = tiger_do_tigerish_thing,
};

And implement the constructor:

void
tiger_ctor(void * p, int age, int stripes)
{
  struct tiger * this = (struct tiger *) p;
  animal_ctor(this, age);
  this->base.vptr = &tiger_vtable;
  this->stripes = stripes;
}

The first thing the tiger constructor does is calling the animal constructor. Remember how the animal constructor sets the vptr to &animal_vtable? This is the reason why calling virtual member functions from a base class constructor ofter surprises people. Only after the base class constructor has run, we re-assign the vptr to the derived type and then do our own initialization.

operator new is just boilerplate.

void *
tiger_new(int age, int stripes)
{
  void * p = malloc(sizeof(struct tiger));
  if (p != NULL)
    tiger_ctor(p, age, stripes);
  return p;
}

We're done. But how do we call a virtual member function? For this, I'll define a helper macro.

#define INVOKE_VIRTUAL_ARGS(STYPE, THIS, FUNC, ...)                     \
  (*((const struct STYPE ## _vtable_type * *) (THIS)))->FUNC( THIS, __VA_ARGS__ )

Now, this is ugly. What it does is taking the static type STYPE, a this pointer THIS and the name of the member function FUNC and any additional arguments to pass to the function.

Then, it constructs the type name of the vtable from the static type. (The ## is the preprocessor's token pasting operator. For example, if STYPE is animal, then STYPE ## _vtable_type will expand to animal_vtable_type.)

Next, the THIS pointer is casted to a pointer to a pointer to the just derived vtable type. This works because we've made sure to put the vptr as the first member in every object so it has the same address. This is essential.

Once this is done, we can dereference the pointer (to get the actual vptr) and then ask for its FUNC member and finally call it. (__VA_ARGS__ expands to the additional variadic macro arguments.) Note that we also pass the THIS pointer as the 0-th argument to the member function.

Now, the acatual truth is that I had to define an almost identical macro again for functions that take no arguments because the preprocessor does not allow a variadic macro argument pack to be empty. So shall it be.

#define INVOKE_VIRTUAL(STYPE, THIS, FUNC)                               \
  (*((const struct STYPE ## _vtable_type * *) (THIS)))->FUNC( THIS )

And it works:

#include <stdio.h>
#include <stdlib.h>

/* Insert all the code from above here... */

int
main()
{
  struct tiger * tp = tiger_new(7, 42);
  struct animal * ap = (struct animal *) tp;
  INVOKE_VIRTUAL(tiger, tp, sayHello);
  INVOKE_VIRTUAL(tiger, tp, doTigerishThing);
  INVOKE_VIRTUAL_ARGS(tiger, tp, setAge, 8);
  INVOKE_VIRTUAL(animal, ap, sayHello);
  return 0;
}

You might be wondering what happens in the

INVOKE_VIRTUAL_ARGS(tiger, tp, setAge, 8);

call. What we are doing is to invoke the non-overridden setAge member of Animal on a Tiger object referred to via a struct tiger pointer. This pointer is first implicitly casted to a void pointer and as such passed as the this pointer to animal_set_age. That function then casts it to a struct animal pointer. Is this correct? It is, because we were careful to put the struct animal as the very first member in struct tiger so the address of the struct tiger object is the same as the address for the struct animal sub-object. It's the same trick (only one level less) we were playing with the vptr.

How does compiler resolves virtual functions accessing non-virtual data members C++

This is all implementation detail, and different compilers do different things. There are two common approaches to the problem but both depend on fixing what the this pointer refers to in the function definition.

One approach is to have the this pointer always referring to the complete object (at least at the level of the final overrider of that virtual function). In this approach, and in the presence of multiple inheritance, the entries in the vtable don't contain a pointer to the actual function, but a pointer to a trampoline that adjusts the this pointer and then jumps to the overrider. The advantage of this approach is that for the leftmost non-empty base and in all cases of single inheritance the entry in the vtable is really the overrider and there is no cost associated. This is the approach taken in the Itanium C++ ABI, which is used in different OS, including Linux.

Another approach is to always pass the address of the subobject that first declared the member function. In this case the caller adjusts the this pointer to refer to the subobject before jumping through the vtable. As in the first case, if there is no offset (first nonempty base, single inheritance) the compiler does not need to add any adjustment and no cost is incurred. Inside the implementation of the final overrider, the compiler uses offsets from the pointer of the base that declared the function, rather than offsets from the complete object. I believe this is the case in Windows/Visual Studio, but don't take my word here, as I don't have access to the VS C++ ABI to confirm this.

A third approach is to store in the vtable the adjustment directly. This approach is less common and incurs the cost of adjusting the offset even when it needs not be updated (by adding 0). I don't know of any current compiler that uses this approach.

How does the compiler generate code for virtual function calls?

What your picture is missing is an arrow from a CAT and a SmallCAT objects to their corresponding vtbls. The compiler embeds a pointer to vtbl into the object itself - one can think of it as a hidden member variable. That is why it is said that adding the first virtual function "costs" you one pointer per object in memory footprint. The pointer to vtbl is set up by the code in the constructor, so all the compiler-generated virtual call needs to do in order to get to its vtable at runtime is dereferencing the pointer to this.

Of course this gets more complicated with virtual and multiple inheritance: the compiler needs to generate a slightly different code, but the basic process remains the same.

Here is your example explained in more details:

CAT *p1,*p2;
p1 = new SmallCat;  //suppose its vtbl address is 0x1234;
// The layout of SmallCat object includes a vptr as a hidden member.
// At this point, the value of this vptr is set to 0x1234.
p2 = new CAT;       //suppose its vtbl address is 0x5678;
// The layout of Cat object also includes a vptr as a hidden member.
// At this point, the value of this vptr is set to 0x5678.
(*p1->vptr[i])(p); //should use vtbl at 0x1234
// Compiler has enough information to do that, because it squirreled away 0x1234
// inside the SmallCat object at the time it was constructed.
(*p2->vptr[i])(p); //should use vtbl at 0x5678
// Same deal - the constructor saved 0x5678 inside the Cat, so we're good.

Why do we need virtual functions in C++?

Without "virtual" you get "early binding". Which implementation of the method is used gets decided at compile time based on the type of the pointer that you call through.

With "virtual" you get "late binding". Which implementation of the method is used gets decided at run time based on the type of the pointed-to object - what it was originally constructed as. This is not necessarily what you'd think based on the type of the pointer that points to that object.

class Base
{
  public:
            void Method1 ()  {  std::cout << "Base::Method1" << std::endl;  }
    virtual void Method2 ()  {  std::cout << "Base::Method2" << std::endl;  }
};

class Derived : public Base
{
  public:
    void Method1 ()  {  std::cout << "Derived::Method1" << std::endl;  }
    void Method2 ()  {  std::cout << "Derived::Method2" << std::endl;  }
};

Base* basePtr = new Derived ();
  //  Note - constructed as Derived, but pointer stored as Base*

basePtr->Method1 ();  //  Prints "Base::Method1"
basePtr->Method2 ();  //  Prints "Derived::Method2"

EDIT - see this question.

Also - this tutorial covers early and late binding in C++.

How does the compiler determine which polymorphic type it is addressing

In effect, presuming a “normal” C implementation such as yours, much of the data of class B is a structure, and the first member of that structure is an object of class A. Since both B and the A that it contains start at the same place, they have the same address.

Because there is an A object at the start of B, you can convert a pointer to the B object to a pointer to the A object, and it acts like an A object because it is: It is a pointer to the A data.

Virtual functions are more complicated. Inside the A data, not usually visible to you, is a pointer to a table. If the object were really a plain A object, that pointer would point to a table that has the addresses of the virtual functions for A. If the object is a B object, then that pointer points to a table that has the addresses of the virtual functions for B. The result is that, if you have a pointer whose compile-time type appears to be pointer-to-A, the compiler calls its functions by looking up their addresses in the table. If the actual type of the pointed-to object is B, this table provides the addresses of the virtual functions for B.

How are virtual functions and vtable implemented?

How are virtual functions implemented at a deep level?

From "Virtual Functions in C++":

Whenever a program has a virtual function declared, a v - table is constructed for the class. The v-table consists of addresses to the virtual functions for classes that contain one or more virtual functions. The object of the class containing the virtual function contains a virtual pointer that points to the base address of the virtual table in memory. Whenever there is a virtual function call, the v-table is used to resolve to the function address. An object of the class that contains one or more virtual functions contains a virtual pointer called the vptr at the very beginning of the object in the memory. Hence the size of the object in this case increases by the size of the pointer. This vptr contains the base address of the virtual table in memory. Note that virtual tables are class specific, i.e., there is only one virtual table for a class irrespective of the number of virtual functions it contains. This virtual table in turn contains the base addresses of one or more virtual functions of the class. At the time when a virtual function is called on an object, the vptr of that object provides the base address of the virtual table for that class in memory. This table is used to resolve the function call as it contains the addresses of all the virtual functions of that class. This is how dynamic binding is resolved during a virtual function call.

Can the vtable be modified or even directly accessed at runtime?

Universally, I believe the answer is "no". You could do some memory mangling to find the vtable but you still wouldn't know what the function signature looks like to call it. Anything that you would want to achieve with this ability (that the language supports) should be possible without access to the vtable directly or modifying it at runtime. Also note, the C++ language spec does not specify that vtables are required - however that is how most compilers implement virtual functions.

Does the vtable exist for all objects, or only those that have at least one virtual function?

I believe the answer here is "it depends on the implementation" since the spec doesn't require vtables in the first place. However, in practice, I believe all modern compilers only create a vtable if a class has at least 1 virtual function. There is a space overhead associated with the vtable and a time overhead associated with calling a virtual function vs a non-virtual function.

Do abstract classes simply have a NULL for the function pointer of at least one entry?

The answer is it is unspecified by the language spec so it depends on the implementation. Calling the pure virtual function results in undefined behavior if it is not defined (which it usually isn't) (ISO/IEC 14882:2003 10.4-2). In practice it does allocate a slot in the vtable for the function but does not assign an address to it. This leaves the vtable incomplete which requires the derived classes to implement the function and complete the vtable. Some implementations do simply place a NULL pointer in the vtable entry; other implementations place a pointer to a dummy method that does something similar to an assertion.

Note that an abstract class can define an implementation for a pure virtual function, but that function can only be called with a qualified-id syntax (ie., fully specifying the class in the method name, similar to calling a base class method from a derived class). This is done to provide an easy to use default implementation, while still requiring that a derived class provide an override.

Does having a single virtual function slow down the whole class or only the call to the function that is virtual?

This is getting to the edge of my knowledge, so someone please help me out here if I'm wrong!

I believe that only the functions that are virtual in the class experience the time performance hit related to calling a virtual function vs. a non-virtual function. The space overhead for the class is there either way. Note that if there is a vtable, there is only 1 per class, not one per object.

Does the speed get affected if the virtual function is actually overridden or not, or does this have no effect so long as it is virtual?

I don't believe the execution time of a virtual function that is overridden decreases compared to calling the base virtual function. However, there is an additional space overhead for the class associated with defining another vtable for the derived class vs the base class.

Additional Resources:

http://www.codersource.net/published/view/325/virtual_functions_in.aspx (via way back machine)

http://en.wikipedia.org/wiki/Virtual_table

http://www.codesourcery.com/public/cxx-abi/abi.html#vtable

---

Related Topics