On Friday, 1 June 2018 at 21:18:25 UTC, IntegratedDimensions
wrote:
What is the best optimizations that a compiler does to switches
in general and in the D compilers?
The best possible depends a lot on the specific case at hand.
Best possible is to fully elide the switch, which does happen.
You can use d.godbolt.org to investigate what happens for
different pieces of code.
Sometimes a jumptable is used, sometimes an if-chain.
LLVM's (LDC) and GCC's (GDC) optimizers are strong and the
optimized code will often do extra calculations before indexing
in the table or before doing the comparisons in the if-chain.
Different compilers will make different optimizations.
https://godbolt.org/g/pHptff
https://godbolt.org/g/AwZ69o
A switch can be seen as if statements, or safer, nested if
elses.
but surely the cost per case does not grow with depth in the
switch? If one has a switch of N case then the last cost surely
does not cost N times the cost of the first, approximately?
Depends on the code, but it's not O(N).
This is the cost when implementing a switch as nested ifs.
Not true. Nested if's are optimized as well. Sometimes switch is
faster, sometimes if-chain, sometimes it's the same.
Tables can be used to give O(1) cost, are these used in D's
compilers?
Yes (LDC and GDC).
How are they generally implemented? Hash tables? If the switch
is on an enum of small values is it optimized for a simple
calculating offset table?
Table stored in the instruction stream. Simple offset table with
calculation on the index value (I guess you could say it is a
simplified hash table).
Note that with performance, the rest of the program and the
execution flow also matters...
cheers,
Johan
