Hacker News Reader

Comment by boffinAudio | Hacker News Reader

Whats the performance cost exactly?

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

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):

      .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

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.

Switch statements are a pretty good default.

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

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.

Reply on news.ycombinator.com