Why virtual function call is faster than dynamic_cast?

Question

I wrote a simple example, which estimates average time of calling virtual function, using base class interface and dynamic_cast and call of non-virtual function. Here is it:

#include <iostream>
#include <numeric>
#include <list>
#include <time.h>

#define CALL_COUNTER (3000)

__forceinline int someFunction()
{
  return 5;
}

struct Base
{
  virtual int virtualCall() = 0;
  virtual ~Base(){};
};

struct Derived : public Base
{
  Derived(){};
  virtual ~Derived(){};
  virtual int virtualCall(){ return someFunction(); };
  int notVirtualCall(){ return someFunction(); };
};


struct Derived2 : public Base
{
  Derived2(){};
  virtual ~Derived2(){};
  virtual int virtualCall(){ return someFunction(); };
  int notVirtualCall(){ return someFunction(); };
};

typedef std::list<double> Timings;

Base* createObject(int i)
{
  if(i % 2 > 0)
    return new Derived(); 
  else 
    return new Derived2(); 
}

void callDynamiccast(Timings& stat)
{
  for(unsigned i = 0; i < CALL_COUNTER; ++i)
  {
    Base* ptr = createObject(i);

    clock_t startTime = clock();

    for(int j = 0; j < CALL_COUNTER; ++j)
    {
      Derived* x = (dynamic_cast<Derived*>(ptr));
      if(x) x->notVirtualCall();
    }

    clock_t endTime = clock();
    double callTime = (double)(endTime - startTime) / CLOCKS_PER_SEC;
    stat.push_back(callTime);

    delete ptr;
  }
}

void callVirtual(Timings& stat)
{
  for(unsigned i = 0; i < CALL_COUNTER; ++i)
  {
    Base* ptr = createObject(i);

    clock_t startTime = clock();

    for(int j = 0; j < CALL_COUNTER; ++j)
      ptr->virtualCall();


    clock_t endTime = clock();
    double callTime = (double)(endTime - startTime) / CLOCKS_PER_SEC;
    stat.push_back(callTime);

     delete ptr;
  }
}

int main()
{
  double averageTime = 0;
  Timings timings;


  timings.clear();
  callDynamiccast(timings);
  averageTime = (double) std::accumulate<Timings::iterator, double>(timings.begin(), timings.end(), 0);
  averageTime /= timings.size();
  std::cout << "time for callDynamiccast: " << averageTime << std::endl;

  timings.clear();
  callVirtual(timings);
  averageTime = (double) std::accumulate<Timings::iterator, double>(timings.begin(), timings.end(), 0);
  averageTime /= timings.size();
  std::cout << "time for callVirtual: " << averageTime << std::endl;

  return 0;
}

It looks like callDynamiccast takes almost two times more.

time for callDynamiccast: 0.000240333

time for callVirtual: 0.0001401

Any ideas why does it?

EDITED: object creation is made in separete function now, so the compler does not know it real type. Almost the same result.

EDITED2: create two different types of a derived objects.

Answer 1

The virtual function call is similar to a function pointer, or if the compiler knows the type, static dispatch. This is constant time.

dynamic_cast is quite different -- it uses an implementation defined means to determine a type. It is not constant time, may traverse the class hierarchy (also consider multiple inheritance) and perform several lookups. An implementation may use string comparisons. Therefore, the complexity is higher in two dimensions. Real time systems often avoid/discourage dynamic_cast for these reasons.

More details are available in this document.

Answer 2

It should be noted that the entire purpose of virtual functions is to not have to cast down the inheritance graph. Virtual functions exist so that you can use a derived class instance as though it were a base class. So that more specialized implementations of functions can be called from code that originally called base class versions.

If virtual functions were slower than a safe cast to the derived-class + function call, then C++ compilers would simply implement virtual function calls that way.

So there's no reason to expect dynamic_cast+call to be faster.