A switch with five cases usually becomes a jump table: one array of addresses, one indirect jump. If you do the same five cases with gaps between them, GCC builds a tree of comparisons. Because the compiler has a budget.

The rule

In practice, GCC roughly applies this: a jump table is worth it if it is no more than eight times as large as the number of case labels. So five labels may produce a table of forty entries. If the outlier is too far away, the table becomes too expensive.

In Xoranth's article it is worked out neatly. This variant still becomes a table:

switch (x) {
    case 0:  return f0(val);
    case 7:  return f1(val);
    case 14: return f2(val);
    case 21: return f3(val);
    case 34: return f4(val);
}

This one does not:

switch (x) {
    case 0:  return f0(val);
    case 8:  return f1(val);
    case 16: return f2(val);
    case 24: return f3(val);
    case 40: return f4(val);
}

At a glance the blocks differ little, and yet the decision comes out differently.

What else the compiler sees

First: an outlier is handled separately. Add a case 100, and GCC makes a branch for 100 and a table for 1 through 5. For each switch it looks for a subset that pays off.

Second: contiguous ranges are summarised. case 42 through 45 become two comparisons instead of four, even before a table is considered.

For the sequence 0, 8, 16, 24, 40 you could divide x by eight and still use a table. GCC does not do that. It optimises what it sees, and what a human would come up with does not enter into it.

Why this matters

With a switch, most programmers think about readability. The compiler thinks about expected jumps, cache and code size, and has a heuristic for that which is nowhere in the language.

As a result you do not have to write assembly. It is also the reason the same code can perform differently on two architectures, and that a micro-optimisation sometimes turns out wrong.

The compiler is a negotiator with a budget. You only see the outcome.

Source: Switch lowering in GCC — Xoranth.