4 ms·

Definitely can be useful, but keep in mind that performance will usually be worse for function tables.

• boffinAudio 4y ago
  Why? And, if this is the case, why then do compilers turn switch statements into function tables?
  • vore 4y ago
    While compilers do turn switch statements into jump tables, in this case storing function pointers and calling them you add the additional call overhead of saving registers, setting up the stack, etc in the function prolog and epilog.
    • boffinAudio 4y ago
      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.
      • flohofwoe 4y ago
        ...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.
        • boffinAudio 4y ago
          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 https://news.ycombinator.com/item?id=31834241
          • dzaima 4y ago
            I can't reproduce neither clang nor gcc with -O3 inlining functions in a call table: https://godbolt.org/z/E7Tj31vox https://godbolt.org/z/E7Tj31vox Nor do I see any of that kind of behavior in your linked assembly - call_table clearly contains "call *%r8", which is an indirect call to a function, definitely not inlined. Here's a more complete test: https://godbolt.org/z/dT45aKTe1 https://godbolt.org/z/dT45aKTe1 - putting the operation in a loop (to be able to more clearly see the per-iteration cost of the operation), with -O3, both clang & gcc. While gcc decides to do comparisons (it wants at least 5 cases for a jump table apparently), clang does do the indirect jump, while neither does anything other than a call (thus suffering said register spilling & stack manipulation overhead) for the explicit function jump table.
            • boffinAudio 4y ago
              I'm using gcc under Ubuntu/WSL on Windows, so it may be some compiler thing. But nevertheless, thank you for taking the time to follow up on this, because it is a very interesting subject to me personally and a lot has been learned through efforts such as yours, in this thread.
              • dzaima 4y ago
                Windows/WSL shouldn't change anything, gcc will have the same set of optimizations everywhere. There's just no inlining of the functions going on. There may be differences in the dispatching between different compilers & optimization levels, but none inline functions from a function list. It'd be a pretty messy optimization, as it'd need to check whether all functions can be inlined instead of just any single one (and increase the requirements if the call otherwise would be a tail-call, which cost a decent bit less), and it'd make it impossible to predictably do an actual function jump table if the compiler sometimes just didn't.
            • dzaima 4y ago
              And, some actual timings (code: https://godbolt.org/z/qnWEqs446 https://godbolt.org/z/qnWEqs446): $ clang -DLEN=1024 -DITERATIONS=100000 -O3 switch.c && ./a.out predictable: call_table: 173.1ms switch_cases: 59.6ms random: call_table: 536.2ms switch_cases: 450.4ms $ gcc -DLEN=1024 -DITERATIONS=100000 -O3 -fcf-protection=none switch.c && ./a.out predictable: call_table: 174.5ms switch_cases: 114.7ms random: call_table: 581.8ms switch_cases: 108.8ms $ clang -DLEN=64 -DITERATIONS=2000000 -O3 switch.c && ./a.out predictable: call_table: 230.6ms switch_cases: 116.0ms random: call_table: 218.7ms switch_cases: 158.2ms $ gcc -DLEN=64 -DITERATIONS=2000000 -O3 -fcf-protection=none switch.c && ./a.out predictable: call_table: 872.7ms switch_cases: 146.3ms random: call_table: 740.4ms switch_cases: 132.2ms The switch is faster in all cases, often by a big margin.
      • vore 4y ago
        My comparison is vis-a-vis an array of function pointers as described in the article vs a compiler-generated switch jump table with inlined bodies that the compiler will always generate with a switch statement, rather than in comparison to an if-else tree: there is no function being generated, so there is no function prolog or epilog.
  • flohofwoe 4y ago
    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.
    • vore 4y ago
      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 https://godbolt.org/z/6cY7zxT9W