Single Dispatch in C++
by Howard "SiCrane" Jeng

Dynamic Dispatch in C++

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.

Virtual Functions

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.

Visitor

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.

Acyclic Visitor

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 RTTI approaches

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

dynamic_cast if statements

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.

type_info if statements

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.

Switching on a Type Code

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.

As a Member Variable

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.

As a Virtual Function

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

Use type_info in a map

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

Non-Standard Approaches

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).

Comparing vtable Addresses

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.

Static Virtual Type Codes

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.

Performance

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.

Test One

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

3 classes; no type member; Full Mean SD %CV
virtual functions 363.39 5.72 1.57%
compare vtable address no else 395.97 6.81 1.72%
compare vtable address 396.61 5.50 1.39%
switch on static virtual default 405.28 8.50 2.10%
switch on static virtual 410.62 9.21 2.24%
visitor 455.61 6.87 1.51%
switch on virtual function 589.28 13.03 2.21%
switch on virtual function default 621.40 9.37 1.51%
compare type_info no else 1717.45 47.05 2.74%
compare type_info 2136.85 44.43 2.08%
switch on type_info map default 2419.69 56.90 2.35%
switch on type_info map 2456.39 50.11 2.04%
check with dynamic_cast no else 3220.87 62.35 1.94%
check with dynamic_cast 3731.42 84.44 2.26%
acyclic visitor 4226.15 47.12 1.11%

3 classes; using type member; Full Mean SD %CV
switch on type code 418.41 7.50 1.79%
virtual functions 426.93 7.35 1.72%
switch on type code default 430.92 7.83 1.82%
compare vtable address no else 456.23 7.28 1.60%
switch on static virtual 457.76 7.42 1.62%
compare vtable address 458.13 7.42 1.62%
switch on static virtual default 459.34 7.55 1.64%
visitor 510.35 10.40 2.04%
switch on virtual function 637.04 11.39 1.79%
switch on virtual function default 664.94 13.19 1.98%
compare type_info no else 1847.47 43.87 2.37%
compare type_info 2227.56 47.93 2.15%
switch on type_info map default 2501.39 58.33 2.33%
switch on type_info map 2528.37 55.51 2.20%
check with dynamic_cast no else 3361.83 88.64 2.64%
check with dynamic_cast 3830.28 74.25 1.94%
acyclic visitor 4345.80 109.76 2.53%

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.

3 classes; combined; Full Mean SD %CV
virtual functions 363.39 5.72 1.57%
compare vtable address no else 395.97 6.81 1.72%
compare vtable address 396.61 5.50 1.39%
switch on static virtual default 405.28 8.50 2.10%
switch on static virtual 410.62 9.21 2.24%
switch on type code 418.41 7.50 1.79%
switch on type code default 430.92 7.83 1.82%
visitor 455.61 6.87 1.51%
switch on virtual function 589.28 13.03 2.21%
switch on virtual function default 621.40 9.37 1.51%
compare type_info no else 1717.45 47.05 2.74%
compare type_info 2136.85 44.43 2.08%
switch on type_info map default 2419.69 56.90 2.35%
switch on type_info map 2456.39 50.11 2.04%
check with dynamic_cast no else 3220.87 62.35 1.94%
check with dynamic_cast 3731.42 84.44 2.26%
acyclic visitor 4226.15 47.12 1.11%

6 classes; no type member; Full Mean SD %CV
virtual functions 425.08 12.38 2.91%
compare vtable address 479.54 17.80 3.71%
compare vtable address no else 481.15 14.38 2.99%
switch on static virtual default 482.86 15.60 3.23%
switch on static virtual 490.94 13.33 2.71%
visitor 510.81 18.55 3.63%
switch on virtual function 697.73 24.79 3.55%
switch on virtual function default 705.15 24.61 3.49%
switch on type_info map default 3077.87 82.11 2.67%
switch on type_info map 3110.60 79.55 2.56%
compare type_info no else 3392.79 57.98 1.71%
compare type_info 3554.24 89.32 2.51%
acyclic visitor 5706.67 174.44 3.06%
check with dynamic_cast no else 6929.94 146.02 2.11%
check with dynamic_cast 7062.55 177.71 2.52%

6 classes; using type member; Full Mean SD %CV
virtual functions 448.35 10.17 2.27%
switch on type code default 463.27 10.66 2.30%
switch on type code 468.42 10.61 2.26%
compare vtable address no else 491.15 11.10 2.26%
switch on static virtual 494.89 9.14 1.85%
switch on static virtual default 495.62 7.22 1.46%
compare vtable address 496.83 8.57 1.72%
visitor 527.88 10.96 2.08%
switch on virtual function 700.18 11.23 1.60%
switch on virtual function default 706.58 13.50 1.91%
switch on type_info map default 2958.83 83.66 2.83%
switch on type_info map 2983.41 82.48 2.76%
compare type_info no else 3238.10 61.21 1.89%
compare type_info 3423.08 73.30 2.14%
acyclic visitor 5415.70 99.86 1.84%
check with dynamic_cast no else 6559.76 115.50 1.76%
check with dynamic_cast 6935.94 121.62 1.75%

6 classes; combined; Full Mean SD %CV
virtual functions 425.08 12.38 2.91%
switch on type code default 463.27 10.66 2.30%
switch on type code 468.42 10.61 2.26%
compare vtable address 479.54 17.80 3.71%
compare vtable address no else 481.15 14.38 2.99%
switch on static virtual default 482.86 15.60 3.23%
switch on static virtual 490.94 13.33 2.71%
visitor 510.81 18.55 3.63%
switch on virtual function 697.73 24.79 3.55%
switch on virtual function default 705.15 24.61 3.49%
switch on type_info map default 3077.87 82.11 2.67%
switch on type_info map 3110.60 79.55 2.56%
compare type_info no else 3392.79 57.98 1.71%
compare type_info 3554.24 89.32 2.51%
acyclic visitor 5706.67 174.44 3.06%
check with dynamic_cast no else 6929.94 146.02 2.11%
check with dynamic_cast 7062.55 177.71 2.52%

9 classes; no type member; Full Mean SD %CV
virtual functions 419.75 8.32 1.98%
switch on static virtual default 457.80 6.55 1.43%
switch on static virtual 473.31 7.39 1.56%
compare vtable address 486.44 9.20 1.89%
compare vtable address no else 496.55 9.74 1.96%
visitor 498.15 10.01 2.01%
switch on virtual function 685.55 11.45 1.67%
switch on virtual function default 692.79 12.77 1.84%
switch on type_info map default 3280.27 66.96 2.04%
switch on type_info map 3332.73 57.36 1.72%
compare type_info no else 4461.50 62.01 1.39%
compare type_info 4676.25 81.15 1.74%
acyclic visitor 6528.78 128.43 1.97%
check with dynamic_cast no else 9469.32 175.49 1.85%
check with dynamic_cast 9693.18 165.50 1.71%

9 classes; using type member; Full Mean SD %CV
virtual functions 459.64 11.21 2.44%
switch on type code 464.86 11.92 2.56%
switch on type code default 466.34 13.82 2.96%
switch on static virtual default 504.61 14.45 2.86%
switch on static virtual 509.77 13.59 2.67%
compare vtable address no else 531.32 12.81 2.41%
compare vtable address 535.46 13.30 2.48%
visitor 541.27 12.86 2.38%
switch on virtual function 733.51 22.16 3.02%
switch on virtual function default 735.46 19.44 2.64%
switch on type_info map default 3410.68 54.18 1.59%
switch on type_info map 3459.59 62.24 1.80%
compare type_info no else 4540.38 107.81 2.37%
compare type_info 4661.27 106.12 2.28%
acyclic visitor 6501.69 149.37 2.30%
check with dynamic_cast no else 9461.76 172.66 1.82%
check with dynamic_cast 9724.18 219.70 2.26%

9 classes; combined; Full Mean SD %CV
virtual functions 419.75 8.32 1.98%
switch on static virtual default 457.80 6.55 1.43%
switch on type code 464.86 11.92 2.56%
switch on type code default 466.34 13.82 2.96%
switch on static virtual 473.31 7.39 1.56%
compare vtable address 486.44 9.20 1.89%
compare vtable address no else 496.55 9.74 1.96%
visitor 498.15 10.01 2.01%
switch on virtual function 685.55 11.45 1.67%
switch on virtual function default 692.79 12.77 1.84%
switch on type_info map default 3280.27 66.96 2.04%
switch on type_info map 3332.73 57.36 1.72%
compare type_info no else 4461.50 62.01 1.39%
compare type_info 4676.25 81.15 1.74%
acyclic visitor 6528.78 128.43 1.97%
check with dynamic_cast no else 9469.32 175.49 1.85%
check with dynamic_cast 9693.18 165.50 1.71%

12 classes; no type member; Full Mean SD %CV
virtual functions 424.95 9.46 2.23%
switch on static virtual default 475.37 7.22 1.52%
switch on static virtual 487.54 8.75 1.80%
visitor 504.01 9.35 1.86%
compare vtable address 517.83 10.25 1.98%
compare vtable address no else 536.24 11.89 2.22%
switch on virtual function 702.52 12.33 1.76%
switch on virtual function default 704.47 13.46 1.91%
switch on type_info map default 3714.37 76.22 2.05%
switch on type_info map 3750.81 51.01 1.36%
compare type_info no else 5894.50 105.26 1.79%
compare type_info 6119.93 122.25 2.00%
acyclic visitor 8059.82 113.27 1.41%
check with dynamic_cast no else 12461.73 215.37 1.73%
check with dynamic_cast 12582.33 145.50 1.16%

12 classes; using type member; Full Mean SD %CV
virtual functions 472.00 10.78 2.28%
switch on type code default 476.49 11.13 2.34%
switch on type code 478.78 10.93 2.28%
switch on static virtual 514.38 9.89 1.92%
switch on static virtual default 516.13 9.94 1.93%
visitor 546.44 9.87 1.81%
compare vtable address 568.19 11.18 1.97%
compare vtable address no else 568.43 12.22 2.15%
switch on virtual function 744.32 16.46 2.21%
switch on virtual function default 747.34 17.25 2.31%
switch on type_info map 3875.46 57.35 1.48%
switch on type_info map default 4036.91 58.81 1.46%
compare type_info no else 5895.19 93.63 1.59%
compare type_info 6209.67 122.50 1.97%
acyclic visitor 7993.71 148.56 1.86%
check with dynamic_cast no else 12385.55 217.27 1.75%
check with dynamic_cast 12757.06 196.49 1.54%

12 classes; combined; Full Mean SD %CV
virtual functions 424.95 9.46 2.23%
switch on static virtual default 475.37 7.22 1.52%
switch on type code default 476.49 11.13 2.34%
switch on type code 478.78 10.93 2.28%
switch on static virtual 487.54 8.75 1.80%
visitor 504.01 9.35 1.86%
compare vtable address 517.83 10.25 1.98%
compare vtable address no else 536.24 11.89 2.22%
switch on virtual function 702.52 12.33 1.76%
switch on virtual function default 704.47 13.46 1.91%
switch on type_info map default 3714.37 76.22 2.05%
switch on type_info map 3750.81 51.01 1.36%
compare type_info no else 5894.50 105.26 1.79%
compare type_info 6119.93 122.25 2.00%
acyclic visitor 8059.82 113.27 1.41%
check with dynamic_cast no else 12461.73 215.37 1.73%
check with dynamic_cast 12582.33 145.50 1.16%

15 classes; no type member; Full Mean SD %CV
virtual functions 425.78 8.26 1.94%
switch on static virtual default 472.91 11.72 2.48%
switch on static virtual 490.04 11.82 2.41%
visitor 505.42 11.70 2.32%
compare vtable address 555.91 14.24 2.56%
compare vtable address no else 572.02 12.10 2.11%
switch on virtual function 637.73 14.45 2.27%
switch on virtual function default 641.57 15.79 2.46%
switch on type_info map default 3914.90 76.96 1.97%
switch on type_info map 3998.19 45.43 1.14%
compare type_info 7249.31 171.41 2.36%
compare type_info no else 7297.51 160.11 2.19%
acyclic visitor 9270.41 182.32 1.97%
check with dynamic_cast no else 15434.56 338.31 2.19%
check with dynamic_cast 15665.37 298.73 1.91%

15 classes; using type member; Full Mean SD %CV
virtual functions 474.41 7.73 1.63%
switch on type code 483.30 7.79 1.61%
switch on type code default 488.27 6.45 1.32%
switch on static virtual default 514.56 11.55 2.25%
switch on static virtual 522.36 10.22 1.96%
visitor 550.60 11.90 2.16%
compare vtable address 588.60 14.25 2.42%
compare vtable address no else 608.61 10.35 1.70%
switch on virtual function 678.37 15.40 2.27%
switch on virtual function default 682.16 16.00 2.35%
switch on type_info map default 3963.79 81.76 2.06%
switch on type_info map 3998.48 96.34 2.41%
compare type_info no else 7229.06 97.16 1.34%
compare type_info 7376.62 112.48 1.52%
acyclic visitor 9281.07 180.30 1.94%
check with dynamic_cast no else 15489.90 356.42 2.30%
check with dynamic_cast 15545.74 292.56 1.88%

15 classes; combined; Full Mean SD %CV
virtual functions 425.78 8.26 1.94%
switch on static virtual default 472.91 11.72 2.48%
switch on type code 483.30 7.79 1.61%
switch on type code default 488.27 6.45 1.32%
switch on static virtual 490.04 11.82 2.41%
visitor 505.42 11.70 2.32%
compare vtable address 555.91 14.24 2.56%
compare vtable address no else 572.02 12.10 2.11%
switch on virtual function 637.73 14.45 2.27%
switch on virtual function default 641.57 15.79 2.46%
switch on type_info map default 3914.90 76.96 1.97%
switch on type_info map 3998.19 45.43 1.14%
compare type_info 7249.31 171.41 2.36%
compare type_info no else 7297.51 160.11 2.19%
acyclic visitor 9270.41 182.32 1.97%
check with dynamic_cast no else 15434.56 338.31 2.19%
check with dynamic_cast 15665.37 298.73 1.91%

Some thoughts:

Test Two

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.

3 classes; no type member; Half Mean SD %CV
compare vtable address 346.75 9.79 2.82%
switch on static virtual default 357.15 9.49 2.66%
virtual functions 364.85 8.22 2.25%
switch on static virtual 375.44 8.88 2.36%
visitor 419.89 11.89 2.83%
switch on virtual function 484.82 15.09 3.11%
switch on virtual function default 506.54 15.97 3.15%
compare type_info 1725.01 37.38 2.17%
switch on type_info map 2448.89 78.60 3.21%
switch on type_info map default 2519.08 59.36 2.36%
check with dynamic_cast 3238.05 55.56 1.72%
acyclic visitor 4086.35 137.21 3.36%

3 classes; using type member; Half Mean SD %CV
switch on type code 376.99 6.73 1.78%
switch on type code default 388.48 6.22 1.60%
compare vtable address 399.68 7.12 1.78%
virtual functions 412.65 7.64 1.85%
switch on static virtual default 414.50 7.55 1.82%
switch on static virtual 421.42 7.19 1.71%
visitor 474.39 8.62 1.82%
switch on virtual function 527.81 12.25 2.32%
switch on virtual function default 538.78 12.32 2.29%
compare type_info 1789.29 43.51 2.43%
switch on type_info map default 2437.76 59.18 2.43%
switch on type_info map 2468.69 49.63 2.01%
check with dynamic_cast 3302.06 73.03 2.21%
acyclic visitor 4131.45 85.62 2.07%

3 classes; combined; Half Mean SD %CV
compare vtable address 346.75 9.79 2.82%
switch on static virtual default 357.15 9.49 2.66%
virtual functions 364.85 8.22 2.25%
switch on static virtual 375.44 8.88 2.36%
switch on type code 376.99 6.73 1.78%
switch on type code default 388.48 6.22 1.60%
visitor 419.89 11.89 2.83%
switch on virtual function 484.82 15.09 3.11%
switch on virtual function default 506.54 15.97 3.15%
compare type_info 1725.01 37.38 2.17%
switch on type_info map 2448.89 78.60 3.21%
switch on type_info map default 2519.08 59.36 2.36%
check with dynamic_cast 3238.05 55.56 1.72%
acyclic visitor 4086.35 137.21 3.36%

6 classes; no type member; Half Mean SD %CV
switch on static virtual 385.77 11.03 2.86%
virtual functions 395.74 13.16 3.32%
switch on static virtual default 409.23 13.76 3.36%
compare vtable address 434.45 16.99 3.91%
visitor 458.66 17.37 3.79%
switch on virtual function default 569.47 23.66 4.16%
switch on virtual function 634.22 24.70 3.89%
compare type_info 2346.18 99.49 4.24%
switch on type_info map default 2900.76 121.00 4.17%
switch on type_info map 2977.65 128.46 4.31%
check with dynamic_cast 4960.43 172.57 3.48%
acyclic visitor 5030.45 239.35 4.76%

6 classes; using type member; Half Mean SD %CV
switch on static virtual 411.98 7.92 1.92%
switch on type code default 415.92 6.72 1.62%
virtual functions 431.27 9.00 2.09%
switch on static virtual default 441.60 8.57 1.94%
switch on type code 457.53 9.62 2.10%
compare vtable address 470.59 10.77 2.29%
visitor 498.25 10.66 2.14%
switch on virtual function default 600.80 14.83 2.47%
switch on virtual function 661.46 14.80 2.24%
compare type_info 2369.22 50.01 2.11%
switch on type_info map default 2886.60 73.76 2.56%
switch on type_info map 2969.41 75.60 2.55%
check with dynamic_cast 4833.96 97.36 2.01%
acyclic visitor 5017.06 115.81 2.31%

6 classes; combined; Half Mean SD %CV
switch on static virtual 385.77 11.03 2.86%
virtual functions 395.74 13.16 3.32%
switch on static virtual default 409.23 13.76 3.36%
switch on type code default 415.92 6.72 1.62%
compare vtable address 434.45 16.99 3.91%
switch on type code 457.53 9.62 2.10%
visitor 458.66 17.37 3.79%
switch on virtual function default 569.47 23.66 4.16%
switch on virtual function 634.22 24.70 3.89%
compare type_info 2346.18 99.49 4.24%
switch on type_info map default 2900.76 121.00 4.17%
switch on type_info map 2977.65 128.46 4.31%
check with dynamic_cast 4960.43 172.57 3.48%
acyclic visitor 5030.45 239.35 4.76%

9 classes; no type member; Half Mean SD %CV
compare vtable address 377.61 7.66 2.03%
virtual functions 407.70 8.48 2.08%
switch on static virtual default 429.50 8.99 2.09%
visitor 466.22 10.90 2.34%
switch on static virtual 497.55 12.34 2.48%
switch on virtual function 600.62 12.68 2.11%
switch on virtual function default 602.00 13.23 2.20%
switch on type_info map default 3212.20 55.48 1.73%
switch on type_info map 3263.36 61.24 1.88%
compare type_info 3471.50 76.97 2.22%
acyclic visitor 5971.82 119.11 1.99%
check with dynamic_cast 7621.40 192.10 2.52%

9 classes; using type member; Half Mean SD %CV
compare vtable address 430.17 7.89 1.83%
switch on type code default 433.24 6.75 1.56%
switch on type code 441.00 8.20 1.86%
virtual functions 445.10 7.28 1.64%
switch on static virtual default 488.65 9.87 2.02%
visitor 515.78 6.28 1.22%
switch on static virtual 542.94 10.22 1.88%
switch on virtual function 645.52 14.59 2.26%
switch on virtual function default 646.58 14.25 2.20%
switch on type_info map default 3235.86 63.17 1.95%
switch on type_info map 3285.96 74.38 2.26%
compare type_info 3569.21 82.78 2.32%
acyclic visitor 6011.44 84.14 1.40%
check with dynamic_cast 7655.37 163.95 2.14%

9 classes; combined; Half Mean SD %CV
compare vtable address 377.61 7.66 2.03%
virtual functions 407.70 8.48 2.08%
switch on static virtual default 429.50 8.99 2.09%
switch on type code default 433.24 6.75 1.56%
switch on type code 441.00 8.20 1.86%
visitor 466.22 10.90 2.34%
switch on static virtual 497.55 12.34 2.48%
switch on virtual function 600.62 12.68 2.11%
switch on virtual function default 602.00 13.23 2.20%
switch on type_info map default 3212.20 55.48 1.73%
switch on type_info map 3263.36 61.24 1.88%
compare type_info 3471.50 76.97 2.22%
acyclic visitor 5971.82 119.11 1.99%
check with dynamic_cast 7621.40 192.10 2.52%

12 classes; no type member; Half Mean SD %CV
compare vtable address 378.34 9.53 2.52%
switch on static virtual default 413.97 12.54 3.03%
virtual functions 414.85 9.12 2.20%
switch on static virtual 432.35 11.54 2.67%
visitor 467.98 12.55 2.68%
switch on virtual function default 597.84 15.43 2.58%
switch on virtual function 680.02 19.41 2.85%
switch on type_info map 3583.22 77.14 2.15%
switch on type_info map default 3824.23 97.08 2.54%
compare type_info 4241.60 46.06 1.09%
acyclic visitor 6547.14 199.09 3.04%
check with dynamic_cast 9126.36 240.75 2.64%

12 classes; using type member; Half Mean SD %CV
switch on type code default 437.33 7.85 1.79%
compare vtable address 440.41 7.23 1.64%
switch on static virtual default 455.49 7.22 1.58%
virtual functions 462.39 8.89 1.92%
switch on static virtual 465.53 7.15 1.54%
switch on type code 510.34 10.08 1.98%
visitor 523.61 8.52 1.63%
switch on virtual function default 632.27 12.30 1.94%
switch on virtual function 734.62 14.24 1.94%
switch on type_info map 3751.60 61.26 1.63%
switch on type_info map default 3927.97 76.55 1.95%
compare type_info 4393.22 80.94 1.84%
acyclic visitor 6575.58 109.88 1.67%
check with dynamic_cast 9194.17 175.25 1.91%

12 classes; combined; Half Mean SD %CV
compare vtable address 378.34 9.53 2.52%
switch on static virtual default 413.97 12.54 3.03%
virtual functions 414.85 9.12 2.20%
switch on static virtual 432.35 11.54 2.67%
switch on type code default 437.33 7.85 1.79%
visitor 467.98 12.55 2.68%
switch on type code 510.34 10.08 1.98%
switch on virtual function default 597.84 15.43 2.58%
switch on virtual function 680.02 19.41 2.85%
switch on type_info map 3583.22 77.14 2.15%
switch on type_info map default 3824.23 97.08 2.54%
compare type_info 4241.60 46.06 1.09%
acyclic visitor 6547.14 199.09 3.04%
check with dynamic_cast 9126.36 240.75 2.64%

15 classes; no type member; Half Mean SD %CV
compare vtable address 420.06 8.37 1.99%
switch on static virtual default 422.35 12.20 2.89%
virtual functions 427.88 8.04 1.88%
visitor 469.48 8.28 1.76%
switch on static virtual 541.45 17.61 3.25%
switch on virtual function default 602.34 13.31 2.21%
switch on virtual function 619.30 14.97 2.42%
switch on type_info map default 3847.85 95.52 2.48%
switch on type_info map 3954.76 117.86 2.98%
compare type_info 5623.56 114.44 2.04%
acyclic visitor 7699.11 215.35 2.80%
check with dynamic_cast 11917.22 231.79 1.95%

15 classes; using type member; Half Mean SD %CV
switch on type code default 445.09 10.10 2.27%
virtual functions 457.71 11.02 2.41%
compare vtable address 461.85 12.55 2.72%
switch on static virtual default 467.36 13.15 2.81%
switch on type code 473.79 12.26 2.59%
visitor 530.34 16.29 3.07%
switch on static virtual 585.23 19.19 3.28%
switch on virtual function default 641.10 19.37 3.02%
switch on virtual function 674.95 21.33 3.16%
switch on type_info map default 3930.20 145.63 3.71%
switch on type_info map 3977.33 145.81 3.67%
compare type_info 5774.78 196.94 3.41%
acyclic visitor 7738.00 268.84 3.47%
check with dynamic_cast 12440.78 436.37 3.51%

15 classes; combined; Half Mean SD %CV
compare vtable address 420.06 8.37 1.99%
switch on static virtual default 422.35 12.20 2.89%
virtual functions 427.88 8.04 1.88%
switch on type code default 445.09 10.10 2.27%
visitor 469.48 8.28 1.76%
switch on type code 473.79 12.26 2.59%
switch on static virtual 541.45 17.61 3.25%
switch on virtual function default 602.34 13.31 2.21%
switch on virtual function 619.30 14.97 2.42%
switch on type_info map default 3847.85 95.52 2.48%
switch on type_info map 3954.76 117.86 2.98%
compare type_info 5623.56 114.44 2.04%
acyclic visitor 7699.11 215.35 2.80%
check with dynamic_cast 11917.22 231.79 1.95%

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.

Test Three

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.

3 classes; no type member; Single Mean SD %CV
compare vtable address 229.37 4.94 2.15%
switch on static virtual 253.71 5.33 2.10%
switch on static virtual default 328.76 7.00 2.13%
virtual functions 360.61 11.29 3.13%
visitor 394.94 11.26 2.85%
switch on virtual function 405.46 9.56 2.36%
switch on virtual function default 476.50 13.66 2.87%
compare type_info 1043.13 33.57 3.22%
check with dynamic_cast 1994.94 48.04 2.41%
switch on type_info map default 2418.54 80.25 3.32%
switch on type_info map 2420.67 77.62 3.21%
acyclic visitor 3616.40 107.07 2.96%

3 classes; using type member; Single Mean SD %CV
compare vtable address 301.14 4.33 1.44%
switch on type code 315.11 4.34 1.38%
switch on static virtual 339.23 5.34 1.57%
switch on type code default 363.83 5.91 1.63%
switch on static virtual default 384.37 7.15 1.86%
virtual functions 407.64 8.20 2.01%
visitor 458.28 9.16 2.00%
switch on virtual function 478.77 8.83 1.84%
switch on virtual function default 557.90 10.35 1.85%
compare type_info 1100.49 28.44 2.58%
check with dynamic_cast 2054.17 49.05 2.39%
switch on type_info map 2449.41 55.98 2.29%
switch on type_info map default 2490.62 55.13 2.21%
acyclic visitor 3733.71 94.34 2.53%

3 classes; combined; Single Mean SD %CV
compare vtable address 229.37 4.94 2.15%
switch on static virtual 253.71 5.33 2.10%
switch on type code 315.11 4.34 1.38%
switch on static virtual default 328.76 7.00 2.13%
virtual functions 360.61 11.29 3.13%
switch on type code default 363.83 5.91 1.63%
visitor 394.94 11.26 2.85%
switch on virtual function 405.46 9.56 2.36%
switch on virtual function default 476.50 13.66 2.87%
compare type_info 1043.13 33.57 3.22%
check with dynamic_cast 1994.94 48.04 2.41%
switch on type_info map default 2418.54 80.25 3.32%
switch on type_info map 2420.67 77.62 3.21%
acyclic visitor 3616.40 107.07 2.96%

6 classes; no type member; Single Mean SD %CV
compare vtable address 191.37 3.64 1.90%
switch on static virtual 216.06 3.83 1.77%
switch on static virtual default 255.93 5.96 2.33%
virtual functions 386.95 14.01 3.62%
visitor 412.16 11.91 2.89%
switch on virtual function 424.07 13.08 3.09%
switch on virtual function default 476.96 16.14 3.38%
compare type_info 989.86 33.52 3.39%
check with dynamic_cast 2018.01 59.50 2.95%
switch on type_info map default 2748.69 89.91 3.27%
switch on type_info map 2758.03 73.47 2.66%
acyclic visitor 3578.44 107.54 3.01%

6 classes; using type member; Single Mean SD %CV
compare vtable address 250.97 4.45 1.77%
switch on type code 252.36 3.72 1.48%
switch on static virtual 288.60 3.50 1.21%
switch on type code default 311.28 4.48 1.44%
switch on static virtual default 323.16 4.61 1.43%
virtual functions 421.80 9.95 2.36%
visitor 467.13 11.33 2.43%
switch on virtual function 469.43 10.95 2.33%
switch on virtual function default 525.63 13.34 2.54%
compare type_info 1027.78 32.98 3.21%
check with dynamic_cast 2045.08 60.03 2.94%
switch on type_info map default 2794.52 61.72 2.21%
switch on type_info map 2799.14 63.84 2.28%
acyclic visitor 3625.71 129.65 3.58%

6 classes; combined; Single Mean SD %CV
compare vtable address 191.37 3.64 1.90%
switch on static virtual 216.06 3.83 1.77%
switch on type code 252.36 3.72 1.48%
switch on static virtual default 255.93 5.96 2.33%
switch on type code default 311.28 4.48 1.44%
virtual functions 386.95 14.01 3.62%
visitor 412.16 11.91 2.89%
switch on virtual function 424.07 13.08 3.09%
switch on virtual function default 476.96 16.14 3.38%
compare type_info 989.86 33.52 3.39%
check with dynamic_cast 2018.01 59.50 2.95%
switch on type_info map default 2748.69 89.91 3.27%
switch on type_info map 2758.03 73.47 2.66%
acyclic visitor 3578.44 107.54 3.01%

9 classes; no type member; Single Mean SD %CV
compare vtable address 178.46 2.38 1.33%
switch on static virtual 210.09 3.44 1.64%
switch on static virtual default 254.72 4.42 1.74%
virtual functions 398.53 7.24 1.82%
visitor 409.19 8.57 2.09%
switch on virtual function 446.54 10.79 2.42%
switch on virtual function default 472.60 10.25 2.17%
compare type_info 960.03 19.29 2.01%
check with dynamic_cast 1996.49 42.52 2.13%
switch on type_info map default 3072.98 39.68 1.29%
switch on type_info map 3091.56 50.25 1.63%
acyclic visitor 3584.51 72.69 2.03%

9 classes; using type member; Single Mean SD %CV
compare vtable address 234.96 2.64 1.12%
switch on type code 243.14 3.53 1.45%
switch on static virtual 282.74 3.79 1.34%
switch on type code default 307.98 4.48 1.45%
switch on static virtual default 321.06 4.80 1.50%
virtual functions 444.56 8.35 1.88%
visitor 469.88 8.54 1.82%
switch on virtual function 489.52 10.24 2.09%
switch on virtual function default 516.01 9.93 1.92%
compare type_info 997.57 23.32 2.34%
check with dynamic_cast 2045.95 57.42 2.81%
switch on type_info map 3121.35 92.66 2.97%
switch on type_info map default 3125.81 70.35 2.25%
acyclic visitor 3638.87 96.72 2.66%

9 classes; combined; Single Mean SD %CV
compare vtable address 178.46 2.38 1.33%
switch on static virtual 210.09 3.44 1.64%
switch on type code 243.14 3.53 1.45%
switch on static virtual default 254.72 4.42 1.74%
switch on type code default 307.98 4.48 1.45%
virtual functions 398.53 7.24 1.82%
visitor 409.19 8.57 2.09%
switch on virtual function 446.54 10.79 2.42%
switch on virtual function default 472.60 10.25 2.17%
compare type_info 960.03 19.29 2.01%
check with dynamic_cast 1996.49 42.52 2.13%
switch on type_info map default 3072.98 39.68 1.29%
switch on type_info map 3091.56 50.25 1.63%
acyclic visitor 3584.51 72.69 2.03%

12 classes; no type member; Single Mean SD %CV
compare vtable address 176.61 2.63 1.49%
switch on static virtual 203.27 2.45 1.20%
switch on static virtual default 244.64 3.86 1.58%
virtual functions 423.63 12.72 3.00%
visitor 428.02 11.52 2.69%
switch on virtual function 431.05 12.11 2.81%
switch on virtual function default 475.16 13.31 2.80%
compare type_info 956.31 30.54 3.19%
check with dynamic_cast 2042.39 63.26 3.10%
switch on type_info map default 3572.71 89.43 2.50%
switch on type_info map 3621.41 66.83 1.85%
acyclic visitor 3670.29 74.24 2.02%

12 classes; using type member; Single Mean SD %CV
compare vtable address 230.40 3.50 1.52%
switch on type code 239.46 3.85 1.61%
switch on static virtual 277.19 4.05 1.46%
switch on type code default 302.28 4.86 1.61%
switch on static virtual default 312.86 5.38 1.72%
virtual functions 436.17 9.12 2.09%
visitor 462.84 9.55 2.06%
switch on virtual function 466.55 11.33 2.43%
switch on virtual function default 519.56 12.23 2.35%
compare type_info 1001.32 24.45 2.44%
check with dynamic_cast 2089.23 50.54 2.42%
switch on type_info map default 3497.53 96.56 2.76%
switch on type_info map 3522.01 90.82 2.58%
acyclic visitor 3671.07 87.64 2.39%

12 classes; combined; Single Mean SD %CV
compare vtable address 176.61 2.63 1.49%
switch on static virtual 203.27 2.45 1.20%
switch on type code 239.46 3.85 1.61%
switch on static virtual default 244.64 3.86 1.58%
switch on type code default 302.28 4.86 1.61%
virtual functions 423.63 12.72 3.00%
visitor 428.02 11.52 2.69%
switch on virtual function 431.05 12.11 2.81%
switch on virtual function default 475.16 13.31 2.80%
compare type_info 956.31 30.54 3.19%
check with dynamic_cast 2042.39 63.26 3.10%
switch on type_info map default 3572.71 89.43 2.50%
switch on type_info map 3621.41 66.83 1.85%
acyclic visitor 3670.29 74.24 2.02%

15 classes; no type member; Single Mean SD %CV
compare vtable address 168.85 2.38 1.41%
switch on static virtual 201.16 2.93 1.46%
switch on static virtual default 241.93 4.02 1.66%
virtual functions 409.77 10.03 2.45%
visitor 416.72 8.67 2.08%
switch on virtual function 431.65 11.10 2.57%
switch on virtual function default 485.24 11.17 2.30%
compare type_info 945.37 24.55 2.60%
check with dynamic_cast 2020.84 43.93 2.17%
acyclic visitor 3610.77 82.86 2.29%
switch on type_info map default 3712.09 98.83 2.66%
switch on type_info map 3799.08 66.97 1.76%

15 classes; using type member; Single Mean SD %CV
compare vtable address 226.59 2.72 1.20%
switch on type code 232.69 3.30 1.42%
switch on static virtual 277.19 3.87 1.40%
switch on static virtual default 308.86 5.35 1.73%
switch on type code default 339.77 4.91 1.44%
virtual functions 443.98 10.00 2.25%
visitor 478.48 10.19 2.13%
switch on virtual function 558.43 13.42 2.40%
switch on virtual function default 591.34 11.34 1.92%
compare type_info 1017.08 25.32 2.49%
check with dynamic_cast 2140.53 63.22 2.95%
acyclic visitor 3687.55 80.93 2.19%
switch on type_info map default 3790.44 104.52 2.76%
switch on type_info map 3830.84 82.36 2.15%

15 classes; combined; Single Mean SD %CV
compare vtable address 168.85 2.38 1.41%
switch on static virtual 201.16 2.93 1.46%
switch on type code 232.69 3.30 1.42%
switch on static virtual default 241.93 4.02 1.66%
switch on type code default 339.77 4.91 1.44%
virtual functions 409.77 10.03 2.45%
visitor 416.72 8.67 2.08%
switch on virtual function 431.65 11.10 2.57%
switch on virtual function default 485.24 11.17 2.30%
compare type_info 945.37 24.55 2.60%
check with dynamic_cast 2020.84 43.93 2.17%
acyclic visitor 3610.77 82.86 2.29%
switch on type_info map default 3712.09 98.83 2.66%
switch on type_info map 3799.08 66.97 1.76%

Performance Test Program

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;
}