Run-time polymorphism design and strategies with CRTP

Question

In my work I have a lot of loops with many inner function calls; performance is critical here, and the overhead of virtual function calls is unacceptable, so I try to avoid dynamic polymorphism by using CRTP, like so:

template<class DType>
struct BType {
  DType& impl(){ return *static_cast<DType*>(this); }
  void Func(){ impl().Func(); }
};

struct MyType : public BType<MyType> {
  void Func(){ /* do work */ }
};

template<class DType>
void WorkLoop(BType<DType>* func){
  for  (int i=0;i<ni;++i){ func->func(); }
}

struct Worker {
  void DoWork(){ WorkLoop(&thing) };
 private:
  MyType thing;
};

Worker worker;
worker.DoWork();

Aside: is the correct way to actually use a CRTP class? Now I need the actual type to depend on a runtime user option, and normally dynamic polymorphism with an abstract base class / strategy pattern would be the right design, but I can't afford the virtual function calls. One way to do this seems to be with some branching:

struct Worker {
  void DoWork(){
   if (option=="optionA"){
     TypeA thing;
     WorkLoop(thing); }
   else if (option=="optionB"){
     TypeB thing;
     WorkLoop(thing); } 
  ...

But this seems like a lousy design. Passing it as a template parameter here (or using policy based design) seems like an option:

template<class T>
struct Worker {
 void DoWork(){ WorkLoop(&thing) };
 T thing;
};
if (option=="optionA"){
 Worker<TypeA> worker; worker.DoWork() } ...

but here worker only has scope in the if branch, and I'd need it to have a life the length of the program. Additionally, the relevant user options would probably specify 4+ "policies", each of those with several options (say 4), so it seems like you'd quickly have a nasty problem where a templated class could take 1 of 4*4*4*4 template combinations.

Also, moving the loop logic into the types is not an option - if it were the virtual function call overhead would be negligible and I'd use normal polymorphism. The actual control of the loops could be rather complicated and will vary at runtime.

Would this suggest that I should try and build a custom iterator and pass that as a function argument and use normal polymorphism, or would this incur similar overhead?

What is a good design for selecting classes at run-time without resorting to pointers to abstract base classes?

*"Now I need the actual type to depend on a runtime user option*" CRTP is no way to create some kind of dynamic dispatch. I think you're rather looking for a devirtualization technique. — dyp, Dec 20 '13 at 23:39
You could link the user decisions to a table of function pointers (`std::function`s) instead of using a `switch`. For the other option, if you need a longer lifetime of the Worker - that's what dynamic storage duration is for (i.e. create the Worker on the heap). — dyp, Dec 20 '13 at 23:44
Regarding std::function, [this answer](http://stackoverflow.com/questions/10757167/do-function-pointers-force-an-instruction-pipeline-to-clear) states that such a thing would prevent any inlining so that's not a viable option either. — Aurelius, Dec 21 '13 at 00:08
I don't see how that would get away from the need to specify the type for the template. — Aurelius, Dec 21 '13 at 00:58
It doesn't. It's just an alternative to using the branching / switch to *select* a Worker type / function. As you cannot afford a virtual function call (or any kind of indirect call) for every invocation of `Func` inside the loop, you need to select a specific `WorkLoop` where the called `Func` is known at compile-time. This selection can be done via a switch/branching, a function table, a factory.. — dyp, Dec 21 '13 at 01:41

score 0 · Answer 1 · answered Dec 21 '13 at 02:20

You have a classic problem of runtime-to-compile-time dispatch: "Additionally, the relevant user options would probably specify extra policies, each of those with several options". Your code has to support many combinations of options which you do not know at compile time.

It means you have to write some code for every possible combination and then dispatch user's choice onto one of the combinations. It implies you have to have some ugly and not-so-efficient piece of code where you parse user's runtime decisions and dispatch them onto predefined templates.

To keep efficiency as high as possible you want to do this dispatch at very high-level, as close to entry points as possible. On the other side, your low-level code can templatized as much as you like.

It means dispatch can have several down-steps from non-template code to mix of templates and options to fully templetized.

Usually it is achieved better with tags and policies, not CRTP, but it depends closely on your algorithms and options.

Run-time polymorphism design and strategies with CRTP

1 Answers1