Earlier quoted context omitted.
Why? And, if this is the case, why then do compilers turn switch statements into function tables?
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.
Function Dispatch Tables in C (2019)
31–40 of 52 posts
Re: Function Dispatch Tables in C (2019)
#32For readability, this is reasonable. There may be a cost that it weakens some static analyzers, but I don't program in C enough to be sure. 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.
Re: Function Dispatch Tables in C (2019)
#33As 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.
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.
Re: Function Dispatch Tables in C (2019)
#34Earlier quoted context omitted.
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 yo…
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.
Re: Function Dispatch Tables in C (2019)
#35Earlier quoted context omitted.
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 w…
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 yo…
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.
Re: Function Dispatch Tables in C (2019)
#36Earlier quoted context omitted.
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.
--- C-code "exer.c" file containing the different techniques:
#include
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): .file "exer.c"
.text
.def printf; .scl 3; .type 32; .endef
.seh_proc printf
printf:
pushq %rbp
.seh_pushreg %rbp
pushq %rbx
.seh_pushreg %rbx
subq $56, %rsp
.seh_stackalloc 56
leaq 48(%rsp), %rbp
.seh_setframe %rbp, 48
.seh_endprologue
movq %rcx, 32(%rbp)
movq %rdx, 40(%rbp)
movq %r8, 48(%rbp)
movq %r9, 56(%rbp)
leaq 40(%rbp), %rax
movq %rax, -16(%rbp)
movq -16(%rbp), %rbx
movl $1, %ecx
movq __imp___acrt_iob_func(%rip), %rax
call *%rax
movq %rbx, %r8
movq 32(%rbp), %rdx
movq %rax, %rcx
call __mingw_vfprintf
movl %eax, -4(%rbp)
movl -4(%rbp), %eax
addq $56, %rsp
popq %rbx
popq %rbp
ret
.seh_endproc
.globl my_array
.data
.align 32
my_array:
.quad add
.quad sub
.quad mult
.quad divide
.text
.globl add
.def add; .scl 2; .type 32; .endef
.seh_proc add
add:
pushq %rbp
.seh_pushreg %rbp
movq %rsp, %rbp
.seh_setframe %rbp, 0
.seh_endprologue
movl %ecx, 16(%rbp)
movl %edx, 24(%rbp)
movl 16(%rbp), %edx
movl 24(%rbp), %eax
addl %edx, %eax
popq %rbp
ret
.seh_endproc
.globl sub
.def sub; .scl 2; .type 32; .endef
.seh_proc sub
sub:
pushq %rbp
.seh_pushreg %rbp
movq %rsp, %rbp
.seh_setframe %rbp, 0
.seh_endprologue
movl %ecx, 16(%rbp)
movl %edx, 24(%rbp)
movl 16(%rbp), %eax
subl 24(%rbp), %eax
popq %rbp
ret
.seh_endproc
.globl mult
.def mult; .scl 2; .type 32; .endef
.seh_proc mult
mult:
pushq %rbp
.seh_pushreg %rbp
movq %rsp, %rbp
.seh_setframe %rbp, 0
.seh_endprologue
movl %ecx, 16(%rbp)
movl %edx, 24(%rbp)
movl 16(%rbp), %eax
imull 24(%rbp), %eax
popq %rbp
ret
.seh_endproc
.globl divide
.def divide; .scl 2; .type 32; .endef
.seh_proc divide
divide:
pushq %rbp
.seh_pushreg %rbp
movq %rsp, %rbp
.seh_setframe %rbp, 0
.seh_endprologue
movl %ecx, 16(%rbp)
movl %edx, 24(%rbp)
movl 16(%rbp), %eax
cltd
idivl 24(%rbp)
popq %rbp
ret
.seh_endproc
.section .rdata,"dr"
.LC0:
.ascii "Result is %d\12\0"
.text
.globl inline_with_switch
.def inline_with_switch; .scl 2; .type 32; .endef
.seh_proc inline_with_switch
inline_with_switch: Re: Function Dispatch Tables in C (2019)
#37Earlier quoted context omitted.
That call overhead is there in then code using "if-else" logic to determine which functions to call, also, though. So I still don't see your claim as being accurate.
...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.
See my comment here for the C code and Assembly that demonstrates this:
Re: Function Dispatch Tables in C (2019)
#38Earlier quoted context omitted.
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 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]…
Re: Function Dispatch Tables in C (2019)
#39Quick 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.
Re: Function Dispatch Tables in C (2019)
#40Earlier quoted context omitted.
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 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]…
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).
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.