which is faster? switch statement or function pointers

Most compilers are very good at optimizing switch statements, as long as the enumerants are all contiguous.

Also, moved to General Programming.

As mentioned, most compilers will use a jump table (similar to function pointers) to evaluate switch statements - with some constraints. In any case you can be fairly sure that a switch statement is the most efficient way to do a "switch-like" operation.

thanks, sorry i got the wrong forum.

[hijack]
I don't understand the 'switch or function pointer' questions? Only because the code that I have seen use a if/else or switch to have the function pointer choose the correct function to point at.

I guess my question is how do you use a 'switch or function pointer'? Shouldn't it be a 'switch to different functions' or a 'switch using function pointers'?
[/hijack]

was just thinking of finding the pointers at the beginning and placing them with arguments in an array.

[funcPtr] [arg1], [arg2]

I thought this would be quicker because you could jump straight to the correct function instead of using a function index and going through a switch statement to decide what to do.

EDIT: would there be a limit on how many cases in a switch statement before it becomes less efficient than function pointers?

No limit, though 'a big switch statement' is almost universally abhorrent design-wise.

"Software Optimization Guide for AMD64 Processors" states that switch statements with contiguous expressions is usually faster than a switch statement with noncontiguous expressions. The noncontiguous case is better coded with if-else statements. The guide also contains a lot of optimizations, both for C/C++ and assembly language programmers. Here's a link:

Software Optimization Guide for AMD64 Processors

thanks that helps a lot

This really depends...

The most important question is "How many branch mispredictions will I get with either methodology?" .. the cost (in cycles) of a branch misprediction is always at least the number of stages in the instruction pipeline .. so about a dozen on most machines and (aha) 20 or so on those ungodly P4's with their insane and unforgiving pipeline. Branch mispredictions dominate the runtime of this sort of methodology (blowing away all other considerations such as code size, alignment, the 4/1/1 decode rule, and so forth)


I always consider refactoring the code so that the switch methodology can happen at a higher level (yes, that usualy means code duplication) because that leads to zero chance of a branch mispredictions due to this logic while within the inner loop since its simply not there.

If this switch is not within an inner loop then you are over-optimizing.

You can't over-optimize. What you can do, however, is optimize prematurely. He's already told us this is in a performance critical loop, but I still wouldn't worry about the difference between a table of function pointers and a big switch statement. I'd use the function pointers because the method is more elegant and means much simpler code. If it turned out to be too slow, I'd look for more effective optimizations than this little micro optimization.

This talk about the Parrot VM has some description of various ways to do an interpreter: indirect function calls (via a table of opcode->fptr), direct function calls (via inserting the fptrs into the bytecode stream), switch statement, JIT (and pseudo-JIT that just generates code which calls a function per op, so the CPU can do some branch prediction on those function calls), and computed goto (which is a GCC extension, and is basically like a function-pointer call minus the overhead of entering a function because it just does a jump instead). Apparently the latter usually gives the best performance of the interpreters, though it's not portable and C compilers' optimisers hate it. JIT is obviously the fastest by far, but it's a bit of a pain to write.

(Parrot just implements all of those methods, and lets you choose whichever you fancy.)

Giant switch statements are, yes, probably the more efficient strategy. However, they're very poor when it comes to readability for any situation where efficiency would matter (i.e. very large switch tables). Unfortunately, the syntax behind a function pointer isn't very readable either.

My solution would be, if you're using C++ or some scripting language with first class functions, is polymorphism. That is, if the switch you would have used happens to be really large, and you're not uncomfortable with the overhead of an indirect jump in the generated code.

Quote:

Original post by Inmate2993 Giant switch statements are, yes, probably the more efficient strategy. However, they're very poor when it comes to readability for any situation where efficiency would matter (i.e. very large switch tables). Unfortunately, the syntax behind a function pointer isn't very readable either.

I actually don't find giant switch statements unreadable, but that's probably because most of the ones I've seen were the main focus of the function at hand and quickly offload any extened calculations to other functions.

As for function pointers, typedef is your friend. The typedef syntax for a function is relatively readable and, once you have the typedef, the rest becomes as readable as anything.

Quote:

My solution would be, if you're using C++ or some scripting language with first class functions, is polymorphism. That is, if the switch you would have used happens to be really large, and you're not uncomfortable with the overhead of an indirect jump in the generated code.

Polymorphism doesn't eliminate the switch statement because you still need to "switch" on the class or functions at some point (and is essentially syntactic sugar for the function pointer idea); the benefit is that in some cases it's easier to consolidate the switch to just one place.

Quote:

Original post by Way Walker Polymorphism doesn't eliminate the switch statement because you still need to "switch" on the class or functions at some point

Umm, no? Why would you need to? Well, you might have to for *creation* (see Abstract Factory design pattern), but that's about it. And even in that case, we can construct something more intelligent than a switch statement...

Quote:

(and is essentially syntactic sugar for the function pointer idea);

Um, sort of; but your "function pointer" (assuming a vtable based implementation) is now embedded within an object, instead of being selected out of a switch.

Anyway. When there are many, discontinuous (or perhaps, even, "not easily represented with integers) cases, another strategy is to build an associative array (in C++, this usually means std::map or similar) from whatever natural "key type" to whatever natural "value type" (either a function pointer type, or an object as in the abstract factory).

For example, if we are parsing operator tokens out of the script file, we might have polymorphic classes that represent the addition, multiplication etc. operators, and then build a map from std::string to the base class, and register mapping['+'] = AdditionOperator(), etc. Then, to create and use an operator, you just do something like

typedef std::map<std::string, Operator> Registry;Registry::iterator it = mapping.find(symbol);if (it == mapping.end()) { cerr << "Syntax error\n"; }else { result = (*it)(lhs, rhs); } // where Operator defines virtual operator()(lhs_type, rhs_type)

Actually, I once saw a method in a 6502 emulator, which was pretty cool. They wrote the 50 something opcodes as functions, and 8 functions for addressing modes, and set up a struct array for the 255 commands using the combinations of opcode function pointer and addressing mode function pointer. Obviously, it took two function calls, but the amount of code was pretty minimal and it was very readable.

It's a bit of an alternative idea. Being able to manage the code, for future modification, might be worth more than the stream-lined performance.

Quote:

Original post by Zahlman Quote: Original post by Way Walker Polymorphism doesn't eliminate the switch statement because you still need to "switch" on the class or functions at some point Umm, no? Why would you need to? Well, you might have to for *creation* (see Abstract Factory design pattern), but that's about it. And even in that case, we can construct something more intelligent than a switch statement... Quote: (and is essentially syntactic sugar for the function pointer idea); Um, sort of; but your "function pointer" (assuming a vtable based implementation) is now embedded within an object, instead of being selected out of a switch.

In both cases, that's more or less what I was getting at.

Consider these two examples:

void main()
{
int s;
for (;;) {
s = (rand()*2)/RAND_MAX;
switch ( s ) {
case 0: myfuncA(); break;
case 1: myfuncB(); break;
}; // close switch
}
}

void main()
{
int s, c;
for (;;) {
c = getkey();
if ( c == '0' || c == '1' ) s = atoi (c);
switch ( s ) {
case 0: myfuncA(); break;
case 1: myfuncB(); break;
}; // close switch
}
}

Which is faster? In the above examples (assume getkey, rand and atoi take 0 time), both will run at same rate. They are both switches. Function pointers could make the second example much faster, but not the first:

void main()
{
void (*func) void;
int c;
for (;;) {
c = getkey();
if ( c == '0' || c == '1' ) {
switch ( c ) {
case 0: func = &myfuncA break;
case 1: func = &myfuncB break;
}; // close switch
} // close if
func ();
}
}

It all depends on how frequently the call is made, versus how frequently it is switched. If you switch on every call - ie. calls are completely random, then switch is best. If its not completely random and you can store a function pointer some of the time then this will be faster: because a function call is just a jump on address, while even an optimized switch must do at least a compare and two jumps: one to the function and one to exit the bottom of the switch. So, if your switching on functions, and the switch is semi-predictable, and you need every bit of performance, use func pointers.