Instead, virtual function calls should be compared with similar constructions solving the same problem: namely calling a function containing a switch on the actual type of the object. Since the problem is actually related to executing different code depending on the dynamic "type" of an object, we hereafter call this dynamic dispatch regardless of whether it is in C or C++.
Setting the Scene
To illustrate the traditional solutions in C and C++, we assume that we wish to implement a simple virtual machine and demonstrate how it is done in a typical C manner and in a typical C++ manner. In both cases we use C++ syntax to write the code, so there are some minor differences compared to how it would look in standard C.For simplicity, we assume that all instruction have one constant and manipulate the accumulator. The instruction we will implement are, in Z80-like notation:
| Instruction | Description |
|---|---|
LD A, c |
Load accumulator with constant value c |
ADD A, c |
Add constant c to value in accumulator |
SUB A, c |
Substract value c from value in accumulator |
struct state {
int acc;
};
Call + Switch
For the "C solution", we introduce a structure to represent an instruction and an enumeration with constants for the instructions:
enum enum_kind { LOAD_INSTR, ADD_INSTR, SUB_INSTR };
struct instr {
enum_kind kind;
int val;
};
The C code to implement dynamic dispatch then look like this:
void execute(instr* i, state* s) {
switch (i->kind) {
case LOAD_INSTR:
s->acc = i->val;
break;
case ADD_INSTR:
s->acc += i->val;
break;
case SUB_INSTR:
s->acc -= i->val;
break;
}
}
We call this approach the call+switch method.
- Advantages:
-
- Less code to write (than the C++ solution)
- Can be inlined if the
execute()function is small.
- Disadvantages:
-
- Not in accordance with the Open-Closed Principle: the code cannot be extended with new instructions without changing existing code.
- Slower than using virtual function calls [sic], unless the function is inlined
The function pointer structure
An alternative, and quite common, way to imlement virtual dispatch is to use a structure with function pointers, where the function pointer is set to the apropriate function. To handle this, we create the following structure:
struct instr {
void (*execute)(instr*, state*);
int val;
};
void load(instr* i, state* s) { s->acc = i->val; }
void add(instr* i, state* s) { s->acc += i->val; }
void sub(instr* i, state* s) { s->acc -= i->val; }
To perform the virtual dispatch, the following code is then used:
program[pc]->execute(program[pc], &state);We call this the function pointer method.
- Advantages:
-
- In accordance with the Open-Closed Principle: the code is open for extension with new instruction but closed to changes since it doesn't require changing existing code.
- Disadvantages:
- More code to write
- Larger structures: one function pointer is required for each method
- Cannot be inlined
Virtual functions
The corresponding construction in C++ using virtual functions look something like this:
class Instruction {
protected:
int m_val;
public:
Instruction(int v = 0) : m_val(v) { }
virtual void execute(state&) const = 0;
};
class Add : public Instruction {
public:
Add(int v) : Instruction(v) { ; }
virtual void execute(state& s) const { s.acc += m_val; }
};
class Sub : public Instruction {
public:
Sub(int v) : Instruction(v) { ; }
virtual void execute(state& s) const { s.acc -= m_val; }
};
class Load : public Instruction {
public:
Load(int v) : Instruction(v) { ; }
virtual void execute(state& s) const { s.acc = m_val; }
};
We call this approach the virtual call method.
- Advantages:
-
- In accordance with the Open-Closed Principle: the code can be extended with new instruction without changing existing code.
- Disadvantage:
-
- More code to write
- Cannot be inlined
Measurements
All measurements done are on an Intel(R) Pentium(R) M processor 1.60GHz and using gcc 3.0 with -O3.
To measure the execution time of the two pieces of code, we create a
random program of length length and execute it 20000 times. To avoid any randomization problems, we use the same sequence of instructions for both the call+switch, function pointer, and virtual call versions when we measure. In addition, the call+switch function is placed in a separate translation unit to prevent automatic inlining: this would be the normal case, since the function would be to large to inline.
| length | call+switch (CS) |
funcptr (FP) |
virtual (VF) |
CS/FP | FP/VF |
|---|---|---|---|---|---|
| 2000 | 1.08 | 0.82 | 1.49 | 1.31 | 0.55 |
| 4000 | 2.09 | 1.64 | 1.64 | 1.27 | 1.00 |
| 6000 | 3.12 | 2.50 | 2.46 | 1.25 | 1.01 |
| 8000 | 4.16 | 3.30 | 3.28 | 1.26 | 1.01 |
| 10000 | 5.22 | 4.13 | 4.09 | 1.26 | 1.01 |
| 12000 | 6.26 | 4.97 | 4.97 | 1.26 | 1.00 |
| 14000 | 7.31 | 5.84 | 5.79 | 1.25 | 1.01 |
| 16000 | 8.45 | 6.84 | 6.75 | 1.23 | 1.01 |
| 18000 | 9.52 | 7.59 | 7.55 | 1.26 | 1.00 |
| 20000 | 10.53 | 8.49 | 8.47 | 1.24 | 1.00 |
