How are switches optimized

[Johan Engelen]

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