Command pattern without virtual functions (C++)

Question

For performance reasons, I am using the the Curiously Reoccuring Template Pattern to avoid virtual functions. I have lots of small commands which execute millions of times. I am trying to fit this into the Command Pattern. I want to add tons of commands to a queue, and then iterate through them executing each one by one. Each Command uses a CRTP to avoid virtual functions. The problem I am running into is that the Command pattern is typically implemented using a vector of pointers. But when the Command class is templated, it becomes hard to pass around generic Command pointers. I'm not a C++ expert, so perhaps there is an obvious way to store a vector of templated command objects? I have been trying to use something like:

boost:ptr_vector commands;
AddCommand(Command* command) {
  commands.push_back(command);
}

The problem is Command is not a type, so Command* command gives a compile error. I need to use Command<CommandType>, but that won't work because I need the queue to hold different types of commands.

Any ideas for solutions? Or are virtual functions my only option?

ADDED: The command objects are part of a monte carlo simulation algorithm. So you might have, Command be a random number from a normal distribution, where the parameters of the normal distribution are part of the class. So the command pattern fits very nicely. I have lots of calls, in a particular order, to functions that need to maintain state.

Supernatural

An example of your commands would be helpful. If you have a bunch of small command template classes, posting 1 or 2 as examples in your might help people suggest alternatives. At the very least, it will improve understanding of the question for future readers. – Catto

Could you also provide some more information about the specific scenario you are using the Command Pattern to solve? Also, explain why you think virtual functions are too slow. Have you implemented it using virtual functions and found it to be too slow? – Catto

Answer 1

The CRTP does its magic by resolving the run time type of the object at compile time so that the compiler can inline the function calls. If you have a vector of pointers to a generic type, the compiler cannot determine the specific concrete type, and will not be able to do its compile time resolution.

From just the information you have in your question, I think virtual functions are your best option. However, virtual functions are not that slow. They are slower than an in-lined function, sure, but in many cases they are plenty fast enough! Especially if your process is bounded by I/O time instead of processing time.

One of the answers to this question has some more in depth discussion of this issue. To summarize, the overhead for a virtual function call will likely be measured in nanoseconds. It is more complicated than that, but the point is that you shouldn't be afraid of virtual functions unless your function is doing something really trivial like a single assignment. You said that your commands were small, so perhaps this is the case. I'd try doing a quick prototype with virtual functions and see if that gives acceptable performance.

Catto

I have not benchmarked it, so perhaps you are correct. On the simple side a command might be as short a call to a random number generator. These are called literally millions of times in a very tight loop. Can you guess at what the virtual function overhead is? – Supernatural

Might be significant if your pseudo-random number generator is a simple linear congruential generator. Some of the more complicated ones like the Mersenne Twister will probably have enough instructions that the virtual call overhead is insignificant. – Catto

Unless you are doing something extremely trivial in the command method and all methods called by it, I would recommend using virtual methods. If you ARE doing something trivial in all/most of the command methods, then void* may be your friend. – Method

Until it bites your hand off ;-) – Method

Answer 2

Unless you are building your command queue during compile time, what you want is impossible.

Gualtiero

Answer 3

I can't tell if your command queue changes often or seldom.

If it changes seldom, compared to how often it is executed, it seems to me this could be a job for code generation.

Just print out a program to do the actions you need, compile & link a dll on the fly, and load it. That should take about a second. No classes, objects, or dispatching. And if you single-step it, you'll see almost no cycles that don't contribute materially to your answer.

Malvaceous