Compiler Optimization: How Compilers Optimize switch Statements

The common assumption is that a switch statement compiles to a jump table: an array of code addresses indexed by the case value. This is sometimes true, but it is one of several strategies a modern compiler may use. The actual choice depends on the distribution of case values, the values being returned or computed, and the relative costs of different instruction sequences on the target architecture.

This article is part of the Advent of Compiler Optimisations 2025 series by Matt Godbolt.

Strategy 1: Arithmetic

When the case values form an arithmetic sequence and the return values follow a predictable pattern, the compiler may eliminate the switch entirely and replace it with a formula.

int f(int x) {
    switch(x) {
        case 0: return 100;
        case 1: return 200;
        case 2: return 300;
        case 3: return 400;
        case 4: return 500;
        default: return 0;
    }
}

The compiler observes that the return value is (x + 1) * 100 for inputs 0 through 4. It generates:

; if x < 5: return (x + 1) * 100
; else: return 0

No table, no jumps based on the case value —just a bounds check and a multiply. The switch has been completely algebraically eliminated.

Strategy 2: Lookup Table

When the return values are arbitrary and cannot be expressed as a formula, but the case values are dense (covering a contiguous or near-contiguous range), the compiler generates a static data table:

switch(x) {
    case 0: return 99;
    case 1: return 42;
    case 2: return 17;
    // ...
}

The compiler creates a read-only array (often labeled something like CSWTCH.1 in the assembly) containing the return values in order, performs a bounds check on x, and uses x as an index into the array. This is a data table, not a jump table —there is one memory load and a bounds check, with no branches for the individual cases.

Strategy 3: Bitmask

For switches that return a boolean —such as a membership test —the compiler may construct a bitmask where each bit corresponds to one case value.

bool is_whitespace(char c) {
    switch(c) {
        case ' ':
        case '\t':
        case '\n':
        case '\r':
        case '\v':
        case '\f':
            return true;
        default:
            return false;
    }
}

The whitespace characters span the range from '\t' (ASCII 9) to ' ' (ASCII 32), a range of 24 positions. The compiler encodes which positions within that range are whitespace as a 24-bit constant, then uses the bt (bit test) instruction:

sub edi, 9           ; shift range to start at 0
mov eax, 8388631     ; bitmask: which positions are whitespace
bt  rax, rdi         ; test bit at position (c - '\t')
setc al              ; al = 1 if the bit was set
cmp dil, 24          ; bounds check: is c in the range at all?
cmovnb eax, edx      ; if out of range, return 0

A single bit test replaces six comparisons, and there are no conditional branches. The result is computed entirely through flag manipulation.

Note that isspace() from the standard library should generally be preferred in production code; this example is purely illustrative of the optimization technique.

Strategy 4: Jump Table

Jump tables appear when case values are dense, the cases have different behaviors (not just different return values), and the compiler cannot simplify to one of the above approaches. The table contains code addresses, and the switch dispatches by loading the address at index x and jumping to it:

jmp [table + rax*8]

This is the implementation people most commonly imagine. It offers O(1) dispatch regardless of how many cases there are, but it requires the case values to be compact (or the compiler to pad the table for missing values). It also introduces an indirect branch, which has implications for branch prediction and security (speculative execution attacks).

Strategy 5: Binary Search Tree

When case values are sparse —spread across a wide range with large gaps —a jump table would waste enormous amounts of memory. Instead the compiler generates a sequence of comparisons that amounts to a binary search:

switch(x) {
    case 100: ...
    case 2511: ...
    case 4865: ...
    case 5284: ...
}

The compiler emits comparisons against the median value, then recursively handles each half. This reduces the average number of comparisons from O(n) (a linear if-else chain) to O(log n) —matching what a hand-written binary search would produce.

How the Compiler Chooses

The compiler evaluates all applicable strategies and selects based on estimated code size and execution cost. The factors include:

Density of case values: dense 鈫?lookup table or jump table; sparse 鈫?arithmetic or binary search.
Pattern in return values: arithmetic patterns 鈫?formula; irregular 鈫?table.
Number of cases: very few 鈫?comparison chain; many dense 鈫?jump table; many sparse 鈫?binary search.
Target architecture: the cost of memory access, branch misprediction, and available instructions influences the decision.

Different compilers (GCC, Clang, MSVC) may reach different conclusions for the same input. Compiler Explorer is the right tool for verifying what a specific compiler and version will produce.

Practical Advice

Write switch statements to express intent clearly. Do not restructure them to try to force a particular implementation strategy —you are more likely to make the code harder to read than to improve performance. The compiler’s analysis is thorough and accounts for factors that are difficult to reason about manually.

If you observe that a hot switch is not being compiled as efficiently as expected, profile first to confirm it is actually a bottleneck, then use Compiler Explorer to understand what the compiler is generating and why. Minor changes to the case values or return expressions can sometimes shift the compiler from one strategy to another.