GCC turns switch statements into jump tables, binary search, or bit tests
Switch Lowering in GCC
A deep dive into how GCC lowers switch statements, revealing jump tables for dense cases, comparison trees for sparse ones, and even bitset tests for non-contiguous labels. The author digs into the compiler source to explain the heuristics—like the eight-entries-per-case threshold—and shows why some seemingly profitable jump tables are skipped in favor of fewer comparisons.
If we examine the binary representation of 2753205, we find that it is in fact a bitset. The bits that are set to one correspond to the ASCII values of the case labels, each value being reduced by 48.
- 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
- 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
- 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)
- 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!