if, switch and function pointers speed comparison

Question

I'm building a small interpreter so I wanted to test how fast ifs, switch and pointers to functions are, compared to each other. if with 19 else ifs is slightly faster than switch with 20 cases, and function pointers (an array of 20 function pointers) is way slower than the previous two...

I expected the results to be completely opposite, can anyone please explain?

Answer 1

On a modern processor, a lot of this comes down to branch prediction. While a switch statement can be implemented as a jump table that takes about the same length of time to execute any branch of the code, it's also generally pretty unpredictable -- literally; a branch predictor will often do a fairly poor job of predicting which branch gets taken, which means there's a very good chance of a pipeline bubble (typically around 15 wasted cycles or so).

An if-statement may do more comparisons, but most of the branches are probably taken the same way nearly every time, so the branch predictor can predict their results much more accurately.

Pointers to functions can also be fairly unpredictable. Worse, until fairly recently, most processors pretty much didn't even try. Only fairly recently did the add enough to most BTB (Branch Target Buffer) implementations that they can really even make a serious attempt at predicting the target of a branch via a pointer. On older processors, pointers to functions often do quite poorly in speed comparisons.