Virtual Methods

Virtual functions are a fairly well-understood programming construct in terms of how and when to use them. But have you ever stopped to think about how they actually work under the hood? You’ve probably heard the term “vtable” thrown around at some point, but do you have a firm understanding of what one is? I’d like to cover a bit of the gritty details so you can leave with a bit more arcane knowledge than you arrived with.

Before we dive into the details, a brief refresher is in order. Classes can contain instance methods, which are methods that have access to per-instance data. But these instance methods can also be declared to be “virtual”, which is the backbone of polymorphism support in C++ (as well as many other languages). While virtual methods can still access all of the per-instance data on a class, they differ from instance methods in their call semantics. When you have a class B and you call an instance method F on it, you will always call B::F. When you have a class B and you call a virtual method G on it, you will call the most-derived inheritor of B’s G on it. In code:

class B {
public:
  void F( void ) {
  }

  virtual void G( void ) {
  }
};

class C : public B {
public:
  void F( void ) {  // NOTE: this hides B::F!
  }

  void G( void ) {
  }
};

// Using the classes
B b;
C c;
B *d = new C();

b.F();  // Calls B::F
b.G();  // Calls B::G

c.F();  // Calls C::F
c.G();  // Calls C::G

d->F();  // Calls B::F
d->G();  // Calls C::G

The interesting case is the variable “d”. Because G is a virtual function, when d->G is called, the compiler uses the “dynamic type” of the variable to determine what to call. Since d was assigned a new instance of C, then C::G is called. Because F is not a virtual function, when d->F is called, the compiler uses the “static type” of the variable to determine what to call. Since d was declared as a B, then B::F is called.

This demonstrates the key concept with virtual functions — the dynamic type of the class is what ultimately determines what function gets called at runtime. With non-virtual functions, the dynamic type plays no role — the compiler uses the static type to determine what function to call, and it can do so at compile time.

Now that you’ve got a quick refresher on virtual methods, let’s take a look at some of the details of how they work. The first topic to cover is the theory behind how compilers generally treat classes. One thing to remember is that this information may not apply to all compilers in all circumstances. It is left up to the compiler writer to determine what memory layout a class will occupy, and how to do virtual method dispatching, etc. The only requirement imposed on the compiler writer is the semantics of the operations, not the actual implementation details.

A class is really just a template (not in the C++ templates sense). It’s a definition of what data and methods are available. So a class definition by itself doesn’t occupy any space at runtime because it only exists within the compiler. As a strange analogy: when you want to make cookies, you take the cookie cutter and press it into the dough. You can do this over and over again, so long as there is dough left. Each one of the cookies comes out looking exactly the same in terms of the shape, but you can decorate the cookies any way you like. Now you can think of the class definition as being the cookie cutter, the machine’s memory as the cookie dough, instance variable values as the decorations, and the compiler is the “cook” cutting out the dough. The class definition (cookie cutter) is something the compiler uses (the cook) in order to make class instances (the cut-out cookies) which can be modified at runtime (the decorations). It is important to understand that the contents of a class definition are what dictate the structure of a class instance at runtime. Once you have a class instance, you can change it independent of any other instances of the same class.

Let’s look at a simple example.

class B {
  int i;

public:
  B() : i( 42 ) {}

  void F( void ) {
    i = 0;
  }

  virtual void G( void ) {
    i = 1;
  }
};

The template used by the compiler will look something like this:

Offset Field Size
0 vtable sizeof(void*)
4 i sizeof(int)

The first thing to note is that the pointer to the vtable is generally the first thing in the class layout, but there’s no hard and fast requirement that it be the first field, so it is not wise to rely on this. This table is really an array of function pointers. So keep in mind that there’s actually two levels of indirection at work. The first is getting the address of the table itself, the second is getting the address of the function pointer within the table.

The vtable is the place where virtual functions are stored (as well as the default constructor, sometimes) and is the mechanism by which virtual function dispatch works. We’ll come back to this. Following the vtable are the data members of the class. By using such a layout, each instance of the class will have its own vtable and its own variable “i.” You’ll notice that class methods do not take up any space in the layout — the address of class methods can be calculated at compile time.

Let’s see how the layout changes when we add a derived class.

class C : public B {
  double d;

public:
  C() : d( 1.0 ), B() {}

  void F( void ) {  // NOTE: this hides B::F!
    d = 3.14;
  }

  void G( void ) {
    d = 2.0;
  }
};

The template used by the compiler will look something like this:

Offset Field Size
0 vtable sizeof(void*)
4 i sizeof(int)
8 d sizeof(double)

There is still only one pointer to the vtable, and following it are the base class member variables, and following that are the derived class member variables. Again, there is no rule stating this is the way it must be. But the basic idea will be the same from compiler to compiler in that there needs to be space for all of the member variables.

So now that you have an idea of what the class layout looks like, let’s look at what the actual memory looks like for the following code:

B b1;
C c;
B *b2 = new C();

In this case, we have three different class instances. Here is an example of what they might look like in memory:

b1
Address Field Size Value
0x12005000 vtable sizeof(void*) 0x00345080
0x12005004 i sizeof(int) 42
c
Address Field Size Value
0x02425000 vtable sizeof(void*) 0x00169068
0x02425004 i sizeof(int) 42
0x02425008 d sizeof(double) 1.0
b2
Address Field Size Value
0x00346700 vtable sizeof(void*) 0x00169068
0x00346704 i sizeof(int) 42
0x00346708 d sizeof(double) 1.0
vtables
Address Value
0x00345080 index 0: 0x00e04580
0x00169068 index 0: 0x00e04584
0x00e04580 B::G
0x00e04584 C::G

The vtable pointers for b1 and c should come as no real surprise. In the case of b1, the static and dynamic type of the variable are both B, so that is why B::G is called. In the case of c, the static and dynamic types are both C, so that is why C::G is called.

However, the table for b2 demonstrates the purpose to vtables. The static type of the variable is B, but the dynamic type is C. The pointer to the vtables always goes off the dynamic type so that you will call the most-derived type in the class hierarchy, so that is why b2 is calling C::G even though the static type is B. This is the important “black magic” that allows virtual method dispatch and polymorphism. The compiler generates a vtable, and the slots within that table list which virtual methods get called based on the dynamic type of the variable.

You might be wondering why you need vtables at all if the compiler can just generate one. Now would be a good time to remember Polymorphism 101:

Base *SomeFunction( int i ) {
  if (i == 0) return new Derived1();
  else if (i == 1) return new Derived2();
  else return new Derived3();
}

Base *b = SomeFunction( rand() % 3 );

In this case, the compiler can’t figure out at compile time exactly what vtable to put into b. Instead, it generates the class instance within SomeFunction, and assigns it into b on return from SomeFunction. So vtables truly are the key to performing polymorphic operations.

So what happens in the case of multiple inheritance?

class Base1 {
  int i;
public:
  Base1() : i( 42 ) {}

  virtual void B() {
    i = 10;
  }
};

class Base2 {
  double d;
public:
  Base2() : d( 1.0 ) {}

  virtual void C() {
  }

  virtual void D() {
  }
};

class Derived : public Base1, public Base2 {
  char *s;
public:
  Derived() : s( "Hello World" ), Base1(), Base2() {}

  void C() {
  }

  void K() {
  }
};

Derived d;

So what does the memory layout look like for d?

d
Address Field Size Value
0x00045032 vtable sizeof(void*) 0x00345080
0x00045036 i sizeof(int) 42
0x0004503A vtable sizeof(void*) 0x00169068
0x0004503E d sizeof(double) 1.0
0x00045046 s sizeof(char*) 0x0016907C
Memory & vtables
Address Value
0x00345080 index 0: 0x00e04580
0x00169068 index 0: 0x00e04584
0x00169068 index 1: 0x00e04588
0x0016907C Hello World
0x00e04580 Base1::B
0x00e04584 Base2::C
0x00e04588 Base2::D

You’ll notice that d has not one, but two vtable pointers! The reason for this is because Base1 and Base2 can represent totally different class hierarchies, and Derived inherits from both. Both class hierarchies can have entirely different vtables, and so all Derived objects need to have the vtable pointers to handle them. Not all compilers will generate multiple vtables, but the general rule of thumb is: for each base class that contains at least one virtual function in its class hierarchy, there will be a vtable in the derived class. Two base classes with a virtual function in each means two vtables in the derived class.

One thing to remember is that virtual functions will add to the memory requirements for a class by requiring a vtable, as well as reduce the performance due to the extra level of indirection when making a function call to a virtual function. Once you start to add multiple inheritance into the mix, the costs go up even higher. So virtual method dispatch is not something that happens “for free”, but without it polymorphism couldn’t happen. Everything’s a tradeoff!

I’ve rambled on far longer than I had intended, but hopefully you have learned a bit more about how virtual functions and class layouts work in C++. Or at least I hope I haven’t confused you further!

Update 10/5/11: Big thanks to Dan for pointing out some flaws in my explanations! I’ve corrected them inline, but the basic point I failed to drive home was: a class definition has a vtable layout that can be determined at compile time. A class instance has a pointer to the proper class vtable, and that pointer is filled out at runtime. So for the class definition, there is only one vtable in memory regardless of how many class instances there are. Each instance points back to the same vtable when appropriate. Previously, I had mucked this up by showing each class instance having a pointer to its own vtable in memory instead of pointing back to the same class vtable for every instance. Apologies for any confusion or misinformation!

This entry was posted in C/C++ and tagged , . Bookmark the permalink.

7 Responses to Virtual Methods

  1. Dan says:

    Hi Aaron,

    This is where I swallow my pride & look stupid, all in the name of trying to learn / understand. Here we go…

    In your first example with the (much appreciated) colored highlighting, where you show the layout of b2, I guess it’s really the layout of *b2, would that be correct? In other words, the C object (created via new()) lives at 0×00346700, correct?

    Assuming that’s correct… c is an object of type C which lives at address &c, or 0x0242.5000, and at address b2 we have another object of type C which lives at 0x0034.7600 (I always put a “.” every 16 bits so I can keep track).

    My question is this: since memory 0x0242.5000 and 0x0034.7600 hold 2 distinct “C” objects, shouldn’t a dump of their contents be the same (at least the vtable part at the start – forget about member variable contents, which could vary at runtime).

    I guess my question, stated another way, is this: are you sure that memory 0×00346700, which holds the vtable for a “C” object, is 0×67005244 and not 0×00169068? The C object at 0×00346700 doesn’t know or care how many B*s or C*s are pointing at it, its layout is still the layout of a C object, so its vtable (the first entry in our memory model) should be the same for “c” and “*b2”, right?

    I hope my question makes sense. It could be that I’m on Mars, and that is *exactly* the point of your article, but my understanding is that each class has (at most) 1 vtable, all instances of the class use/reference the same vtable (whose contents are decided at compile time), and at run time, by indexing into the vtable (even through a blisfully unaware base class pointer) we get our polymorphic behavior.

    tl;dr – are you sure the “blue 0×67005244” shouldn’t be a “green 0×00169068”?

    Thanks for the clarification!

  2. Aaron Ballman says:

    In your first example with the (much appreciated) colored highlighting, where you show the layout of b2, I guess it’s really the layout of *b2, would that be correct? In other words, the C object (created via new()) lives at 0×00346700, correct?

    That’s correct — C *b2 starts at memory location 0×00346700, and the first field at that address is the vtable.

    Assuming that’s correct… c is an object of type C which lives at address &c, or 0×0242.5000, and at address b2 we have another object of type C which lives at 0×0034.7600 (I always put a “.” every 16 bits so I can keep track).

    Correct as well.

    My question is this: since memory 0×0242.5000 and 0×0034.7600 hold 2 distinct “C” objects, shouldn’t a dump of their contents be the same (at least the vtable part at the start – forget about member variable contents, which could vary at runtime).

    I guess my question, stated another way, is this: are you sure that memory 0×00346700, which holds the vtable for a “C” object, is 0×67005244 and not 0×00169068? The C object at 0×00346700 doesn’t know or care how many B*s or C*s are pointing at it, its layout is still the layout of a C object, so its vtable (the first entry in our memory model) should be the same for “c” and “*b2″, right?

    The layout of the vtables will be the same for all C objects in that the number of valid indices will be the same. But the values within the vtables may or may not be different between different C objects.

    Another way to think about it would be: imagine if class C had an array of 10 ints (int a[10]). Every instance of C would have the same layout, but they would not share the same memory location. This allows the values within the array to be different from instance to instance. Now just replace “int” with “function pointer” and you’ve got the basic concept of a vtable.

    I hope my question makes sense. It could be that I’m on Mars, and that is *exactly* the point of your article, but my understanding is that each class has (at most) 1 vtable, all instances of the class use/reference the same vtable (whose contents are decided at compile time), and at run time, by indexing into the vtable (even through a blisfully unaware base class pointer) we get our polymorphic behavior.

    This was a fantastic question! This stuff is hard to visualize in many regards, so it can be quite confusing. But your understanding isn’t quite true to the real world. I skirted around some of the points you raise, but hope to have a future post that goes into more depth.

    Classes can have multiple vtables, for instance when multiple inheritance is involved. In that case, you may need a vtable for each of the base classes separately. This also changes the way functions within the vtables are called, possibly!

    All instances of the class will have the same memory layout for the vtable (they have the same number of entries in the array, the order of the functions in the array is the same, etc). But they do not have to share the actual vtable itself (though they could, perhaps, share the same space if the entries can be proven to always be identical between two instances).

    I think the key part that I may not have conveyed properly is what that indexing actually means. Going back to the array of integers concept:

    class Foo {
    public:
      int a[10];
    };
    
    Foo f1, f2;
    f1.a[ 0 ] = 12;
    f2.a[ 0 ] = 42;
    

    It’s the same basic principle at play here. The layout of f1 and f2 will be structurally identical. But the memory location of f1 and f2 must be different, and corollary to that is that Foo::a’s memory location must be different as well. Otherwise you could never have a[ 0 ] be two different values at the same time.

    Vtables are no different — each instance has its own vtable in memory so that the values within the vtable can be different. If it weren’t for this (if they shared a memory location), then all class instances would have to have identical function pointers in the vtable, and they would all behave identically (no polymorphism).

    Does that clear things up, or did I only succeed in muddying the waters further?

  3. Dan says:

    Hi Aaron,

    Thanks a lot for the detailed reply. You definitely didn’t muddy the waters any further, but I’m still at a disconnect. I’ll start with a new example, and maybe by you pointing out what my mis-assumptions are, that will make the light bulb come on.

    (By the way, *all* of this discussion, and my previous questions, are for now restricted entirely to single inheritance… perhaps a deep inheritance tree, but still for now just single inheritance.)

    In order to make the discussion concrete, I’ll state some assumptions for the example that wouldn’t necessarily hold for all compilers, CPU architectures, etc:
    – all pointers are 4 bytes
    – virtual functions are implemented via vtables (not exactly going out on a limb here, never seen it done any other way)
    – each class with at least one virtual function has a vtable (exactly one vtable actually)
    – there is at most one vtable per class (remember, right now we’re talking about single inheritance)
    – in a class’s vtable, there is one entry for each virtual function (each entry is a function pointer)
    – the contents for a class’s vtable are fully known at build time
    – each object (instance) of a class with virtual functions has as its first (hidden) item a “vptr”, simply a pointer to that class’s vtable
    – the first element in an object’s layout is its (hidden) vptr
    – every object of the same type has the same value in its hidden vptr field (not talking about ptrs to objects, but the actual objects themselves)

    My understanding of how polymorphism works is that a “B *” could really be pointing to a “class C” object (C being derived from B). So at run time, when calling a virtual method through the “B *”, we would really be accessing the vptr in a C object, and thus pulling the function pointer for the virtual function from class C’s vtable. Any virtual function of B’s that is overriden by C is a place where class C’s vtable would have a different entry (func ptr) than B’s vtable. Also, C’s vtable could be bigger, if it added new virtual functions that were not present in B.

    Put another way, my understanding of how polymorphism is implemented is this: when dealing with pointers or references to base classes, we don’t know (or care) what actual type we are pointing to (the dynamic type) – any call to a virtual function will go through the correct (dynamic type) vptr/vtable & resolve to the overridden function, if one exists. Otherwise, the entry will be a pointer to the base class’s function.

    Said another way, if C doesn’t override any of B’s virtual functions, and if C doesn’t define any new virtual functions of its own, its vtable contents (the set of function pointers) will be indentical to B’s. It might be a physically separate vtable, or maybe (no idea) the compiler would just “re-use” B’s vtable, but the contents would be the same.

    So I guess what I’m saying is that in the first example in the post (the first color highlighting), it seems like we have 2 full-blown C objects — one @ 0x02425000, and another @ 0x00346700. Assuming the first slot is the vptr, it seems that the 2 objects have different vptrs, i.e. they point to different vtables. I would expect the vptr @ 0x00242500 (169068) and @ 0x00346700 (67005244) to hold the same value (i.e., to point to the same vtable).

    It also seems that we have 2 classes (B & C), but *3* vtables — one @ 0x00345080, one @ 0x00169068, and one @ 0x67005244. That would also go against my understanding of “one vtable per class” and “one vptr per object” – again, for now only talking about single inheritance.

    So when you said:

    The layout of the vtables will be the same for all C objects in that the number of valid indices will be the same. But the values within the vtables may or may not be different between different C objects.

    It seems like that’s saying that I could have code like this:

    C a;
    C b;
    C c;
    C d;

    and each of them could have different vtables? i.e., vtables whose contents didn’t contain the same set of function pointers. I just have difficulty seeing how that would work or why it would be necessary?

    Classes can have multiple vtables, for instance when multiple inheritance is involved. In that case, you may need a vtable for each of the base classes separately. This also changes the way functions within the vtables are called, possibly!

    That I can grok, but right now (single inheritance), I don’t know why it would be necessary.

    To best illustrate my simpleton disconnect, the following is very different from my understanding as written above:

    Vtables are no different — each instance has its own vtable in memory so that the values within the vtable can be different. If it weren’t for this (if they shared a memory location), then all class instances would have to have identical function pointers in the vtable, and they would all behave identically (no polymorphism).

    It’s just that I’ve never heard that each object (“instance”) had its own vtable — vptr yes, but vtable, never heard that. And the distinction is really important.

    If this is all a big misunderstanding (we’re saying the same thing in 2 ways), or I didn’t make it clear that for now I’m only talking about single inheritance, then it makes sense. But the way I’m reading the quote above, you’re saying each instance/object has its own dedicated vtable (the array of function pointers), and of course its own vptr to that vtable — whereas I’m saying that all objects of the same type (not pointers to objects, but the objects themselves), have their own vptr, and they’re the same, i.e. they point to the same vtable. And I’m also saying that by seeing a “B *”, we don’t know which vtable the “B*” points to, because only at run time do we know what the dynamic type is.

    If I’m hopelessly dense, please don’t feel the need to set me straight a 2nd time, I’m probably just hopeless. It’s just that I thought I basic understanding of how polymorphism worked (single inheritance), and the post seemed to contradict one of the things I always took as a given – “one vptr per object, one vtable per class”.

    I am pretty sure my understanding is the same what is stated in the following URLs, but it could be that I’m reading these with a bias & not understanding what they’re really saying:

    http://www.parashift.com/c++-faq-lite/virtual-functions.html#faq-20.4
    http://www.learncpp.com/cpp-tutorial/125-the-virtual-table/

    Thanks for your patience & the series of insightful posts/articles. Hope you don’t regret blogging after trying to explain things like this!

  4. Aaron Ballman says:

    Let me start at the bottom. ;-)

    Hope you don’t regret blogging after trying to explain things like this!

    Not a chance in hell! I love this sort of conversation! Almost any time someone says “please explain”, I come away with a deeper understanding of the subject. So please, fire away with the questions.

    And I think you’ve finally gotten through to me! You are correct, my figure is actually wrong. The idea I was describing was right, but the way I was going about it was wrong.

    Under your assumptions, each class has a vtable that is calculated at compile time. The number of entries in the table is fixed, and the value of the pointers is fixed (ignoring relocations required at load time). Each instance of the class has a pointer to the vtable. The pointer may or may not be different from instance to instance, but it will always point to one of the class vtables.

    So! It’s a good thing you kept asking questions, because otherwise I wouldn’t have been able to recognize and correct my mistake! You caught the mistake initially with your first comment: c and b2 should be pointing to the same memory location, the vtable for class C.

    I’ll correct my tables (and give you attribution) post haste. Thank you for keeping on me about this one! As my friends and I like to joke: you were right, I was wrong. You are an eagle, I am pond scum. You have straight teeth, and mine are crooked. And so on. ;-)

  5. Dan says:

    Hi Aaron,

    Got slammed with a deadline, only peeking up above ground now.

    Thanks for indulging me, I was really starting to feel the ground fall away underneath me – like my mental model of C++’s vtables & vptrs was totally screwed up (with me, that is *always* possible).

    By the way — it’s much harder to blog & take a risk than to sit back & take pot shots at bloggers’ posts. So I commend you for “putting yourself out there” to explain difficult concepts & risk having to revise the original post. Thanks for taking the time to read my input. I hate “know it alls” (I sure try hard not to be one), so I’m always afraid of sounding like the kid sticking his tongue out & saying “Nah nah nah” :-) You graciously understood my questions the right way – trying to confirm my understanding.

  6. Aaron Ballman says:

    Thank you for your kind words Dan! I know it looks like I’ve only just started blogging fairly recently, but prior to this blog primarily on C++, framework design and Windows programming I wrote a blog about a programming language I was the compiler engineer for called REALbasic. I had that blog for around 6 years, with active weekly posts. So I’m no stranger to being corrected when I’ve gotten something amiss.

    I’m a firm believer that you should never stop learning. When you try to teach a particular topic, there will generally be someone who can enrich your understanding. To me, this is a good thing! I blog because I love teaching, but also because I love learning. I have to go deeper into topics, and I get help along the way from people like you.

    So thanks for taking the time to critically think about what I’ve written and challenge me on points you didn’t agree with! I hope we can go through this dance in the future too. :-)

  7. Neha says:

    Hi,

    This is definitely a wonderful explanation of a complicated concept.

    I have a slight doubt related to last example involving classes Base1, Base2 and Derived.

    In memory & vtables section for Derived object “d”, I think in vtable 0x00169068, index0 should point to Derived::C and not Base2::C, since more derived version of virtual function C() is available.

    Please let me know your thoughts.

    Thanks

Leave a Reply

Your email address will not be published. Required fields are marked *