Switch Lowering in GCC
Points and comments are a snapshot, not live.
GCC lowers switch statements using jump tables, bitsets, and decision trees, with complex profitability heuristics.
The article examines how GCC compiles switch statements. It transforms contiguous case labels into jump tables, uses bitset tests (via the `bt` instruction) for up to 64 sparse values with few unique outcomes, and generates decision trees for other patterns. GCC identifies dense subsets (e.g., handling cases 1-5 with a jump table and case 100 with a branch) but misses optimization like dividing by 8 before a jump. The decision tree pass minimizes comparisons; the bitset heuristic requires at least 3 cases for one unique edge, 5 for two, or 6 for three.
The compiler's implementation uses dynamic programming to group case labels into clusters for bitsets or jump tables, applying profitability checks before emitting the transformation.
What commenters are saying
Commenters note missed optimizations: GCC could often use perfect hashing for large sparse switches and divide the input to shrink jump tables. One participant benchmarked an alternative for the sparse_8 example, finding it nearly twice as fast for unpredictable input (4.5 ns vs 2.72 ns) but slower for predictable input. Others observe that decision trees can outperform jump tables in some scenarios. There is skepticism about compiler priorities, with one commenter claiming LLVM rejected perfect hashing a decade ago despite its utility for emulators and Unicode parsing. The performance impact of switch lowering on branch prediction and BTB hardware is also discussed.