Are there alternatives to polymorphism in C++?

Question

The CRTP is suggested in this question about dynamic polymorphism. However, this pattern is allegedly only useful for static polymorphism. The design I am looking at seems to be hampered speedwise by virtual function calls, as hinted at here. A speedup of even 2.5x would be fantastic.

The classes in question are simple and can be coded completely inline, however it is not known until runtime which classes will be used. Furthermore, they may be chained, in any order, heaping performance insult onto injury.

Any suggestions (including how the CRTP can be used in this case) welcome.

Edit: Googling turns up a mention of function templates. These look promising.

Answer 1

Polymorphism literally means multiple (poly) forms (morphs). In statically typed languages (such as C++) there are three types of polymorphism.

1. Adhoc polymorphism: This is best seen in C++ as function and method overloading. The same function name will bind to different methods based on matching the compile time type of the parameters of the call to the function or method signature.
2. Parametric polymorphism: In C++ this is templates and all the fun things you can do with it such as CRTP, specialization, partial specialization, meta-programming etc. Again this sort of polymorphism where the same template name can do different things based on the template parameters is a compile time polymorphism.
3. Subtype Polymorphism: Finally this is what we think of when we hear the word polymorphism in C++. This is where derived classes override virtual functions to specialize behavior. The same type of pointer to a base class can have different behavior based on the concrete derived type it is pointing to. This is the way to get run time polymorphism in C++.

If it is not known until runtime which classes will be used, you must use Subtype Polymorphism which will involve virtual function calls.

Virtual method calls have a very small performance overhead over statically bound calls. I'd urge you to look at the answers to this SO question.

Answer 2

You can go the Ole C Route and use unions. Although that too can be messy.

Answer 3

I agree with m-sharp that you're not going to avoid runtime polymorphism.

If you value optimisation over elegance, try replacing say

void invoke_trivial_on_all(const std::vector<Base*>& v)
{
  for (int i=0;i<v.size();i++)
    v[i]->trivial_virtual_method();
}

with something like

void invoke_trivial_on_all(const std::vector<Base*>& v)
{
  for (int i=0;i<v.size();i++)
  {
    if (v[i]->tag==FooTag)
      static_cast<Foo*>(v[i])->Foo::trivial_virtual_method();
    else if (v[i]->tag==BarTag)
      static_cast<Bar*>(v[i])->Bar::trivial_virtual_method();
    else...
  }
}

it's not pretty, certainly not OOP (more a reversion to what you might do in good old 'C') but if the virtual methods are trivial enough you should get a function with no calls (subject to good enough compiler & optimisation options). A variant using dynamic_cast or typeid might be slightly more elegant/safe but beware that those features have their own overhead which is probably comparable to a virtual call anyway.

Where you'll most likely see an improvement from the above is if some classes methods are no-ops, and it saved you from calling them, or if the functions contain common loop-invariant code and the optimiser manages to hoist it out of the loop.