4 ms·
Whats the performance cost exactly?
by boffinAudio 4y ago
Whats the performance cost exactly?
- asveikau 4y agoModern 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. See also: qsort in c vs std::sort in c++
- boffinAudio 4y agoI 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 agoThat'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 agoEven 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 agoI 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
- 6keZbCECT2uB 4y agoPredicting 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 agoI 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.