Expecting jump tables to have higher performance than the alternatives sounds definitely iffy, this also reads as if the author doesn't know that switch-case statements also just use a jump table under the hood if the case-blocks are continuous.
Regarding performance, if the CPU branch predictor works well the jump indirection overhead might disappear completely, but that's still not as good as if the compiler can inline the destination function, and jump tables usually prevent that.
(a switch-case dispatcher might actually be better than a traditional function pointer jump table, because the switch-case eliminates some function entry/exit "ceremony", also see "computed goto")
I'm also dubious on the claim the switch statement is O(n). It might be in a pathological worst case, but you can pretty much bet the compiler is going to transform it into a jump table or other optimized execution (maybe a computed jump). Especially when the cases are contiguous like this...
I agree that a benchmark is warranted, or at least a comparison of the generated assembly (at different optimization levels).
Not for jumps - modern CPUs still (usually) have limit of one taken branch per cycle, or 1 to 2 untaken branches. And usually branch prediction will be the limiting factor anyway, for which a single branch is gonna be faster than many.
Function pointer jumps definitely break most chances for a compiler to optimize a function call. But then, so does a switch statement, most of the time. (Not to mention switch statements are often transformed into jump tables anyways.)
Humans tend to do a lot better jump tables in assembler, because of better choices about register usage etc. can be made, less (or no) need to spill to stack. One of the few remaining compiler weaknesses.
While compilers do turn switch statements into jump tables, in this case storing function pointers and calling them you add the additional call overhead of saving registers, setting up the stack, etc in the function prolog and epilog.
...not quite: the if-else (or switch-case) can usually inline the called function, which gets rid of the epilogue/prologue and opens up more optimization opportunities.
The call-table functions also get inlined, so the advantage is shared by both approaches, and yet the call-table produces more efficient code (no cmp/jump traps to fall into...)
See my comment here for the C code and Assembly that demonstrates this:
Nor do I see any of that kind of behavior in your linked assembly - call_table clearly contains "call *%r8", which is an indirect call to a function, definitely not inlined.
Here's a more complete test: https://godbolt.org/z/dT45aKTe1 - putting the operation in a loop (to be able to more clearly see the per-iteration cost of the operation), with -O3, both clang & gcc. While gcc decides to do comparisons (it wants at least 5 cases for a jump table apparently), clang does do the indirect jump, while neither does anything other than a call (thus suffering said register spilling & stack manipulation overhead) for the explicit function jump table.
I'm using gcc under Ubuntu/WSL on Windows, so it may be some compiler thing.
But nevertheless, thank you for taking the time to follow up on this, because it is a very interesting subject to me personally and a lot has been learned through efforts such as yours, in this thread.
Windows/WSL shouldn't change anything, gcc will have the same set of optimizations everywhere. There's just no inlining of the functions going on. There may be differences in the dispatching between different compilers & optimization levels, but none inline functions from a function list.
It'd be a pretty messy optimization, as it'd need to check whether all functions can be inlined instead of just any single one (and increase the requirements if the call otherwise would be a tail-call, which cost a decent bit less), and it'd make it impossible to predictably do an actual function jump table if the compiler sometimes just didn't.
My comparison is vis-a-vis an array of function pointers as described in the article vs a compiler-generated switch jump table with inlined bodies that the compiler will always generate with a switch statement, rather than in comparison to an if-else tree: there is no function being generated, so there is no function prolog or epilog.
A jump table made of function pointers has more runtime overhead than a switch-case jump table because the latter directly jumps into machine code snippets within the same function, and those snippets don't have the function prologues/epilogues. And function pointers are also often an "optimization barrier" where the compiler can't inline to get rid of the epilogue and prologue.
Yup, though I do think in some cases if the indexes into the function table are known a sufficiently smart compiler can inline it anyway, even if the linkage isn't static: https://godbolt.org/z/6cY7zxT9W
With four branches, maybe. With more branches, having array of tens of function pointers makes hard to tell which index maps to which function call. OTOH, that can somehow be mitigated (at least in C99) with designated initialisers.
I prefer the flexibility of computed gotos
a GCC extension that is likely the fastest
dispatch method outside of compile-time.
With computed gotos, you can have arbitrary dispatch complexity and structure, interleave
code(e.g./code1/ ;skip_label: ;label1: /code2/; goto *return_loc;) and use assembler-like tricks to
reduce fast paths(e.g. switch off code segment execution or alter control flow on the fly)
> Having 100 cases means we could potentially check 100 cases before selecting one. case statements are O(n), where n is the number of case/switch statements possible.
I was under the impression that most (all?) C compilers would optimize this use-case into a jump-table, turning this case statement usage into an O(1) operation. Or is this a C++ feature that I'm thinking of?
Quite a lot of effort goes into compiling switch statements. Jump tables and binary search are likely, as is a mixture of the two based on distribution of cases.
I haven't seen computed goto but wouldn't be surprised if some compilers have that as a third option.
As others say I'm fairly sure switch/case creates a jump table under the hood, and it also checks bounds.
Personally, I don't think a static dispatch table like this is a good example. It's really more useful where the dispatch table might be dynamic; for example if a plugin could add more maths functions.
There sure are lots of "fairly sure", "I feel" and "I think" comments in this thread.
I'm inclined to accept that Alice Goldfuss knows what theyre talking about, partly because their twitter is full of good tech stuff, and partly because I too have encountered situations where switching from a big branchy case statement to function pointers improved performance significantly.
That's because there's no right or wrong answer about this, and people on here are not just a bunch of juniors who should automatically accept as an authority anyone who blogs.
If switch/case actually does compare each and every item, as the article claims, then obviously a dispatch table is a solid choice to improve performance.
But that is just not likely the case in this example (and it does depend on a number of factors), and so it's then largely a matter of taste. This technique definitely has it's place, but this example is not the best, um, case, IMHO.
A compiler can generate a jump table. Whether it will is another matter. For a small number of cases or values with large numeric gaps you will most likely get a chain of conditionals.
IME the popular compilers (clang, gcc, msvc) are really aggressive about generating a jump table though, e.g. if you have continuous ranges with gaps between them, it will create a jump table for each range, not simply fall back to a dumb sequence of tests.
If you want to get rid of the switch-case bounds check, add a default case with __builtin_unreachable() (or on MSVC: __assume(0)), this hints the optimizer to not create a bounds check before the jump table access. At your own risk of course ;)
There is a vague reference to performance and runtime efficiency, as if function pointers will magically help. The syscalls table is said to be function pointers for performance reasons?? I feel the author does not understand this. The syscall ABI needs it because it's not a direct call, it's a generic mechanism to index into a list of functions whose implementations are completely abstract to the caller...
I guarantee you for these short examples in this article, using function pointers will slow everything down. The function pointer approach destroys locality, is bad for speculative execution, increases code size... A good optimizer would detect this and replace the indirect call with inlining. It's rare that you really need dynamic dispatch. There is a high performance cost for it.
The times when you need dynamic dispatch are those which you can't make a direct call, the callee is not known in advance. So things like generic callback mechanisms.
Modern CPUs with pipelining, branch prediction, speculative execution, caching do best with fewer jumps, small code size, predictable jump targets, sequential access. A tight loop of "jump to the address i just loaded from this 64 bit quantity" throws a total wrench in the middle of it and will have those mechanisms stall.
Imagine a sorting algorithm with a jump into a callback to compare the elements. Then compare with a simple integer compare (1-2 instructions) inlined. In the former, you are jumping all over town, to jump targets loaded from RAM (not predictable). In the latter, one very small integer compare instruction, inline with the larger algorithm.
I think you are constructing a straw man argument. The jump-table approach is just as likely to be a candidate for the optimization you claim will get in the way, as the code using if/switch statements. In fact, the compiler can see that simple call through the jump table and optimize it even better - maybe even by inlining.
The question is, how are you sure this isn't happening? The answer is, you're not - unless you examine the code your compiler is emitting, such claims are specious.
That's exactly why you're supposed to examine the compiler output, and doing this will tell you that function pointer jump tables are often not optimized that way. There's a good reason why emulators / virtual machines use switch-case or computed-goto instead of function pointer jump tables for opcode dispatching.
Even examining the compiler output is not enough: it may well be that code A is faster than code B in some hardware environments/workloads and slower in other, and the only way to know for sure which is more performant in your scenario is to actually measure them both in your actual scenario.
I did the leg-work. To me, the call_table() approach looks faster - no cmp/jumps to pass through every time, and simpler code for debugging.
--- C-code "exer.c" file containing the different techniques:
#include <stdio.h>
int add(int first, int second);
int sub(int first, int second);
int mult(int first, int second);
int divide(int first, int second);
typedef int math_function(int first, int second);
math_function *my_array[4] = {
add,
sub,
mult,
divide
};
int add(int first, int second){
return first + second;
}
int sub(int first, int second){
return first - second;
}
int mult(int first, int second){
return first * second;
}
int divide(int first, int second){
return first / second;
}
int inline_with_switch() {
int first, second, choice, result;
first = 2;
second = 3;
choice = 1;
switch(choice) {
case 0 :
result = first + second;
break;
case 1 :
result = first - second;
break;
case 2 :
result = first * second;
break;
case 3 :
result = first / second;
break;
}
printf("Result is %d\n", result);
return 0;
}
int functions_with_switch() {
int first, second, choice, result;
first = 2;
second = 3;
choice = 1;
switch(choice) {
case 0 :
result = add(first, second);
break;
case 1 :
result = sub(first, second);
break;
case 2 :
result = mult(first, second);
break;
case 3 :
result = divide(first, second);
break;
}
printf("Result is %d\n", result);
return 0;
}
int call_table() {
int first, second, choice, result;
first = 2;
second = 3;
choice = 1;
math_function *my_array[4] = {
add,
sub,
mult,
divide
};
result = my_array[choice](first, second);
printf("Result is %d\n", result);
return 0;
}
void main(int argc, char *argv[])
{
call_table();
inline_with_switch();
functions_with_switch();
}
--- Assembly Code (produced with gcc -S exer.c -o exer.s):
Well, which is actually faster? Also, try benchmarking while there is a lot of context switching goes on in background (I vaguely recall a story about how some non-optimal looking code actually fared better when the processor constantly kept flushing its caches/buffers but can't remember the exact details).
I measured it with a simple modification of the above program to call each method() 5,000,000 times and sample the time taken.
With minimal optimizations (-O), the call_table is moderately slower. This is probably because with gcc's default optimizer, it doesn't recognize the inline-ability of call_table(), whereas it does with the other method()'s.
With all optimizations on (-O3): all methods are, performance-wise, equivalent. The call_table() gets inlined, like the competition, and it performs just as well.
But thats the actual point: the call_table() method is as equally qualified for optimization as other methods - and in the end, produces the same performance. So really, its a matter of style and readability - which the call_table() wins over gigantic switch() statements, easily.
In a switch you see the index as a number in the case statement, above a small number, finding the value of choice is going to be unreadable, no?
You have to count the position of the function you want?
Small number? I think you mean properly documented enum. ;)
But yeah, point taken. Its a style thing. I've just gotten allergic to wading through multiple-1000 lines of switch/case statements while trying to keep the state machine 'intentions' in my head, comparing with 'actuality' in the debugger.
I much prefer the smaller lines-of-code approach, even if it has been pointed out to me now by others in this thread that switch() is faster - maintenance is a performance index, also... especially when going back to code that was written some time >1year ago, etc.
Predicting through jump tables is no small part of the purpose of indirect branch prediction. This impacts two critical abilities here: 1. Good local decisions from the compiler optimizer; 2. Good execution by superscalar microarchitectures.
This discussion runs the risk of being as dated as advice to write macros rather than functions due to insufficiently aggressive inclining. However, as it stands today anecdotally, I've never seen compiler optimization inline through a indirect call in a jump table, and I have seen numerous examples of inlining through switch. I've also seen switch compile down to computed goto. Santana in his analysis of Indirect Branch Speculation indicates that the execution of these branches is less refined relative to direct branches.
> In fact, the compiler can see that simple call through the jump table and optimize it even better - maybe even by inlining.
Sure, if the table is `static const`. Otherwise the compiler generates code to load the table address, add the offset, retrieve the address and then jump to it.
If the table is defined in the current translation unit[1], or if it is visible but not const[2], or if it is visible but not static[3][4], the compiler cannot safely inline anything.
If the table is:
a) Defined in the current function
b) Does not escape the scope of the current function
c) Is qualified with static
d) Is qualified with const
Then sure, the compiler can figure out the best optimisation. Luckily, for benchmark purposes all of the above will be true so your benchmark program will show a performance benefit to the jump table.
Real programs with jump tables are never able to satisfy all those conditions.
[1] If defined elsewhere, the compiler doesn't know the contents of the table and so has generate code to look it up every time.
[2] If it isn't const, the compiler cannot assume that the entries in the table don't change, and thus has generate code to look it up every time.
[3] If the table is visible outside of the current scope or translation unit, the compiler cannot assume that the entries don't change, and once again has to generate code to perform the lookup every time.
[4] If the table is defined in the current function but not static, the compiler will have to generate code to populate that table every single time the function is entered.
> A good optimizer would detect this and replace the indirect call with inlining
And it seems like it's true for your experiment. These days, this is a common optimization, provided the optimizer can figure it out. A link time optimizer can even do it between complication units. I remember when it wasn't possible or common.
Uh, this is a few years old, and perhaps the author was learning as they went. Still, I think this passage is a bit too much:
Quick refresher: a pointer is a location in memory aka a memory address. That memory address can contain anything: an integer, a float, the middle of a string. It can also store the name of a function, also known as its label. A function’s name is its address in memory.
A pointer is not a location in memory. A pointer is a type of value, that represents a location in memory. It certainly cannot hold the name of a function, since names are not locations (also, in C there are no names at run-time typically).
It can hold the location of a function, which is represented symbolically in C by its name. These names are not called labels in C, that is a common term in assembly though.
If you come at it from an assembly perspective, the explanation makes a lot of sense IMHO. But it could use a qualifier that the "name" is just a number and not the actual name as in the source code.
> case statements are O(n), where n is the number of case/switch statements possible.
What now? Not even close. Any modern or even semi-modern (2005-vintage) compiler will compile large switches into a jump table (O(1)) and medium ones into a tree of branches, giving O(log n)
51 comments
[ 3.3 ms ] story [ 108 ms ] threadRegarding performance, if the CPU branch predictor works well the jump indirection overhead might disappear completely, but that's still not as good as if the compiler can inline the destination function, and jump tables usually prevent that.
(a switch-case dispatcher might actually be better than a traditional function pointer jump table, because the switch-case eliminates some function entry/exit "ceremony", also see "computed goto")
I agree that a benchmark is warranted, or at least a comparison of the generated assembly (at different optimization levels).
Humans tend to do a lot better jump tables in assembler, because of better choices about register usage etc. can be made, less (or no) need to spill to stack. One of the few remaining compiler weaknesses.
And, if this is the case, why then do compilers turn switch statements into function tables?
So I still don't see your claim as being accurate.
See my comment here for the C code and Assembly that demonstrates this:
https://news.ycombinator.com/item?id=31834241
Nor do I see any of that kind of behavior in your linked assembly - call_table clearly contains "call *%r8", which is an indirect call to a function, definitely not inlined.
Here's a more complete test: https://godbolt.org/z/dT45aKTe1 - putting the operation in a loop (to be able to more clearly see the per-iteration cost of the operation), with -O3, both clang & gcc. While gcc decides to do comparisons (it wants at least 5 cases for a jump table apparently), clang does do the indirect jump, while neither does anything other than a call (thus suffering said register spilling & stack manipulation overhead) for the explicit function jump table.
But nevertheless, thank you for taking the time to follow up on this, because it is a very interesting subject to me personally and a lot has been learned through efforts such as yours, in this thread.
It'd be a pretty messy optimization, as it'd need to check whether all functions can be inlined instead of just any single one (and increase the requirements if the call otherwise would be a tail-call, which cost a decent bit less), and it'd make it impossible to predictably do an actual function jump table if the compiler sometimes just didn't.
For performance, this is not necessary because the compiler can optimize long switch-case flow into dispatch tables: https://godbolt.org/z/7WxEfc6YM
With four branches, maybe. With more branches, having array of tens of function pointers makes hard to tell which index maps to which function call. OTOH, that can somehow be mitigated (at least in C99) with designated initialisers.
I was under the impression that most (all?) C compilers would optimize this use-case into a jump-table, turning this case statement usage into an O(1) operation. Or is this a C++ feature that I'm thinking of?
My opinion is the big advantage of dispatch tables in C is decoupling modules from each other.
Tip: Taking things further: variadic function pointers.
I haven't seen computed goto but wouldn't be surprised if some compilers have that as a third option.
Personally, I don't think a static dispatch table like this is a good example. It's really more useful where the dispatch table might be dynamic; for example if a plugin could add more maths functions.
I'm inclined to accept that Alice Goldfuss knows what theyre talking about, partly because their twitter is full of good tech stuff, and partly because I too have encountered situations where switching from a big branchy case statement to function pointers improved performance significantly.
If switch/case actually does compare each and every item, as the article claims, then obviously a dispatch table is a solid choice to improve performance.
But that is just not likely the case in this example (and it does depend on a number of factors), and so it's then largely a matter of taste. This technique definitely has it's place, but this example is not the best, um, case, IMHO.
If you want to get rid of the switch-case bounds check, add a default case with __builtin_unreachable() (or on MSVC: __assume(0)), this hints the optimizer to not create a bounds check before the jump table access. At your own risk of course ;)
I guarantee you for these short examples in this article, using function pointers will slow everything down. The function pointer approach destroys locality, is bad for speculative execution, increases code size... A good optimizer would detect this and replace the indirect call with inlining. It's rare that you really need dynamic dispatch. There is a high performance cost for it.
The times when you need dynamic dispatch are those which you can't make a direct call, the callee is not known in advance. So things like generic callback mechanisms.
Imagine a sorting algorithm with a jump into a callback to compare the elements. Then compare with a simple integer compare (1-2 instructions) inlined. In the former, you are jumping all over town, to jump targets loaded from RAM (not predictable). In the latter, one very small integer compare instruction, inline with the larger algorithm.
See also: qsort in c vs std::sort in c++
The question is, how are you sure this isn't happening? The answer is, you're not - unless you examine the code your compiler is emitting, such claims are specious.
--- C-code "exer.c" file containing the different techniques:
--- Assembly Code (produced with gcc -S exer.c -o exer.s):With minimal optimizations (-O), the call_table is moderately slower. This is probably because with gcc's default optimizer, it doesn't recognize the inline-ability of call_table(), whereas it does with the other method()'s.
With all optimizations on (-O3): all methods are, performance-wise, equivalent. The call_table() gets inlined, like the competition, and it performs just as well.
But thats the actual point: the call_table() method is as equally qualified for optimization as other methods - and in the end, produces the same performance. So really, its a matter of style and readability - which the call_table() wins over gigantic switch() statements, easily.
But yeah, point taken. Its a style thing. I've just gotten allergic to wading through multiple-1000 lines of switch/case statements while trying to keep the state machine 'intentions' in my head, comparing with 'actuality' in the debugger.
I much prefer the smaller lines-of-code approach, even if it has been pointed out to me now by others in this thread that switch() is faster - maintenance is a performance index, also... especially when going back to code that was written some time >1year ago, etc.
This discussion runs the risk of being as dated as advice to write macros rather than functions due to insufficiently aggressive inclining. However, as it stands today anecdotally, I've never seen compiler optimization inline through a indirect call in a jump table, and I have seen numerous examples of inlining through switch. I've also seen switch compile down to computed goto. Santana in his analysis of Indirect Branch Speculation indicates that the execution of these branches is less refined relative to direct branches.
Switch statements are a pretty good default.
Sure, if the table is `static const`. Otherwise the compiler generates code to load the table address, add the offset, retrieve the address and then jump to it.
If the table is defined in the current translation unit[1], or if it is visible but not const[2], or if it is visible but not static[3][4], the compiler cannot safely inline anything.
If the table is: a) Defined in the current function b) Does not escape the scope of the current function c) Is qualified with static d) Is qualified with const
Then sure, the compiler can figure out the best optimisation. Luckily, for benchmark purposes all of the above will be true so your benchmark program will show a performance benefit to the jump table.
Real programs with jump tables are never able to satisfy all those conditions.
[1] If defined elsewhere, the compiler doesn't know the contents of the table and so has generate code to look it up every time.
[2] If it isn't const, the compiler cannot assume that the entries in the table don't change, and thus has generate code to look it up every time.
[3] If the table is visible outside of the current scope or translation unit, the compiler cannot assume that the entries don't change, and once again has to generate code to perform the lookup every time.
[4] If the table is defined in the current function but not static, the compiler will have to generate code to populate that table every single time the function is entered.
> A good optimizer would detect this and replace the indirect call with inlining
And it seems like it's true for your experiment. These days, this is a common optimization, provided the optimizer can figure it out. A link time optimizer can even do it between complication units. I remember when it wasn't possible or common.
Quick refresher: a pointer is a location in memory aka a memory address. That memory address can contain anything: an integer, a float, the middle of a string. It can also store the name of a function, also known as its label. A function’s name is its address in memory.
A pointer is not a location in memory. A pointer is a type of value, that represents a location in memory. It certainly cannot hold the name of a function, since names are not locations (also, in C there are no names at run-time typically).
It can hold the location of a function, which is represented symbolically in C by its name. These names are not called labels in C, that is a common term in assembly though.
What now? Not even close. Any modern or even semi-modern (2005-vintage) compiler will compile large switches into a jump table (O(1)) and medium ones into a tree of branches, giving O(log n)