Polymorphism is an important feature of Object Oriented Programming whereby one can represent an object in different forms, hence the name. However, its implementation between Java and C++ which could bite you if you are not aware. This blog is going to explore the following topics:
- Static Dispatch
- The need for
virtualfunctions - Dynamic Dispatcher - Looking Into Assembly
- Virtual Pointers and Virtual Tables
Static Dispatch
Here’s a snippet of Java code that would behave differently in C++:
class Shape {
public void draw() {
System.out.println("Shape");
}
}
class Triangle extends Shape {
public void draw() {
System.out.println("Triangle");
}
}
public class Main {
public static void main(String[] args) {
Shape shape = new Triangle();
shape.draw(); // prints "Triangle"
}
}
Output: Triangle
In Java, the base (parent) class can be utilized to represent different forms. Although shape is of type Shape, its value is of type Triangle. This
is completely legal as Triangle is a child class (the derived class) of Shape (i.e. Triangle is a Shape). Note that the relation is one way akin to the relationship between
a Rectangle and a Square, a square is a rectangle but a rectangle is not a square. This is one of the power of polymorphism, the ability to have
a base class act as a generic container that can represent different things.
Here’s a typical C++ implementation a novice would write:
#include <iostream>
class Shape {
public:
void draw() { std::cout << "Shape\n"; }
};
class Triangle : public Shape {
public:
void draw() { std::cout << "Triangle\n"; }
};
int main() {
Shape *shape = new Triangle();
shape->draw(); // prints "Shape"
}
Output: Shape
Unlike the Java Implementation, the novice C++ conversion gives a different output as it’s missing one important keyword.
Virtual Functions - The Missing Key Ingredient to Polymorphism
For polymorphism to work in C++, the virtual keyword was introduced to allow dynamic dispatching of function calls (i.e. resolve function calls at runtime).
In simpler terms, virtual tells the compiler that the function could be overridden in the derived class (i.e. child class). For instance,
#include <iostream>
class Shape {
public:
virtual void draw() { std::cout << "Shape\n"; }
};
class Triangle : public Shape {
public:
void draw() { std::cout << "Triangle\n"; }
};
int main() {
Shape *shape = new Triangle();
shape->draw();
}
Output: Triangle
A Peak Under The Hood - Assembly
The behavior of the object slicing will make have the following:
mov rax, QWORD PTR [rbp-8]
mov rdi, rax
call Shape::draw()
Note: GCC 15.2 amd64 with default compiler settings (i.e. no optimization) with C++ demangling enabled on Godbolt.
To bind the correct draw() call, we need to either tell the compiler the correct method to bind statically (via static_cast<>()) or via dynamic dispatch.
Simply adding the virtual keyword will give us the intended result but it would generate significantly more code as it has to invoke the correct method during runtime and
therefore does more jumping to get to the correct function (i.e. virtual dispatch):
mov rax, QWORD PTR [rbp-24]
mov rax, QWORD PTR [rax]
mov rdx, QWORD PTR [rax]
mov rax, QWORD PTR [rbp-24]
mov rdi, rax
call rdx
Here’s some interesting snippet of the code. Do not worry about understanding all of it, it’s just there to illustrate how much more code is generated to get this (note: scrollable):
Shape::Shape() [base object constructor]:
push rbp
mov rbp, rsp
mov QWORD PTR [rbp-8], rdi
mov edx, OFFSET FLAT:vtable for Shape+16
mov rax, QWORD PTR [rbp-8]
mov QWORD PTR [rax], rdx
nop
pop rbp
ret
.set Shape::Shape() [complete object constructor],Shape::Shape() [base object constructor]
Triangle::Triangle() [base object constructor]:
push rbp
mov rbp, rsp
sub rsp, 16
mov QWORD PTR [rbp-8], rdi
mov rax, QWORD PTR [rbp-8]
mov rdi, rax
call Shape::Shape() [base object constructor]
mov edx, OFFSET FLAT:vtable for Triangle+16
mov rax, QWORD PTR [rbp-8]
mov QWORD PTR [rax], rdx
nop
leave
ret
.set Triangle::Triangle() [complete object constructor],Triangle::Triangle() [base object constructor]
main:
push rbp
mov rbp, rsp
push rbx
sub rsp, 24
mov edi, 8
call operator new(unsigned long)
mov rbx, rax
mov QWORD PTR [rbx], 0
mov rdi, rbx
call Triangle::Triangle() [complete object constructor]
mov eax, 0
mov QWORD PTR [rbp-24], rbx
test al, al
je .L6
mov esi, 8
mov rdi, rbx
call operator delete(void*, unsigned long)
.L6:
mov rax, QWORD PTR [rbp-24]
mov rax, QWORD PTR [rax]
mov rdx, QWORD PTR [rax]
mov rax, QWORD PTR [rbp-24]
mov rdi, rax
call rdx
mov eax, 0
mov rbx, QWORD PTR [rbp-8]
leave
ret
vtable for Triangle:
.quad 0
.quad typeinfo for Triangle
.quad Triangle::draw()
vtable for Shape:
.quad 0
.quad typeinfo for Shape
.quad Shape::draw()
typeinfo for Triangle:
.quad vtable for __cxxabiv1::__si_class_type_info+16
.quad typeinfo name for Triangle
.quad typeinfo for Shape
typeinfo name for Triangle:
.string "8Triangle"
typeinfo for Shape:
.quad vtable for __cxxabiv1::__class_type_info+16
.quad typeinfo name for Shape
typeinfo name for Shape:
.string "5Shape"
Let’s go line by line of the virtual dispatch to understand what is going on:
mov rax, QWORD PTR [rbp-24] ; rax = address of `Triangle` object
mov rax, QWORD PTR [rax] ; rax = address of the vtable for `Triangle`
mov rdx, QWORD PTR [rax] ; rdx = address of `Triangle::draw()``
mov rax, QWORD PTR [rbp-24] ; rax = address of `Triangle` object
mov rdi, rax ; rdi = address of `Triangle` object acting as our first hidden `this` argument
call rdx ; call `Triangle::draw(this)`
mov rax, QWORD PTR [rbp-24]- load the value stored at
[rbp-24]intorax rbp-24is where our variableshapeis located pointing to aTriangleobject in the heapmain: push rbp mov rbp, rsp push rbx sub rsp, 24 ; <- allocates `shape` into the stack mov edi, 8 call operator new(unsigned long) ...[rbp-24]will give us the value located inrbp-24(i.e. value ofshapevariable), the address of theTriangleobject intoraxregister
- load the value stored at
mov rax, QWORD PTR [rax]- load the value stored at
[rax] [rax]is the value of the vtable ofTriangle, the first field in the class
- we refer this as the virtual pointer which points to the virtual table, more specifically to the first virtual function in the table
- load the value stored at
mov rdx, QWORD PTR [rax]- load value stored at
[rax]- this resembles the previous instruction except it stores inrdxregister [rax]will give us the first function pointer in the virtual table (i.e.vtbl_ptr[0])- first function pointer in virtual table is
Triangle::draw()
- load value stored at
mov rdx, QWORD PTR [rax]- similar to step 1 - store address of
Triangleobject intoraxregister
- similar to step 1 - store address of
mov rdi, rax- In AMD64,
rdiholds the first argument to pass onto the function - Recall:
thisis a hidden argument to a method
- In AMD64,
call rdx- invokes
Triangle::draw()obtained from step 3
- invokes
Virtual Pointers and Virtual Tables
Recall that in our object slicing example, the call to draw() generated the following assembly code:
mov rax, QWORD PTR [rbp-8]
mov rdi, rax
call Shape::draw()
However, once we declare draw() to be a virtual function, we observed that the compiler generated significantly more code to dynamically dispatch the correct draw()
implementation:
1 mov rax, QWORD PTR [rbp-24]
2 mov rax, QWORD PTR [rax]
3 mov rdx, QWORD PTR [rax]
4 mov rax, QWORD PTR [rbp-24]
5 mov rdi, rax
6 call rdx
Notice how the call to our function is indirect (i.e. calls a function stored in rdx register instead of a named label).
Line 2 suggests that the first 8B in memory allocated for our Triangle object is a pointer to our first virtual function in the virtual table (called a virtual pointer).
This behavior can be observed by looking at the construction of the Triangle constructor:
Triangle::Triangle() [base object constructor]:
; 1 push rbp
; 2 mov rbp, rsp
; 3 sub rsp, 16
; 4 mov QWORD PTR [rbp-8], rdi
; 5 mov rax, QWORD PTR [rbp-8]
; 6 mov rdi, rax
; 7 call Shape::Shape() [base object constructor]
8 mov edx, OFFSET FLAT:vtable for Triangle+16
9 mov rax, QWORD PTR [rbp-8]
10 mov QWORD PTR [rax], rdx
;11 nop
;12 leave
;13 ret
;14 .set Triangle::Triangle() [complete object constructor],Triangle::Triangle() [base object constructor]
- Line 8 shows that we store a pointer to the virtual table into
edxregister. - Line 9 shows we load
this, the address where our object begins intoraxregister - Line 10 states that we move the value in register
rdxinto whereraxregister is pointing into, which isthis, the start of our newly constructed object- recall how the virtual pointer is stored into
edxregister but we are now moving the contents ofrdxintothisrather than fromedxregister edxregister is the 32 bit version ofrdxwhereby the upper bits are zeroed- TODO: Figure out why only the vtable address fits in 32 bits
- AT&T syntax produces:
movl $vtable for Triangle+16, %edxinstead
- recall how the virtual pointer is stored into
Note: The location of virtual pointers is compiler-dependent according to stackoverflow
Let’s disect what the virtual pointer points to seeing that it does not point to the start of the virtual table as evident of the 16B offset.
vtable for Triangle:
.quad 0
.quad typeinfo for Triangle
.quad Triangle::draw()
| Offset | Size | Content |
|---|---|---|
| +0 | 8B | 0 |
| +8 | 8B | RTTI pointer |
| +16 | 8B | Triangle::draw() |
A 16B offset points to the first virtual function in the table, Triangle::draw(), the desired function to invoke. A virtual table is simply a lookup table
generated by the compiler to allow us invoke dynamically the desired function.
Suppose we add a new virtual method erase() to Triangle, we’ll see the following in our virtual table:
vtable for Triangle:
.quad 0
.quad typeinfo for Triangle
.quad Triangle::draw()
.quad Triangle::erase()
As pointers are 8B, an offset of 8 bytes from the virtual pointer will point us to Triangle::erase() as evident from the additional offset during the dynamic dispatch: add rax, 8
; mov rax, QWORD PTR [rbp-24]
; mov rax, QWORD PTR [rax]
add rax, 8
; mov rdx, QWORD PTR [rax]
; mov rax, QWORD PTR [rbp-24]
; mov rdi, rax
; call rdx
That will conclude this blog post as we now understand why virtual keyword is needed, what virtual pointers are, and how virtual functions are invoked.
Bonus - Issue With References
Don’t make Shape, our base class, as a C++ reference if you want to dynamically dispatch different types of shapes like a Circle with the same Shape object.
Use pointers to ensure shape rebinds to the correct derived object.
For instance, suppose we introduce a Circle object and use references instead of pointers
#include <iostream>
class Shape {
public:
virtual void draw() { std::cout << "Shape\n"; }
};
class Triangle : public Shape {
public:
void draw() { std::cout << "Triangle\n"; }
};
class Circle : public Shape {
public:
void draw() { std::cout << "Circle\n"; }
};
int main() {
Triangle tri;
Circle circ;
Shape &shape = tri;
shape.draw(); //displays Triangle
shape = circ;
shape.draw(); //displays Triangle
}
Recall that C++ references must always be initialized and therefore a type is binded to references during initialization. i.e. this is a compiler error:
Shape &shape;
shape = tri;
As C++ references cannot change type after initialization, this is what we call object slicing where the extra components from Circle are sliced away and thus retaining
only the Shape subobject.
When we reassign shape = circ, the reference is not rebinded but instead we see the following invocation:
leaq -24(%rbp), %rdx
movq -8(%rbp), %rax
movq %rdx, %rsi
movq %rax, %rdi
call Shape::operator=(Shape const&)
Specifically, it calls the copy assignment Shape::operator=(Shape const&) whereby only the Shape components of the circle object is copied and hence is object sliced.
Here’s a more clearer example of what happens during object slicing:
#include <iostream>
class Shape {
public:
int x = 0;
virtual std::string draw() { return "Shape "; }
};
class Triangle : public Shape {
public:
int x = 1;
std::string draw() { return "Triangle "; }
};
class Circle : public Shape {
public:
int x = 2;
std::string draw() { return "Circle "; }
};
int main() {
Triangle tri;
Circle circ;
Shape &shape = tri;
shape = circ;
std::cout << shape.draw() << shape.x;
}
Output: Triangle 0
Recall that we set shape = tri, this performs an object slice to tri to conform to Shape layout. This explains why x is zero instead of 1.