4 ms·

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 s

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

by dzaima 4y ago

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.