So, you have a pointer or reference to an object and you want to do something depending on what type of object it is. What are your options and which should you use when? This kind of problem is called dynamic dispatch, and there are a lot of different ways to achieve it in C++.

To be more precise, dynamic dispatch is when you have one or more objects and you want to do something based on all their types. When you have just one object, that is single dispatch. For example, the classic shape example: if you have a pointer to a shape and it could be a circle, square or triangle and want to draw the object on the screen. For two objects, this is double dispatch. For example, if you have two shapes and want to see if they overlap. Three objects would be triple dispatch, though it's rarely discussed. Two or more objects collectively are called multiple dispatch. Here I only talk about single dispatch.

Some preliminaries: for the purposes of this article we'll assume that your types form a hierarchy with a single base class and that class has a virtual destructor. In other words, it looks something like:

struct Base {
  virtual ~Base() = 0;
};
 
struct D1 : Base {};
struct D2 : Base {};
struct D3 : Base {};

Obviously, for real code, each of the classes would have more information inside. The virtual destructor is important since it allows delete to be called on a Base * pointer and allows RTTI to work with our objects.

The first, obvious choice is to use a virtual function.

struct Base {
  virtual void foo(void) = 0;
  virtual ~Base() = 0;
};
 
struct D1 : Base {
  void foo(void) { /* stuff for first derived class */ }
};
struct D2 : Base {
  void foo(void) { /* stuff for second derived class */ }
};
struct D3 : Base {
  void foo(void) { /* stuff for third derived class */ }
};

Pros: virtual functions have the advantages of being quite speedy, as well as being familiar to any C++ programmer.

Cons: adding a new virtual function requires modifying the class definitions for the types in the hierarchy, which means, at the very least, recompiling everything that depends on the definition of the base class.

Another choice is applying the visitor pattern.

struct Visitor;
 
struct Base {
  virtual void accept(Visitor & visitor) = 0;
  virtual ~Base() = 0;
};
 
struct D1;
struct D2;
struct D3;
 
struct Visitor {
  virtual void visit(D1 & d1) = 0;
  virtual void visit(D2 & d2) = 0;
  virtual void visit(D3 & d3) = 0;
};
 
struct D1 : Base {
  void accept(Visitor & visitor) { visitor.visit(*this); }
};
struct D2 : Base {
  void accept(Visitor & visitor) { visitor.visit(*this); }
};
struct D3 : Base {
  void accept(Visitor & visitor) { visitor.visit(*this); }
};
 
struct FooVisitor : Visitor {
  void visit(D1 & d1) {
    /* stuff for first derived class */ 
  }
  void visit(D3 & d2) {
    /* stuff for second derived class */ 
  }
  void visit(D3 & d3) {
    /* stuff for third derived class */ 
  }
};

For those of you not familiar with the visitor pattern in C++, this works like so: When you want to create a new "virtual function" you derived a new type from the Visitor interface. In order to call it on a give Base *, you pass it to the accept() function. The accept() function implemented in the derived classes call the appropriate version of the visit() function on the visitor.

Pros: Still relatively fast. Adding new "virtual functions" doesn't require recompiling code that relies on the class definitions.

Cons: The class definitions are highly coupled to each other. Each of the derived classes and the base visitor class all need to know about all the derived classes in order to compile. If a new derived class is added then everything needs to be recompiled.

Addressing the coupling in Visitor is the acyclic visitor pattern.

struct Visitor {
  virtual ~Visitor() {}
};
 
struct Base {
  virtual void accept(Visitor & visitor) = 0;
  virtual ~Base() = 0;
};
 
struct D1Visitor {
  virtual void visit(D1 & obj) = 0;
  virtual ~D1Visitor() {}
};
struct D1 : Base {
  void accept(Visitor & visitor) { 
    D1Visitor * v = dynamic_cast<D1Visitor *>(&visitor);
    if (v) v->visit(*this);
  }
};
 
struct D2Visitor {
  virtual void visit(D2 & obj) = 0;
  virtual ~D2Visitor() {}
};
struct D2 : Base {
  void accept(Visitor & visitor) { 
    D2Visitor * v = dynamic_cast<D2Visitor *>(&visitor);
    if (v) v->visit(*this);
  }
};
 
struct D3Visitor {
  virtual void visit(D3 & obj) = 0;
  virtual ~D3Visitor() {}
};
struct D3 : Base {
  void accept(Visitor & visitor) { 
    D3Visitor * v = dynamic_cast<D3Visitor *>(&visitor);
    if (v) v->visit(*this);
  }
};
 
struct FooVisitor : Visitor, D1Visitor, D2Visitor, D3Visitor {
  void visit(D1 & d1) {
    /* stuff for first derived class */ 
  }
  void visit(D3 & d2) {
    /* stuff for second derived class */ 
  }
  void visit(D3 & d3) {
    /* stuff for third derived class */ 
  }
};

Acyclic visitor breaks the dependency cycle between derived classes and the base visitor class by using dynamic_cast to see if a visitor processes the given class. Adding a new derived class doesn't require any change in existing visitor classes. This can reduce compile times, but also makes it easier to forget to update a visitor class for new derived classes.

Pros: allows the addition of new "virtual functions" without modifying existing classes and lack of dependency cycles mean decent compile times.

Cons: slow, requires RTTI to be enabled.

Other approaches using RTTI include using if statements with conditions depending on either typeid or dynamic_cast.

void foo(Base & base) {
  if (D1 * obj = dynamic_cast<D1 *>(&base)) {
    /* stuff for first derived class */ 
  } else if (D2 * obj = dynamic_cast<D2 *>(&base)) {
    /* stuff for second derived class */ 
  } else if (D3 * obj = dynamic_cast<D3 *>(&base)) {
    /* stuff for third derived class */ 
  } else {
    /* unknown class */ 
  }
}

As a variant, you can leave off the check for the last derived class and perform a static_cast in the else block.

void foo(Base & base) {
  if (D1 * obj = dynamic_cast<D1 *>(&base)) {
    /* stuff for first derived class */ 
  } else if (D2 * obj = dynamic_cast<D2 *>(&base)) {
    /* stuff for second derived class */ 
  } else {
    D3 * obj = static_cast<D3 *>(&base);
    /* stuff for third derived class */ 
  }
}

Pros: allows the addition of new "virtual functions" without modifying the existing type hierarchy.

Cons: slow. Need to be careful about the order of casting derived classes to make sure that child classes don't get handled by parent class behaviors. Easy to miss modifying functions for new derived classes.

void foo(Base & base) {
  if (typeid(base) == typeid(D1)) {
    D1 & obj = static_cast<D1 &>(base);
    /* stuff for first derived class */ 
  } else if (typeid(base) == typeid(D2)) {
    D2 & obj = static_cast<D2 &>(base);
    /* stuff for second derived class */ 
  } else if (typeid(base) == typeid(D3)) {
    D3 & obj = static_cast<D3 &>(base);
    /* stuff for third derived class */ 
  } else {
    /* unknown class */ 
  }
}

Again, if you're sure that you've listed all the classes, you can leave off the check for the last derived class.

void foo(Base & base) {
  if (typeid(base) == typeid(D1)) {
    D1 & obj = static_cast<D1 &>(base);
    /* stuff for first derived class */ 
  } else if (typeid(base) == typeid(D2)) {
    D2 & obj = static_cast<D2 &>(base);
    /* stuff for second derived class */ 
  } else {
    D3 & obj = static_cast<D3 &>(base);
    /* stuff for third derived class */ 
  }
}

Pros: allows the addition of new "virtual functions" without modifying the existing type hierarchy.

Cons: slow. Easy to miss modifying functions for new derived classes. May not work properly in the presence of multiple or virtual inheritance.

A broad group of methods involve getting a type code somehow from the object and then switching on that type code.

enum TypeID {
  d1, d2, d3
};
void foo(Base & base) {
  switch ( /* get a type code */ ) {
    case d1: {
        D1 & d1 = static_cast<D1 &>(base);         
        /* stuff for first derived class */ 
      }
      break;
    case d2: {
        D2 & d2 = static_cast<D2 &>(base);         
        /* stuff for second derived class */ 
      }
      break;
    case d3: {
        D3 & d3 = static_cast<D3 &>(base);         
        /* stuff for third derived class */ 
      }
      break;
    default:
      /* unknown class */ 
      break;
  }
}

Again, you can have a variant when you discard the handling for unknown object types.

enum TypeID {
  d1, d2, d3
};
void foo(Base & base) {
  switch ( /* get a type code */ ) {
    case d1: {
        D1 & d1 = static_cast<D1 &>(base);         
        /* stuff for first derived class */ 
      }
      break;
    case d2: {
        D2 & d2 = static_cast<D2 &>(base);         
        /* stuff for second derived class */ 
      }
      break;
    case d3: {
        D3 & d3 = static_cast<D3 &>(base);         
        /* stuff for third derived class */ 
      }
      break;
  }
}

The question becomes how you determine the type code for an object. All of the following have the following:

Pro: Able to add new "virtual functions" without modifying existing classes.

Con: Easy to miss modifying functions for new derived classes. May not work properly in the presence of multiple or virtual inheritance.

One option is to give the Base class a member variable for the type code.

enum TypeID {
  d1, d2, d3
};
 
struct Base {
  virtual ~Base() = 0;
 
  TypeID type_code;
};
 
struct D1 : Base {
  D1() : type_code(d1) {}
};
struct D2 : Base {
  D2() : type_code(d2) {}
};
struct D3 : Base {
  D3() : type_code(d3) {}
};

Pros: Reasonably fast

Cons: Requires extra storage. Can create schizophrenic behavior if the type_code gets modified.

Another option is to give Base a virtual function that returns the type code.

enum TypeID {
  d1, d2, d3
};
 
struct Base {
  virtual ~Base() = 0;
 
  TypeID type_code(void) = 0;
};
 
struct D1 : Base {
  TypeID type_code(void) { return d1; }
};
struct D2 : Base {
  TypeID type_code(void) { return d2; }
};
struct D3 : Base {
  TypeID type_code(void) { return d3; }
};

Pros: Still reasonably fast

Cons: No additional cons

You can also associate the type code with type_info objects for the derived types.

struct TypeInfoProxy {
  TypeInfoProxy(const std::type_info * t) : ti(t) {}
  const std::type_info * ti;
};
 
inline bool operator<(const TypeInfoProxy & lhs, const TypeInfoProxy & rhs) {
  return lhs.ti->before(*rhs.ti) != 0;
}
 
struct KeyValuePair {
  const std::type_info * first;
  TypeID second;
  
  operator std::pair<const TypeInfoProxy, TypeID>() { return std::make_pair(first, second); }
} initializers[] = {
  { &typeid(D1), d1 },
  { &typeid(D2), d2 },
  { &typeid(D3), d3 }
};
 
std::map<TypeInfoProxy, TypeID> id_mapper(&initializers[0], &initializers[3]);

Pros: Doesn't require modifying the type hierarchy to add the type codes

Cons: Slow

All the previous options all rely on mechanisms that are well-defined with respect to the C++ standard. You can count on each of them working on any platform with a working C++ compiler. However, sometimes you're willing to sacrifice portability for some other goal (usually speed). Here are a couple of options for MSVC (specifically tested with 2008).

It's an open secret that most compilers implement virtual functions by including a pointer to a structure usually referred to as the vtable: the virtual function table. If you have a pointer to an object with virtual functions but no member variables, then you can pretty much assume that you actually have a pointer to a pointer to the vtable. This enables writing code like:

struct Base {
  virtual ~Base() = 0;
 
  inline const void * get_vtable_addr(void) const {
    return *(void **)this;
  }
};
 
struct D1 : Base {
  const void * const vtable_address;
};
struct D2 : Base {
  const void * const vtable_address;
};
struct D3 : Base {
  const void * const vtable_address;
};
 
void foo(Base & base) {
  if (base.get_vtable_addr() == D1::vtable_address) {
    D1 & d1 = static_cast<D1 &>(base);         
    /* stuff for first derived class */ 
  } else if (base.get_vtable_addr() == D2::vtable_address) {
    D2 & d2 = static_cast<D2 &>(base);
    /* stuff for second derived class */ 
  } else if (base.get_vtable_addr() == D3::vtable_address) {
    D3 & d3 = static_cast<D3 &>(base);         
    /* stuff for third derived class */ 
  } else {
    /* unknown type */ 
  }
}

The question becomes how to load the vtable addresses in the first place. One technique is to simply create an object of each of the types and inspect those objects for the vtable address. If your objects are large or otherwise expensive to construct or have other side effects that may not be the best approach. However, we're already well into undefined behavior land, so we might as well use some compiler dependent black magic.

The __identifier keyword was added to MSVC to ease integration with non-C++ languages that use C++ keywords as identifiers. Using it with identifiers that aren't C++ keywords raises a C4483 compiler error. However, this is an optional compiler error. With a pragma or compiler option you can disable it and use the __identifier keyword to refer to name mangled identifiers. In this case we want names of the form "??_7SomeClass@@6B@", which is the name of the vtable for a class SomeClass.

#pragma warning(disable:4483)
const void * const D1::vtable_address = &__identifier("??_7D1@@6B@");
const void * const D2::vtable_address = &__identifier("??_7D2@@6B@");
const void * const D3::vtable_address = &__identifier("??_7D3@@6B@");

Pros: quite fast for a cascading if statement mechanism. Can add new "virtual functions" without modifying class definitions.

Cons: Depends on undefined and undocumented behavior. This particular implementation is also compiler dependent. High likelihood of blowing up messily if multiple modules are present (i.e. classes are defined in DLLs). More complicated to implement in the presence of multiple or virtual inheritance.

Another approach is to revisit the idea of using switch statements with the vtable in mind. Addresses aren't resolved until load time, so you can't use the vtable address directly in a switch, but you can use the vtable address to produce a type code. One way would be to associate the address with a map or unordered_map, but since we're still swimming in undefined behavior land we can take another approach: embedded the type code directly in the virtual function table. In order for C++ objects to directly usable as COM objects, MSVC uses a strict straightforward ordering of functions in the vtable: the order of declaration in the class decides the order in the vtable. So if we make the very first function a function that we never, ever call, we can overwrite that address in the vtable to get us virtual static data.

struct Base {
  virtual void for_the_love_of_god_never_call_this_function(void) {}
  virtual ~Base() = 0;
 
  inline TypeID get_type_id(void) const {
    return **(TypeID **)this;
  }
};
 
void assign_typeids(void) {
  *(TypeID *)(__identifier("??_7D1@@6B@")) = d1;
  *(TypeID *)(__identifier("??_7D2@@6B@")) = d2;
  *(TypeID *)(__identifier("??_7D3@@6B@")) = d3;
}

You can also replace an explicit call to assign_typeids() to some autoexecution trick of your choice, but I think we're enough trouble as it is.

Under normal circumstances this will compile, but cause an access violation when it executes because the virtual function tables are loaded into the .rdata const data segment. We can force this to work by merging the .rdata data segment with the .data segment with the linker option /merge:.rdata=.data .

Pros: Relatively fast. Can add new "virtual functions" without modifying class definitions.

Cons: Depends on undefined and undocumented behavior. Highly compiler dependent. High likelihood of blowing up messily if multiple modules are present (i.e. classes are defined in DLLs). More complicated to implement in the presence of multiple or virtual inheritance.

So I've been using terms like "fast" and "slow" for these techniques. Basically techniques that rely directly on the C++ RTTI mechanisms typeid and dynamic_cast fall in the "slow" category and everything else falls in the "fast" category. But how fast is fast and how slow is slow? As usual, performance is very context dependent, but for those who want something more concrete I've assembled a test program that includes each of these techniques. Again, this is a highly artificial situation and really doesn't mean too much in isolation. Still, it can still be more fun to comment on the things that don't mean too much versus the things that do, so let's pretend that it does mean something for a little while.

The first scenario we'll look at is the situation where every derived class does something different.

Comparing the first two sets of data, we see one important things: the act of adding a type code to the base type slows down everything. From 17% worse performance for virtual functions, to 3% to the acyclic visitor. So for a more fair comparison I'll take the type code data from the second table and merge that into the first table.

Some thoughts:

• Normal virtual functions seem to perform quite well, coming in first in the combined table for every number of derived classes, even beating type code switches with the extra data penalty for more than three derived classes.
• Using if statements with RTTI seem like a clear loser here. They start bad and get worse quickly. If you can't modify the classes in question and don't want to rely on non-standard behavior, it looks like the best bet is a map of type_infos. That starts bad and gets worse slowly.
• The penalty for sticking extra data in the class does decrease as the number of classes goes up, but only seems to go away for the very worst performers.
• For the best performers, adding the extra checks for valid classes (the defaults and the elses) don't seem to add much overhead. For the worst performers, that extra else, while statistically significant, doesn't seem like a practical difference.

For the second test we'll try to create a scenario where virtual functions don't perform as well, and one area where a virtual function is pure overhead is when the function does nothing. So let's look at the situation where half the derived classes do a no-op.

For this situation, cases involving cascading if statements get simplified by simply omitting checks for derived classes that don't need work performed. For example, the vtable address comparison would look like this for three classes:

void foo(Base & base) {
  if (base.get_vtable_addr() == D1::vtable_address) {
    D1 & d1 = static_cast<D1 &>(base);         
    /* stuff for first derived class */ 
  } else if (base.get_vtable_addr() == D3::vtable_address) {
    D3 & d3 = static_cast<D3 &>(base);         
    /* stuff for third derived class */ 
  }
}

Doing so means that there's no else/no else pair for the cascading ifs in the following tables.

Now virtual functions usually take a back seat to the two non-standard methods, but the three techniques are very close in performance, usually within sampling error. The extra data penalty is still here, but seems somewhat less severe than in the previous scenario.

For the final scenario, we look at the situation where we only do something if the derived class is one particular type and nothing otherwise.

• Interestingly, here some techniques perform better as the number of classes increase as a proportionally less work is done. However, some techniques stay pretty steady and the type_info map actually gets worse.
• The extra data penalty remains, and actually seems more severe than scenario one.
• This is finally a situation where plain old virtual functions lose out performance-wise to another technique that doesn't require relying on undefined behavior.

The performance test program uses heavy use of boost::preprocessor to produce output for differing numbers of derived classes. The BODY() macro controls exactly what happens in each of the function calls. The current definition was chosen so that the code for different derived types wouldn't be merged and that it would easy to determine if all the different dynamic dispatch methods were actually executing the same algorithms. A fun exercise is to set the contents to empty to see how well the compiler does dead code elimination for each of the different dynamic dispatch techniques.

Again, this is MSVC specific, and /merge:.rdata=.data can be used to allow the modification of vtable data.

//Copyright (c) 2009 Howard Jeng 
// 
//Permission is hereby granted, free of charge, to any person obtaining a copy 
//of this software and associated documentation files (the "Software"), to deal 
//in the Software without restriction, including without limitation the rights 
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
//copies of the Software, and to permit persons to whom the Software is 
//furnished to do so, subject to the following condition: 
// 
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
//THE SOFTWARE. 
 
#define _SECURE_SCL 0
 
#define NOMINMAX
#include <windows.h>
 
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <typeinfo>
#include <vector>
 
#include <cmath>
 
#include <boost/preprocessor/array/elem.hpp>
#include <boost/preprocessor/arithmetic/mod.hpp>
#include <boost/preprocessor/arithmetic/sub.hpp>
#include <boost/preprocessor/comparison/equal.hpp>
#include <boost/preprocessor/control/if.hpp>
#include <boost/preprocessor/facilities/empty.hpp>
#include <boost/preprocessor/logical/or.hpp>
#include <boost/preprocessor/repetition.hpp>
 
#ifndef NUM_DERIVED_CLASSES
#define NUM_DERIVED_CLASSES 3
#endif
 
#ifndef USE_TYPECODE 
#define USE_TYPECODE 0
#endif
 
#ifndef TEST_RUNS
#define TEST_RUNS 15
#endif
 
#ifndef TEST_REPS
#define TEST_REPS 200
#endif
 
#ifndef TEST_SIZE
#define TEST_SIZE 100000
#endif
 
#ifndef PROCESS_EMPTY_IF
#define PROCESS_EMPTY_IF 0
#endif
 
#ifdef SINGLE
  #define C(num) BOOST_PP_EQUAL(num, 0)
  #define USE_ELSE PROCESS_EMPTY_IF
#elif defined(HALF)
  #define C(num) BOOST_PP_EQUAL(BOOST_PP_MOD(num, 2), 0)
  #define USE_ELSE PROCESS_EMPTY_IF
#elif defined(EMPTY)
  #define C(num) 0
  #define USE_ELSE PROCESS_EMPTY_IF
#else
  #define C(num) 1
  #define USE_ELSE 1
#endif
 
#define EMPTY_0()
#define EMPTY_1(x)
#define EMPTY_2(x, y)
 
#define BODY_CONTENTS(num, ref) \
  do { \
    D ## num::static_data ^= (D ## num::static_data << 5) ^ (D ## num::static_data >> 3); \
    D ## num::static_data ^= (0xf001 * (ref).instance_data1); \
    D ## num::static_data ^= (0xdeadbeef << num) | (0xdeadbeef >> ((32 - num) % 32)); \
  } while (0)
#define BODY(num, ref) BOOST_PP_IF(C(num), BODY_CONTENTS, EMPTY_2)(num, ref)
#define COND(num) BOOST_PP_OR(C(num), PROCESS_EMPTY_IF)
 
enum TypeID {
  #define LINE(z, n, unused) d ## n,
  BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
  #undef LINE
  extra
};
 
struct BaseV;
 
struct AcyclicV {
  virtual ~AcyclicV() = 0;
};
 
AcyclicV::~AcyclicV() {}
 
struct Base {
  virtual void for_the_love_of_god_never_call_this_function(void) {}
  virtual void foo(void) const = 0;
  virtual TypeID type_id(void) const = 0;
  virtual void accept(BaseV & base_v) const = 0;
  virtual void accept(AcyclicV & acyclic_v) const = 0;
  virtual ~Base() {}
  
  inline const void * get_vtable_addr(void) const {
    return *(void **)this;
  }
  
  inline TypeID get_type_id(void) const {
    return **(TypeID **)this;
  }
  
  #if USE_TYPECODE
    inline void set_type_code(TypeID id) { type_code = id; }
    TypeID type_code;
  #else
    inline void set_type_code(TypeID id) {}
  #endif
};
 
#define LINE(z, n, unused) struct D ## n;
BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
#undef LINE
 
struct BaseV {
  virtual ~BaseV() {}
  #define LINE(z, n, unused) virtual void do_D ## n(const D ## n & obj) = 0;
  BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
  #undef LINE
};
 
#define DERIVED_CLASS(z, n, unused) \
  struct D ## n ## Visitor {                                                 \
    virtual void visit(const D ## n & obj) = 0;                              \
    virtual ~D ## n ## Visitor() {}                                          \
  };                                                                         \
  struct D ## n : Base {                                                     \
    virtual void foo(void) const { BODY(n, *this); }                         \
    virtual TypeID type_id(void) const { return d ## n; }                    \
    virtual void accept(BaseV & base_v) const { base_v.do_D ## n(*this); }   \
    virtual void accept(AcyclicV & acyclic_v) const {                        \
      D ## n ## Visitor * v = dynamic_cast<D ## n ## Visitor *>(&acyclic_v); \
      if (v) v->visit(*this);                                                \
    }                                                                        \
    static const void * const vtable_addr;                                   \
                                                                             \
    D ## n() : instance_data1(rand()) {                                      \
      set_type_code(d ## n);                                                 \
    }                                                                        \
    static int static_data;                                                  \
    int instance_data1;                                                      \
    int instance_data2;                                                      \
    int instance_data3;                                                      \
  };
BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, DERIVED_CLASS, ~)
#undef DERIVED_CLASS
 
#pragma warning(push)
#pragma warning(disable:4483)
#define ARRAY (15, (__identifier("??_7D0@@6B@") \
                   ,__identifier("??_7D1@@6B@") \
                   ,__identifier("??_7D2@@6B@") \
                   ,__identifier("??_7D3@@6B@") \
                   ,__identifier("??_7D4@@6B@") \
                   ,__identifier("??_7D5@@6B@") \
                   ,__identifier("??_7D6@@6B@") \
                   ,__identifier("??_7D7@@6B@") \
                   ,__identifier("??_7D8@@6B@") \
                   ,__identifier("??_7D9@@6B@") \
                   ,__identifier("??_7D10@@6B@") \
                   ,__identifier("??_7D11@@6B@") \
                   ,__identifier("??_7D12@@6B@") \
                   ,__identifier("??_7D13@@6B@") \
                   ,__identifier("??_7D14@@6B@") \
                    ))
#define LINE(z, n, unused) const void * const D ## n::vtable_addr = &BOOST_PP_ARRAY_ELEM(n, ARRAY);
BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
#undef LINE
 
void set_typeids(void) {
  #define LINE(z, n, unused) *(TypeID *)&BOOST_PP_ARRAY_ELEM(n, ARRAY) = d ## n;
  BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
  #undef LINE
}
#pragma warning(pop)
 
#define LINE(z, n, unused) int D ## n::static_data = 0;
BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
#undef LINE
 
#define L1(n, compare) } else if (compare(n)) { BODY(n, static_cast<const D ## n &>(base));
#define LINE(z, n, compare) BOOST_PP_IF(COND(n), L1, EMPTY_2)(n, compare)
#define ELSE_CLAUSE() } else { std::cout << "Unknown\n";
#define CONST_REF(n) const D ## n &
#define B(n) BODY(n, static_cast<CONST_REF(n)>(base));
 
#define COMPARE_ELSE(name, compare) \
void name(const Base & base) { \
  if (false) { \
    BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, compare) \
    BOOST_PP_IF(USE_ELSE, ELSE_CLAUSE, EMPTY_0)() \
  } \
}
#define COMPARE_NOELSE(name, compare) \
void name(const Base & base) { \
  if (false) { \
    BOOST_PP_REPEAT(BOOST_PP_SUB(NUM_DERIVED_CLASSES, 1), LINE, compare) \
  } else { \
    B(BOOST_PP_SUB(NUM_DERIVED_CLASSES, 1)); \
  } \
}
 
#define COMPARE_TYPE_INFO(n) typeid(base) == typeid(D ## n)
COMPARE_ELSE  (compare_type_info_else, COMPARE_TYPE_INFO)
COMPARE_NOELSE(compare_type_info,      COMPARE_TYPE_INFO)
#undef COMPARE_TYPE_INFO
 
#define CHECK_DYNAMIC_CAST(n) dynamic_cast<const D ## n *>(&base)
COMPARE_ELSE  (check_dynamic_cast_else, CHECK_DYNAMIC_CAST)
COMPARE_NOELSE(check_dynamic_cast,      CHECK_DYNAMIC_CAST)
#undef CHECK_DYNAMIC_CAST
 
#define COMPARE_VTABLE_ADDR(n) base.get_vtable_addr() == D ## n::vtable_addr
COMPARE_ELSE  (compare_vtable_addr_else, COMPARE_VTABLE_ADDR)
COMPARE_NOELSE(compare_vtable_addr,      COMPARE_VTABLE_ADDR)
#undef COMPARE_VTABLE_ADDR
 
#undef B
#undef CONST_REF
#undef ELSE_CLAUSE
#undef LINE
#undef L1
 
void call_virtual(const Base & base) {
  base.foo();
}
 
void call_visitor(const Base & base) {
  struct ConcreteBaseV : BaseV {
    #define LINE(z, n, unused) virtual void do_D ## n(const D ## n & obj) { BODY(n, obj); }
    BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
    #undef LINE
  } v;
  base.accept(v);
}
 
void call_acyclic_visitor(const Base & base) {
  struct ConcreteAcyclicV : AcyclicV 
    #define L1(n) , D ## n ## Visitor
    #define LINE(z, n, unused) BOOST_PP_IF(COND(n), L1, EMPTY_1)(n)
    BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
    #undef LINE
    #undef L1
  {
    #define L1(n) virtual void visit(const D ## n & obj) { BODY(n, obj); }
    #define LINE(z, n, unused) BOOST_PP_IF(COND(n), L1, EMPTY_1)(n)
    BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
    #undef LINE
    #undef L1
  } v;
  base.accept(v);
}
 
struct TypeInfoProxy {
  TypeInfoProxy(const std::type_info * t) : ti(t) {}
  const std::type_info * ti;
};
 
inline bool operator<(const TypeInfoProxy & lhs, const TypeInfoProxy & rhs) {
  return lhs.ti->before(*rhs.ti) != 0;
}
 
struct KeyValuePair {
  const std::type_info * first;
  TypeID second;
  
  operator std::pair<const TypeInfoProxy, TypeID>() { return std::make_pair(first, second); }
} initializers[] = {
  #define LINE(z, n, unused) { &typeid(D ## n), d ## n },
  BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
  #undef LINE
  { 0, extra }
};
 
std::map<TypeInfoProxy, TypeID> id_mapper(&initializers[0], &initializers[NUM_DERIVED_CLASSES]);
 
#define L1(n) case d ## n: BODY(n, static_cast<const D ## n &>(base)); break;
#define L2(n) case d ## n: break;
#define LINE1(z, n, unused) BOOST_PP_IF(COND(n), L1, EMPTY_1)(n)
#define LINE2(z, n, unused) BOOST_PP_IF(COND(n), L1, L2)(n)
 
#define NO_DEFAULT_SWITCH(name, val) \
  void name(const Base & base) { \
    switch (val) { \
      BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE1, ~) \
    } \
  }
#define DEFAULT_SWITCH(name, val) \
  void name(const Base & base) { \
    switch (val) { \
      BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE2, ~) \
      default: \
        std::cout << "Unknown\n"; \
        break; \
    } \
  }
 
NO_DEFAULT_SWITCH(switch_map_type_info,         id_mapper[&typeid(base)])
   DEFAULT_SWITCH(switch_map_type_info_default, id_mapper[&typeid(base)])
NO_DEFAULT_SWITCH(switch_virtual_function,         base.type_id())
   DEFAULT_SWITCH(switch_virtual_function_default, base.type_id())
NO_DEFAULT_SWITCH(switch_static_virtual,         base.get_type_id())
   DEFAULT_SWITCH(switch_static_virtual_default, base.get_type_id())
 
#if USE_TYPECODE
NO_DEFAULT_SWITCH(call_typecode,         base.type_code)
   DEFAULT_SWITCH(call_typecode_default, base.type_code)
#endif
 
 
#undef LINE2
#undef LINE1
#undef L2
#undef L1
 
template <typename InputIterator>
std::pair<typename std::iterator_traits<InputIterator>::value_type,
          typename std::iterator_traits<InputIterator>::value_type>
mean_and_standard_deviation(InputIterator first, InputIterator last) {
 typedef typename std::iterator_traits<InputIterator>::value_type ValueType;
 ValueType n = 0;
 ValueType mean = 0;
 ValueType M2 = 0;
 
 while (first != last) {
   ++n;
   ValueType x = *first++;
   ValueType delta = x - mean;
   mean += delta / n;
   M2 += delta * (x - mean);
 }
 
 if (n < 2) throw std::range_error("Unable to calculate standard deviation of less than two elements");
 
 ValueType variance = M2 / (n - 1);
 return std::make_pair(mean, sqrt(variance));
}
 
class Timer {
  public:
    Timer(void) {
      QueryPerformanceFrequency(&freq);
      QueryPerformanceCounter(&start);
    }
    
    double elapsed_time(void) const {
      LARGE_INTEGER end;
      QueryPerformanceCounter(&end);
      return (end.QuadPart - start.QuadPart)/(double)(freq.QuadPart);
    }
  private:
    LARGE_INTEGER freq;
    LARGE_INTEGER start;
 
    Timer(const Timer &);
    Timer & operator=(const Timer &);
};
 
class TestTimer : Timer {
  public:
    TestTimer(double * b, std::string * c, const char * f) : bucket(b), code(c), fn(f) {
      #define LINE(z, n, unused) D ## n::static_data = 0;
      BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
      #undef LINE
    }
    
    ~TestTimer() {
      *bucket += 1000.0 * elapsed_time();
      
      std::stringstream sstr;
      sstr << std::hex << "~";
      #define LINE(z, n, unused) sstr << (static_cast<unsigned>(D ## n::static_data) & 0xff);
      BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
      #undef LINE
      if (code->empty()) {
        *code = sstr.str();
      } else {
        if (*code != sstr.str()) {
          std::cout << *code << "\n";
          std::cout << fn << " " << sstr.str() << std::endl;
          exit(-1);
        }
      }
    }
  private:
    double * bucket;
    std::string * code;
    const char * fn;
    
    TestTimer(const TestTimer &);
    TestTimer & operator=(const TestTimer &);
};
 
#define TEST(bucket, function, hash) \
  { \
    TestTimer t(bucket, &hash, #function); \
    for (int i = 0; i < TEST_SIZE; i++) { \
      function(*data[i]); \
    } \
  }
 
#if USE_TYPECODE
  #define NUM_TESTS 17
#else
  #define NUM_TESTS 15
#endif
 
int main(int, char **) {
  set_typeids();
  srand(0);
  std::cout << std::fixed << std::setprecision(4);
  
  std::vector<Base *> data;
  data.reserve(TEST_SIZE);
  for (int i = 0; i < TEST_SIZE; i++) {
    switch (rand() % NUM_DERIVED_CLASSES) {
      #define LINE(z, n, unused) case n: data.push_back(new D ## n); break;
      BOOST_PP_REPEAT(NUM_DERIVED_CLASSES, LINE, ~)
      #undef LINE
    }
  }
  
  std::string hash;
  double bucket[NUM_TESTS][TEST_RUNS] = {};
  for (int i = 0; i < TEST_RUNS; i++) {
    for (int j = 0; j < TEST_REPS; j++) {
      TEST(&bucket[0][i], call_virtual, hash);
      TEST(&bucket[2][i], compare_type_info_else, hash);
      TEST(&bucket[4][i], check_dynamic_cast_else, hash);
      TEST(&bucket[5][i], switch_static_virtual, hash);
      TEST(&bucket[6][i], switch_static_virtual_default, hash);
      TEST(&bucket[7][i], switch_virtual_function, hash);
      TEST(&bucket[8][i], switch_virtual_function_default, hash);
      TEST(&bucket[10][i], compare_vtable_addr_else, hash);
      TEST(&bucket[11][i], call_visitor, hash);
      TEST(&bucket[12][i], call_acyclic_visitor, hash);
      TEST(&bucket[13][i], switch_map_type_info, hash);
      TEST(&bucket[14][i], switch_map_type_info_default, hash);
      #if USE_ELSE
        TEST(&bucket[1][i], compare_type_info, hash);
        TEST(&bucket[3][i], check_dynamic_cast, hash);
        TEST(&bucket[9][i], compare_vtable_addr, hash);
      #endif
      #if USE_TYPECODE
        TEST(&bucket[15][i], call_typecode, hash);
        TEST(&bucket[16][i], call_typecode_default, hash);
      #endif
    }
  }
  const char * names[] = {
    "virtual functions, ",
    "compare type_info no else, ",
    "compare type_info, ",
    "check with dynamic_cast no else, ",
    "check with dynamic_cast, ",
    "switch on static virtual, ",
    "switch on static virtual default, ",
    "switch on virtual function, ",
    "switch on virtual function default, ",
    "compare vtable address no else, ",
    "compare vtable address, ",
    "visitor, ",
    "acyclic visitor, ",
    "switch on type_info map, ",
    "switch on type_info map default, ",
    #if USE_TYPECODE
      "switch on type code, ",
      "switch on type code default, ",
    #endif
    "" 
  };
  std::pair<double, double> stats[NUM_TESTS];
  std::map<double, int> sorter;
  int text_length = 0;
  for (int i = 0; i < NUM_TESTS; i++) {
    stats[i] = mean_and_standard_deviation(&bucket[i][0], &bucket[i][TEST_RUNS]);
    if (stats[i].first) {
      sorter.insert(std::make_pair(stats[i].first, i));
      text_length = std::max<int>(strlen(names[i]), text_length);
    }
  }
  
  const int COLUMN_WIDTH = 12;
 
  std::stringstream sstr;
  sstr << NUM_DERIVED_CLASSES << " classes; " 
       << (USE_TYPECODE ? "using " : "no ") 
       << "type member; ";
  #ifdef HALF
    sstr << "Half, ";
  #elif defined(SINGLE)
    sstr << "Single, ";
  #elif defined(EMPTY)
    sstr << "Empty, ";
  #else
    sstr << "Full, ";
  #endif
  text_length = std::max<int>(sstr.str().length(), text_length);
  std::cout << std::setw(text_length) << std::left << sstr.str()
            << std::setw(COLUMN_WIDTH) << std::right << "Mean" << ", " 
            << std::setw(COLUMN_WIDTH) << std::right << "SD" << ", " 
            << std::setw(COLUMN_WIDTH) << std::right << "%CV" << "\n";
  for (std::map<double, int>::iterator itr = sorter.begin(); itr != sorter.end(); ++itr) {
    double mean = stats[itr->second].first;
    if (mean) {
      double sd = stats[itr->second].second;
      std::cout << std::setw(text_length) << std::left << names[itr->second] 
                << std::setw(COLUMN_WIDTH) << std::right << mean << ", " 
                << std::setw(COLUMN_WIDTH) << std::right << sd << ", " 
                << std::setw(COLUMN_WIDTH) << std::right << 100.0 * sd / mean << "%\n";
    }
  }
  std::cout << "\n";
 
  #ifdef SHOW_INDIVIDUAL_RUNS
    for (int i = 0; i < NUM_TESTS; i++) {
      if (stats[i].first) {
        std::cout << names[i];
        for (int j = 0; j < TEST_RUNS; j++) {
          std::cout << bucket[i][j] << ", ";
        }
        std::cout << "\n";
      }
    }
  #endif
  
  std::cout << std::flush;
}