if, switch and function pointers speed comparison

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.

Yet again I was too slow :-) +1

MartinStettner 2010-02-19 02:25:12

How do you even put function pointers into the same class as branching? They are completely unrelated. You still have to have some sort of logic branching to assign the function pointer...

2010-02-19 02:27:40

@STingRaySC:A typical case is an array of pointers to functions, where the same value you would have used in the switch statement is instead used to index into the array.

Jerry Coffin 2010-02-19 02:31:20

Thanks, Jerry :) So, you're saying that there is no point in testing this? My first interpreter was done with ifs, the second one was ifs in C# with strings, and third was in C++ again, but with function pointers. I didn't see as much improvement as I would expect with pointers, but the languages are different, so I'm not sure.

2010-02-19 02:52:49

Note that a `switch` with (n) `case…break` basic blocks can be translated into (n) basic blocks reachable from no more than log(n) branches, whereas a chain of `if…else if` takes up to (n) branches unless the compiler is very clever. OP noted that the `switch` is faster than the `else if`. @STing: Function calls are a class of branch instructions, period, and you can declare a static array of function pointers (likely in OP's scenario) to assign them without ever branching, or possibly even invoking user-space code at all.

Potatoswatter 2010-02-19 02:56:36

@hilikus: I'm not saying there's no point in testing. I'm saying you shouldn't expect to *automatically* make huge gains by doing the same thing in slightly different ways.

Jerry Coffin 2010-02-19 02:57:50

@STing: http://en.wikipedia.org/wiki/Branch_instruction

Potatoswatter 2010-02-19 03:52:13

@STing: inside the processor, the next instruction is found by incrementing the instruction pointer unless the current instruction is a branch. If you ignore unconditional branches, you could code an endless loop with "no branches." Unconditional or not, a branch jumps to the beginning of a basic block. In PowerPC, some unconditional branches (including all indirect function calls) are actually encoded as conditional branches with "condition always TRUE"!

Potatoswatter 2010-02-19 04:21:17

ansaurus

tags:

views:

answers:

if, switch and function pointers speed comparison

related questions