5 ms·

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 pointer

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.

boffinAudio 4y ago
Whats the performance cost exactly?
- asveikau 4y ago
  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. See also: qsort in c vs std::sort in c++
  - boffinAudio 4y ago
    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

boffinAudio 4y ago

Whats the performance cost exactly?

asveikau 4y ago
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. See also: qsort in c vs std::sort in c++
- boffinAudio 4y ago
  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