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.

Kingsize

Answer 1

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.

Icehouse

I believe if-statements in a template may make this mess a bit cleaner. Looks promising anyway. – Kingsize

PLEASE use static_cast<> instead of reinterpret_cast<>, the latter will give incorrect results in certain cases (on a typical implementation, an example would be if Foo or Bar has multiple base classes and Base is not first among them). – Denten

if-else chain is very likely to be slower. Branches are fairly expensive. Not only that but having to chain them means you have O(N) behavior in your time critical section... A better comparison would be a switch vs. virtual function call. Even then the speed should be similar... – Saltus

Answer 2

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.

Operational

Answer 3

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

Gonzales

I read this three separate times as 'onions' and could only imagine what your 'messy' workflow involved. – Roscoeroscommon