The arrow of time

Ivan Voras' blog

How slow are virtual methods in C++?

NOTE: this is bogus and I'm retracing this blog entry. The compiler still managed to trick me - what I'm describing in this post resulted from using -O3 optimization in gcc. With -O2 the times are close but it looks like the vtable approach could be faster.

The original post follows:

In one project I have a choice of modifying a behaviour of a class either by abstracting a base class with virtual methods and creating two descendant classes implementing those methods differently or by adding a flag and an "if" statement in the class and implementing the difference in behaviour based on this flag. Which one would you choose? Which one do you think would be faster?

As it turns out, the virtual method approach appears to be 2x slower than the if-based approach in this microbenchmark I made. I have no other conclusion but that the vtable lookup is indeed very slow even on modern CPU-s, and probably will never be "fast enough" for microbenchmarks.

/* vtable approach */
class FibBase {
public:
virtual int64_t fib(int64_t n) = 0;
};

class Fib : public FibBase {
public:
virtual int64_t fib(int64_t n);
};

int64_t Fib::fib(int64_t n) {
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}


/* conditional approach */
class FibIf {
private:
int f;
public:
FibIf(int flag);
int64_t fib(int64_t n);
};

FibIf::FibIf(int flag) {
f = flag;
}

int64_t FibIf::fib(int64_t n) {
if (f == 42) {
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
} else
return -1;
}

I've taken precautions in main() not to have the compiler short-circut or optimize away the if statement in the FibIf::fib() method.

Time taken for calculating the first 40 Fibonacci numbers on a Core2 CPU are: 3.2 seconds for the virtual method variation and 1.5 seconds for the conditional variation. Compiled with gcc 4.2, FreeBSD 8 (amd64 arch).