5 ms·

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 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 you examine the code your compiler is emitting, such claims are specious.

flohofwoe 4y ago
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.
- Joker_vD 4y ago
  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.
  - boffinAudio 4y ago
    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): .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: <------- inline_with_switch() pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $48, %rsp .seh_stackalloc 48 .seh_endprologue movl $2, -8(%rbp) movl $3, -12(%rbp) movl $1, -16(%rbp) cmpl $3, -16(%rbp) je .L12 cmpl $3, -16(%rbp) jg .L13 cmpl $2, -16(%rbp) je .L14 cmpl $2, -16(%rbp) jg .L13 cmpl $0, -16(%rbp) je .L15 cmpl $1, -16(%rbp) je .L16 jmp .L13 .L15: movl -8(%rbp), %edx movl -12(%rbp), %eax addl %edx, %eax movl %eax, -4(%rbp) jmp .L13 .L16: movl -8(%rbp), %eax subl -12(%rbp), %eax movl %eax, -4(%rbp) jmp .L13 .L14: movl -8(%rbp), %eax imull -12(%rbp), %eax movl %eax, -4(%rbp) jmp .L13 .L12: movl -8(%rbp), %eax cltd idivl -12(%rbp) movl %eax, -4(%rbp) nop .L13: movl -4(%rbp), %eax movl %eax, %edx leaq .LC0(%rip), %rax movq %rax, %rcx call printf movl $0, %eax addq $48, %rsp popq %rbp ret .seh_endproc .globl functions_with_switch .def functions_with_switch; .scl 2; .type 32; .endef .seh_proc functions_with_switch functions_with_switch: <------- functions_with_switch() pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $48, %rsp .seh_stackalloc 48 .seh_endprologue movl $2, -8(%rbp) movl $3, -12(%rbp) movl $1, -16(%rbp) cmpl $3, -16(%rbp) je .L19 cmpl $3, -16(%rbp) jg .L20 cmpl $2, -16(%rbp) je .L21 cmpl $2, -16(%rbp) jg .L20 cmpl $0, -16(%rbp) je .L22 cmpl $1, -16(%rbp) je .L23 jmp .L20 .L22: movl -12(%rbp), %edx movl -8(%rbp), %eax movl %eax, %ecx call add movl %eax, -4(%rbp) jmp .L20 .L23: movl -12(%rbp), %edx movl -8(%rbp), %eax movl %eax, %ecx call sub movl %eax, -4(%rbp) jmp .L20 .L21: movl -12(%rbp), %edx movl -8(%rbp), %eax movl %eax, %ecx call mult movl %eax, -4(%rbp) jmp .L20 .L19: movl -12(%rbp), %edx movl -8(%rbp), %eax movl %eax, %ecx call divide movl %eax, -4(%rbp) nop .L20: movl -4(%rbp), %eax movl %eax, %edx leaq .LC0(%rip), %rax movq %rax, %rcx call printf movl $0, %eax addq $48, %rsp popq %rbp ret .seh_endproc .globl call_table .def call_table; .scl 2; .type 32; .endef .seh_proc call_table call_table: <------- call_table() pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $80, %rsp .seh_stackalloc 80 .seh_endprologue movl $2, -4(%rbp) movl $3, -8(%rbp) movl $1, -12(%rbp) leaq add(%rip), %rax movq %rax, -48(%rbp) leaq sub(%rip), %rax movq %rax, -40(%rbp) leaq mult(%rip), %rax movq %rax, -32(%rbp) leaq divide(%rip), %rax movq %rax, -24(%rbp) movl -12(%rbp), %eax cltq movq -48(%rbp,%rax,8), %r8 movl -8(%rbp), %edx movl -4(%rbp), %eax movl %eax, %ecx call *%r8 movl %eax, -16(%rbp) movl -16(%rbp), %eax movl %eax, %edx leaq .LC0(%rip), %rax movq %rax, %rcx call printf movl $0, %eax addq $80, %rsp popq %rbp ret .seh_endproc .def __main; .scl 2; .type 32; .endef .globl main .def main; .scl 2; .type 32; .endef .seh_proc main main: pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $32, %rsp .seh_stackalloc 32 .seh_endprologue movl %ecx, 16(%rbp) movq %rdx, 24(%rbp) call __main call call_table call inline_with_switch call functions_with_switch nop addq $32, %rsp popq %rbp ret .seh_endproc .ident "GCC: (MinGW-W64 x86_64-posix-seh, built by Brecht Sanders) 11.2.0" .def __mingw_vfprintf; .scl 2; .type 32; .endef
    - Joker_vD 4y ago
      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).
      - boffinAudio 4y ago
        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.
        teknopaul 4y ago
        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?
        boffinAudio 4y ago
        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.
6keZbCECT2uB 4y ago
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. Switch statements are a pretty good default.
lelanthran 4y ago
> 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.
asveikau 4y ago
I wrote this: > 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.

flohofwoe 4y ago

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.

Joker_vD 4y ago
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.
- boffinAudio 4y ago
  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): .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: <------- inline_with_switch() pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $48, %rsp .seh_stackalloc 48 .seh_endprologue movl $2, -8(%rbp) movl $3, -12(%rbp) movl $1, -16(%rbp) cmpl $3, -16(%rbp) je .L12 cmpl $3, -16(%rbp) jg .L13 cmpl $2, -16(%rbp) je .L14 cmpl $2, -16(%rbp) jg .L13 cmpl $0, -16(%rbp) je .L15 cmpl $1, -16(%rbp) je .L16 jmp .L13 .L15: movl -8(%rbp), %edx movl -12(%rbp), %eax addl %edx, %eax movl %eax, -4(%rbp) jmp .L13 .L16: movl -8(%rbp), %eax subl -12(%rbp), %eax movl %eax, -4(%rbp) jmp .L13 .L14: movl -8(%rbp), %eax imull -12(%rbp), %eax movl %eax, -4(%rbp) jmp .L13 .L12: movl -8(%rbp), %eax cltd idivl -12(%rbp) movl %eax, -4(%rbp) nop .L13: movl -4(%rbp), %eax movl %eax, %edx leaq .LC0(%rip), %rax movq %rax, %rcx call printf movl $0, %eax addq $48, %rsp popq %rbp ret .seh_endproc .globl functions_with_switch .def functions_with_switch; .scl 2; .type 32; .endef .seh_proc functions_with_switch functions_with_switch: <------- functions_with_switch() pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $48, %rsp .seh_stackalloc 48 .seh_endprologue movl $2, -8(%rbp) movl $3, -12(%rbp) movl $1, -16(%rbp) cmpl $3, -16(%rbp) je .L19 cmpl $3, -16(%rbp) jg .L20 cmpl $2, -16(%rbp) je .L21 cmpl $2, -16(%rbp) jg .L20 cmpl $0, -16(%rbp) je .L22 cmpl $1, -16(%rbp) je .L23 jmp .L20 .L22: movl -12(%rbp), %edx movl -8(%rbp), %eax movl %eax, %ecx call add movl %eax, -4(%rbp) jmp .L20 .L23: movl -12(%rbp), %edx movl -8(%rbp), %eax movl %eax, %ecx call sub movl %eax, -4(%rbp) jmp .L20 .L21: movl -12(%rbp), %edx movl -8(%rbp), %eax movl %eax, %ecx call mult movl %eax, -4(%rbp) jmp .L20 .L19: movl -12(%rbp), %edx movl -8(%rbp), %eax movl %eax, %ecx call divide movl %eax, -4(%rbp) nop .L20: movl -4(%rbp), %eax movl %eax, %edx leaq .LC0(%rip), %rax movq %rax, %rcx call printf movl $0, %eax addq $48, %rsp popq %rbp ret .seh_endproc .globl call_table .def call_table; .scl 2; .type 32; .endef .seh_proc call_table call_table: <------- call_table() pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $80, %rsp .seh_stackalloc 80 .seh_endprologue movl $2, -4(%rbp) movl $3, -8(%rbp) movl $1, -12(%rbp) leaq add(%rip), %rax movq %rax, -48(%rbp) leaq sub(%rip), %rax movq %rax, -40(%rbp) leaq mult(%rip), %rax movq %rax, -32(%rbp) leaq divide(%rip), %rax movq %rax, -24(%rbp) movl -12(%rbp), %eax cltq movq -48(%rbp,%rax,8), %r8 movl -8(%rbp), %edx movl -4(%rbp), %eax movl %eax, %ecx call *%r8 movl %eax, -16(%rbp) movl -16(%rbp), %eax movl %eax, %edx leaq .LC0(%rip), %rax movq %rax, %rcx call printf movl $0, %eax addq $80, %rsp popq %rbp ret .seh_endproc .def __main; .scl 2; .type 32; .endef .globl main .def main; .scl 2; .type 32; .endef .seh_proc main main: pushq %rbp .seh_pushreg %rbp movq %rsp, %rbp .seh_setframe %rbp, 0 subq $32, %rsp .seh_stackalloc 32 .seh_endprologue movl %ecx, 16(%rbp) movq %rdx, 24(%rbp) call __main call call_table call inline_with_switch call functions_with_switch nop addq $32, %rsp popq %rbp ret .seh_endproc .ident "GCC: (MinGW-W64 x86_64-posix-seh, built by Brecht Sanders) 11.2.0" .def __mingw_vfprintf; .scl 2; .type 32; .endef
  - Joker_vD 4y ago
    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).
    - boffinAudio 4y ago
      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.
      - teknopaul 4y ago
        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?
        boffinAudio 4y ago
        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.

6keZbCECT2uB 4y ago

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. Switch statements are a pretty good default.

lelanthran 4y ago

> 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.

asveikau 4y ago

I wrote this: > 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.