Switch Lowering in GCC

arsalan17

This one was interesting, especially its name :)

LarsKrimi

> The switch in sparse_8 could be simplified by dividing x by eight before the jump. Interestingly, gcc doesn't find this simplification. It could not because that would ensure that 7 values for each case would be handled by function calls instead of the default case - 0/8 is 0, but 3/8 is also 0

sylware

In order to peak into hardware speculation/BTB, having a look atswitch lowering seems a good way. Big switches will go into serious convolution to please that hardware since by definition this is a source of a lot of branch mispredicitions.

rurban

What a shame for clang and gcc! They still don't implement perfect hashes for large sparse switch tables. I did that recently for my rcc C compiler, and it was just a single day of work. Esp. beneficial for unicode work. The LLVM patch was rejected a decade ago. Gcc has several unicode patches sitting in branches, which would also need that

tsukikage

Why the indirection? - why not have the jump table reference f0..fX directly rather than jumping to a jump?

Andi

I remember having implemented similar things in JavaScript (by generating code), for immutable Maps and Sets - no significant performance gain in modern engines. For regular expressions of complex unicode ranges, the speedup was around 2x!

p-t

I assume 34 in the compact_7() one was supposed to be 35, and edx was supposed to be used at some point in the bittest() one (unless i'm missing something lol)

erk__

I once played around with having a very large switch statement (all mac address manufactors in one switch) and in LLVM it would compile fine without optimizations, but if I turned optimizations on it would just spend around half an hour compiling it. I think GCC did it faster, but its been some time ago since I did it. In the Rust crate that was the reasons for all this I just ended up doing perfect hashing which compiled much much faster.

zamalek

> The compiler is able to implement them as a decision tree (even though maybe it shouldn't) Sometimes a decision tree is definitely faster. When developing System.HashCode, I used a switch (which I think always compiles to a jump table in .Net - at least my case did back then). This was for the trailing non-block sized bytes, I think. It was either suggested, or I decided to try, a decision tree and it was significantly faster. This was _many_ years back, so I don't have the figures, but they can be better in some scenarios.