GCC emits a jump table for dense case ranges and a comparison tree for sparse ranges, as shown in the compiled assembly.
GCC SWITCH LOWERING REVEALS JUMP TABLE THRESHOLD
*GCC's optimizer chooses between jump tables and comparison trees based on case density. Experiments show a break point near eight entries per label, with outliers handled separately.*
GCC's handling of switch statements hides a nuanced cost model that developers rarely see. By compiling identical source snippets with -O3, the author exposed how the compiler decides between a jump table and a cascade of comparisons. The experiments span contiguous ranges, constant offsets, evenly spaced sparse values, and outlier mixes. Each variant reveals a rule set that pivots on case density, not just numeric spacing. Understanding these rules lets low‑level programmers predict performance and size impacts of their switch constructs.
When does GCC emit a jump table?
The author compiled a simple function with five consecutive case labels (0‑4) under -O3. GCC emitted a jump table, mapping each case to its target function via a .quad table. The same pattern held when the values were offset by a constant (97‑101); GCC generated a lea instruction to normalize the index before the jump. The experiments indicate that GCC prefers a jump table when the number of entries per case label approaches eight. Below that density, the optimizer switches to a tree of comparisons, as shown in the sparse_8 example where five spaced values produced a cascade of cmp and je instructions instead of a table.
How does GCC treat sparse case values?
In the sparse_8 function, case values are equally spaced (0, 8, 16, 24, 40) but still sparse relative to the range. GCC compiled this into a series of conditional branches rather than a jump table. The assembly shows a mix of cmp, je, jle, and direct jumps to the target functions. The visualized comparison tree confirms that GCC builds a decision tree when the density falls below the observed threshold. This behavior aligns with the author's intuition that sparse values diminish the advantage of a jump table.
What happens with outlier case values?
Adding an outlier (case 100) to an otherwise dense block (cases 1‑5) triggers mixed lowering. GCC emits a branch for the outlier and retains a jump table for the dense subset. The generated code first checks if the input exceeds 5, then jumps to a separate branch that handles the 100 case. If the input is within the dense range, GCC uses the same .quad table as before. This demonstrates that GCC can isolate dense subsets and apply the most efficient lowering for each region.
Can GCC simplify identical case outcomes?
The source notes that when multiple case labels resolve to the same function, GCC does not automatically divide the input to reduce the table size. In the sparse_8 example, dividing x by eight would collapse the cases into a smaller range, but GCC does not perform that transformation. The author highlights this as a missed optimization, confirming that GCC's analysis stops at density thresholds and does not pursue arithmetic simplifications that could further shrink the decision structure.
Frequently asked questions
What threshold does GCC use to decide between a jump table and a comparison tree?
Experiments show GCC switches to a comparison tree when there are fewer than about eight jump table entries per case label.
How does GCC handle a switch with a dense block of cases and a single outlier?
GCC emits a branch for the outlier (e.g., case 100) and a jump table for the dense block (e.g., cases 1‑5).
Does GCC simplify switches where multiple cases call the same function?
No. The author notes that GCC does not divide the input to collapse identical outcomes, leaving the original case density unchanged.
The findings strip away the mystery of GCC's switch lowering. A clear density threshold drives the choice of jump tables, while outliers are isolated into separate branches. The optimizer does not pursue arithmetic shortcuts that could compress sparse cases further. Armed with this knowledge, developers can shape their switch statements to force the most efficient lowering, avoiding hidden performance penalties in critical code paths.
Sources: [Hacker News – Switch Lowering in GCC]