Performance of array of functions over if and switch statements

Question

I am writing a very performance critical part of the code and I had this crazy idea about substituting case statements (or if statements) with array of function pointers.

Let me demonstrate; here goes the normal version:

while(statement)
{
    /* 'option' changes on every iteration */

    switch(option)
    {
        case 0: /* simple task */ break;
        case 1: /* simple task */ break;
        case 2: /* simple task */ break;
        case 3: /* simple task */ break;
    }
}

And here is the "callback function" version:

void task0(void) {
    /* simple task */
}

void task1(void) {
    /* simple task */
}

void task2(void) {
    /* simple task */
}

void task3(void) {
    /* simple task */
}

void (*task[4]) (void);

task[0] = task0;
task[1] = task1;
task[2] = task2;
task[3] = task3;

while(statement)
{
    /* 'option' changes on every iteration */

    /* and now we call the function with 'case' number */
    (*task[option]) ();
}

So which version will be faster? Is the overhead of the function call eliminating speed benefit over normal switch (or if) statement?

Ofcourse the latter version is not so readable but I am looking for all the speed I can get.

I am about to benchmark this when I get things set up but if someone has an answer already, I wont bother.

Solution 1

I think at the end of the day your switch statements will be the fastest, because function pointers have the "overhead" of the lookup of the function and the function call itself. A switch is just a jmp table straight. It of course depends on different things which only testing can give you an answer to. That's my two cent worth.

Solution 2

The switch statement should be compiled into a branch table, which is essentially the same thing as your array of functions, if your compiler has at least basic optimization capability.

Solution 3

Which version will be faster depends. The naive implementation of switch is a huge if ... else if ... else if ... construction meaning it takes on average O(n) time to execute where n is the number of cases. Your jump table is O(1) so the more different cases there are and the more the later cases are used, the more likely the jump table is to be better. For a small number of cases or for switches where the first case is chosen more frequently than others, the naive implementation is better. The matter is complicated by the fact that the compiler may choose to use a jump table even when you have written a switch if it thinks that will be faster.

The only way to know which you should choose is to performance test your code.

Solution 4

First, I would randomly-pause it a few times, to make certain enough time is spent in this dispatching to even bother optimizing it.

Second, if it is, since each branch spends very few cycles, you want a jump table to get to the desired branch. The reason switch statements exist is to suggest to the compiler that it can generate one if the switch values are compact.

How long is the list of switch values? If it's short, the if-ladder could still be faster, especially if you put the most frequently used codes at the top. An alternative to an if-ladder (that I've never actually seen anyone use) is an if-tree, the code equivalent of a binary tree.

You probably don't want an array of function pointers. Yes, it's an array reference to get the function pointer, but there's several instructions' overhead in calling a function, and it sounds like that could overwhelm the small amount being done inside each function.

In any case, looking at the assembly language, or single-stepping at the instruction level, will give you a good idea how efficient it's being.

Solution 5

A good compiler will compile a switch with cases in a small numerical range as a single conditional to see if the value is in that range (which can sometimes be optimized out) followed by a jumptable jump. This will almost surely be faster than a function call (direct or indirect) because:

1. A jump is a lot less expensive than a call (which must save call-clobbered registers, adjust the stack, etc.).
2. The code in the switch statement cases can make use of expression values already cached in registers in the caller.

It's possible that an extremely advanced compiler could determine that the call-via-function pointer only refers to one of a small set of static-linkage functions, and thereby optimize things heavily, maybe even eliminating the calls and replacing them by jumps. But I wouldn't count on it.

View more solutions

Comments

[Erik]

My guess is the switch will be faster - no function calls, less cache misses. But, test it, cause as always it depends.

[OptimizingBastard]

I think the biggest problem with case & if statements are that it takes longer to find the correct case if the desired action is at the end of the list.

[Sunilsingh]

@OptimizingBastard - check out en.wikipedia.org/wiki/… to see that the compiler doesn't always generate a long sequence of if/elses. The best advice is to test and measure both methods.

[Anthony]

I think the biggest advantage to the switch-case use is its easier to read. I'm still amazed at the amount of people that have issues with function pointers, non-the-less an array of function pointers. Readability should always be considered.

[OptimizingBastard]

Well I think GCC 4.x should handle it. Pretty clever trick I must say. I found out that -Os flag generates the fastest code with switch statements but -O3 flag generates even faster code with if-else statements.

[conradkleinespel]

How would it take O(n) on average with n being the number of cases. Wouldn't it be something like O(n/2) ? Unless you only ever use the n-th case...

[JeremyP]

@conradk In "big O" notation O(n * k) where k is a constant is the same as O(n)

[conradkleinespel]

Oh, OK. Thanks @JeremyP.