vftable performance penalty vs. switch statement

Question

C++ question here. I have a system where I'm going to have hundreds of mini-subclasses of a given superclass. They all will have a "foo" method that does something. Or... I'm going to have one class with an integer called "type" and use a giant switch statement to decide what to do when I foo.

Performance is a huge consideration here. Extremely important.

The question is, what are the performance benefits/penalties of using a switch statement vs. letting C++ do it via the vftable? If I have it as a switch statement, I can put the commonly occuring foo's up at the top of the switch statement and the less common ones at the bottom, hopefully shortcutting the comparison. Trying to get an effect like this with the vftable is bound to be compiler dependent even if I can figure out how to do it...

On the other hand, my code would be a lot easier to deal with without these ugly switch statements.

Answer 1

There's been some research on this topic in the field of virtual machine design. Generally, a switch statement is going to be faster, a lot of virtual machines use switch semantics as opposed to virtual lookup. Theoretically, one would assume that a virtual table - being a constant time algorithm - will be faster, but we have to examine how the hardware sees a virtual table.

A switch statement is easier for the compiler to inline. This is a huge consideration, the actual act of calling a virtual function is minimal, however, pushing and popping the entire stack frame is necessary because the compiler has no idea which function will be called at run-time.

Branch prediction and hardware prefetch should be easier on a switch statement, although modern architectures are getting better at predicting virtual calls.

A lot of code that uses virtual dispatch requires the use of heap based allocation schemes. Dynamic memory allocation is a bottleneck in a lot C++ applications.

Answer 2

If I have it as a switch statement, I can put the commonly occuring foo's up at the top of the switch statement and the less common ones at the bottom, hopefully shortcutting the comparison.

A switch statement is generally compiled to a jump table rather than a block of if-else conditionals as your question implies. In practice, the virtual table and the switch jump table should have similar performance, though test if you're really concerned.