Live data from Hacker News

Function Dispatch Tables in C (2019)

blog.alicegoldfuss.com

31–40 of 52 posts

Re: Function Dispatch Tables in C (2019)

#31

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.

Yup, though I do think in some cases if the indexes into the function table are known a sufficiently smart compiler can inline it anyway, even if the linkage isn't static: https://godbolt.org/z/6cY7zxT9W

Re: Function Dispatch Tables in C (2019)

#32
post #6

For 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

> For readability, this is reasonable.

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)

#33
post #19

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

That's because there's no right or wrong answer about this, and people on here are not just a bunch of juniors who should automatically accept as an authority anyone who blogs.

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)

#34

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

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.

Re: Function Dispatch Tables in C (2019)

#35

Earlier 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…

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.

Re: Function Dispatch Tables in C (2019)

#36

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

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] = {
            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)

#37

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

The call-table functions also get inlined, so the advantage is shared by both approaches, and yet the call-table produces more efficient code (no cmp/jump traps to fall into...)

See my comment here for the C code and Assembly that demonstrates this:

https://news.ycombinator.com/item?id=31834241

Re: Function Dispatch Tables in C (2019)

#38

Earlier 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]…

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

Re: Function Dispatch Tables in C (2019)

#39
Uh, this is a few years old, and perhaps the author was learning as they went. Still, I think this passage is a bit too much:

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

#40

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

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.

Post reply on HN