Lowering switch Statements

A switch looks innocent — a value, a list of cases, jump to the one that matches. But it hands the compiler a genuine engineering decision, because there is no single right way to turn "pick one of many" into machine code. Should it test the cases one by one? Binary-search them? Or leap straight to the answer through a table of addresses? Each is correct; each is fastest for a different shape of switch. Deciding which — from the number of cases and how tightly their values cluster — is one of the most visibly clever things a code generator does.

Every strategy is built from primitives you already know: conditional jumps and labels from three-address code, and the same jumping-code discipline used to translate control flow. What changes is how many comparisons the generated code performs before it lands on the right arm.

Three ways to dispatch

Consider a plain source switch on an integer, with a handful of case labels and a default. The compiler weighs three canonical lowerings:

Strategy	Shape of generated code	Comparisons to dispatch	Chosen when…
Linear if–else chain	test each case value in turn	O(n)	few cases (roughly \le 3\text{–}4)
Binary search tree	compare against a median, recurse into half	O(\log n)	many cases, values sparse / scattered
Jump table	index an array of addresses, one indirect jump	O(1)	many cases packed into a dense range

The figure shows all three lowerings of the same six-case switch, so you can see the comparison count shrink from a chain, to a tree, to a single indexed jump.

The linear if–else chain

The simplest lowering is a straight cascade of conditional jumps — exactly what a chain of if/else if would produce:

if t == 1 goto L1 if t == 2 goto L2 if t == 5 goto L5 goto Ldefault

Each test that fails falls through to the next. For n cases the worst case is n comparisons, and the last case listed is the slowest to reach — so for a handful of cases it is perfectly fine, and for a switch with a hot common case, putting that case first is a real speed-up. Beyond three or four arms, though, the linear scan starts to sting, and the compiler reaches for something smarter.

The binary search tree

When there are many cases but their values are scattered — say \{3, 17, 42, 99, 256, 1000\} — a jump table would be mostly empty holes, so the compiler sorts the case values and emits a binary search. Compare the switch value against the median case; if smaller, recurse into the lower half, if larger, the upper half:

if t < 42 goto Lo // lower half: {3, 17} if t == 42 goto L42 // upper half: {99, 256, 1000} if t < 256 goto L99_check if t == 256 goto L256 if t == 1000 goto L1000 goto Ldefault ...

Each comparison halves the remaining candidates, so dispatch costs O(\log_2 n) tests — six cases in about three comparisons, a thousand cases in about ten. It needs no contiguous range and no wasted memory, which is why it is the workhorse for large, sparse switches (and how a good compiler lowers a switch over scattered enum-like constants).

The jump table: dispatch in O(1)

The prize lowering. If the case values fill a dense range — say 0,1,2,3,4,5 — the compiler builds a jump table: an array of code addresses, one slot per value in the range. Dispatch becomes a range check, an index, a load, and a single indirect jump — O(1), no matter how many cases:

if t < 0 goto Ldefault // range check, low if t > 5 goto Ldefault // range check, high addr = JTAB[t] // load the target address from the table goto *addr // one indirect jump — done JTAB: [L0, L1, L2, L3, L4, L5] // a table of code addresses

Slots for missing values in the range simply point at Ldefault. The catch is density: a table for cases \{1, 1000000\} would need a million slots, almost all pointing at the default — a megabyte of memory to dispatch two cases. So compilers gate the jump table on a density heuristic: build one only when the filled fraction of the range, \dfrac{\#\text{cases}}{(\text{max} - \text{min} + 1)}, exceeds a threshold (GCC and LLVM use roughly 40–60%). Otherwise they fall back to a binary tree — often a hybrid: dense clusters become little jump tables, sitting at the leaves of a binary search over the clusters.

Few cases (a handful): a linear if–else chain, O(n) — simplest, and lets a hot case be tested first.
Many, sparse cases: a binary search tree on sorted values, O(\log n) — no wasted memory.
Many, dense cases (a packed range): a jump table of addresses, O(1) — chosen when the range's fill density clears a threshold.
default is the fall-through target: the tail of the chain, a tree leaf, or the filler for every empty jump-table slot and out-of-range value.

The density decision, in code

Here is the heart of the compiler's choice: given the set of case values, measure the range density and pick a strategy. We run it on a dense switch, a sparse one, and a tiny one.

type Strategy = "jump-table" | "binary-search" | "if-else-chain"; function chooseLowering(cases: number[]): Strategy { const n = cases.length; if (n <= 3) return "if-else-chain"; // too few to bother being clever const lo = Math.min(...cases); const hi = Math.max(...cases); const span = hi - lo + 1; // slots a jump table would need const density = n / span; // filled fraction of the range console.log(`n=${n} range=[${lo},${hi}] span=${span} density=${density.toFixed(2)}`); // Dense range -> a jump table dispatches in O(1); otherwise binary-search the sorted values. return density >= 0.5 ? "jump-table" : "binary-search"; } console.log("dense :", chooseLowering([0, 1, 2, 3, 4, 5])); // 6/6 = 1.00 -> jump table console.log("sparse :", chooseLowering([3, 17, 42, 99, 256, 1000])); // 6/998 -> binary search console.log("tiny :", chooseLowering([1, 2, 5])); // n<=3 -> if-else chain console.log("cluster:", chooseLowering([10, 11, 12, 13, 90, 91])); // 6/82 -> binary search (hybrid in practice)

The dense case clears the threshold and gets an O(1) jump table; the scattered one, with density under 1%, becomes a binary search; the three-case switch stays a simple chain. A real compiler goes further and splits the cluster example into a jump table per dense run hung off a binary search — the hybrid — but the core decision is exactly this density check.

Because O(1) counts comparisons, not clock cycles — and the indirect goto *addr at the heart of a jump table is a indirect branch the CPU's branch predictor struggles to guess. A mispredicted indirect jump can cost a dozen-plus cycles as the pipeline flushes, whereas a short if–else chain is a string of direct conditional branches the predictor handles beautifully, especially if one case dominates. So for a hot switch with a heavily skewed distribution, a compiler (or a profile-guided optimiser) may deliberately keep a linear chain, or peel the common case out in front of the table. Big-O is the start of the story, not the end; the memory system and the branch predictor write the last chapter.

Two traps snare people lowering switches. First, in C-family languages a case without a break falls through into the next case's body — that is control flow inside the arms, totally separate from how the switch dispatches to an arm. Your lowering strategy (chain / tree / table) picks the entry label; fall-through is just the absence of a jump at the end of an arm. Conflating them produces code that runs the wrong arms. Second, the default is not merely "the else at the bottom of a chain" — in a jump table it must fill every empty slot in the range and catch every out-of-range value, which is why the lowering always emits the two range checks before indexing. Forget either the empty-slot filler or a range check and an unlisted value will index off the end of the table and jump to a garbage address.