22
$\begingroup$

A switch statement, as in languages like C, Java or Javascript, allows branching based on different cases of some value (the "scrutinee"). It's well known that switch statements can be compiled using a jump table, but this relies on the cases all being within a relatively small range of integers, in order to use the scrutinee as an index into the jump table, otherwise the table would be very large and most of it would be wasted space.

For the purposes of this question, assume the case values are fixed integers known at compile time. In the best case, they would be consecutive integers. What other strategies are there for compiling a switch statement if the cases are not densely distributed within some narrow range?

$\endgroup$

3 Answers 3

27
$\begingroup$

In general, it depends how many cases there are and exactly how sparse the cases are.

One way to think about the sparseness problem that may help is to rephrase the question as "How do I turn a sparse switch into a dense switch?" If you can do that, then all the dense techniques (e.g. jump table) can be applied to the resulting switch. Keep that in mind as we go through some possibilities.

Chain or tree of if-then-else statements

A chain of if-then-else statements is self-explanatory, but you can also arrange the if-then-else statements into a binary search tree.

This was a very popular technique back in the day before the cost of a mispredicted branch became extremely high. Minimising the number of difficult-to-predict branches in a code path is very important these days, and for a switch statement, should ideally be reduced to 1 in the worst case.

Use a table to make the switch dense

If the range of possible values isn't too large but the cases are sparse, using a table to make the switch dense may be appropriate. This is especially useful if you have multiple case statements pointing to the same line of code. For example, this switch statement in C:

switch (x) {
    case 1:
    case 5:
        do_something();
        break;
    case 3:
    case 10:
        do_something_else();
        break;
    default:
        do_default();
        break;
}

could be made dense like this:

static uint8_t switch_1[11] = { 2, 0, 2, 1, 2, 0, 2, 2, 2, 2, 1 };
if (x > 10) goto default_case; /* Statically predict this branch as unlikely */
switch (switch_1[x]) {
    case 0:
        do_something();
        break;
    case 1:
        do_something_else();
        break;
    case 2:
default_case:
        do_default();
        break;
}

Note that any kind of table would work; you could also use perfect hashing if you were switching on strings. If this new switch is implemented as a jump table, then this is sometimes called a two-level jump table.

This technique clearly doesn't work if the range of possible values is huge. Here's an example based on real code; it iterates over all of the set bits in a word:

void f(uint16_t x)
{
    while (x) {
        uint16_t bit = x & -x; /* Extract the least-significant set bit */
        x &= ~bit;
        switch (bit) {
            case 0x0001: case_bit_0(); break;
            case 0x0002: case_bit_1(); break;
            case 0x0004: case_bit_2(); break;
            case 0x0008: case_bit_3(); break;
            /* etc etc */
            case 0x4000: case_bit_14(); break;
            case 0x8000: case_bit_15(); break;
        }
    }
}

I'm going to use this as an archetype in the examples that follow.

Split the range

You could perform a top-level switch on some of the range and then a switches to discriminate between leaf cases:

switch (bit >> 8) {
    case 0:
        switch (bit & 0xFF) {
            case 0x01: case_bit_0(); break;
            case 0x02: case_bit_1(); break;
            /* etc etc */
            case 0x80: case_bit_7(); break;
        }
        break;
    case 0x01: if (bit != 0x0100) break; case_bit_8(); break;
    case 0x02: if (bit != 0x0200) break; case_bit_9(); break;
    /* etc etc */
    case 0x80: if (bit != 0x8000) break; case_bit_15(); break;
}

Note that a switch on a single value is here compiled to an if statement. That if statement can be statically predicted if allowed on the platform.

Arithmetic or logic transformation

This doesn't always apply, but when it does, it pays off handsomely.

In this example, the cases have a geometric distribution, which is a surprisingly common case. Modern CPUs have a priority encoder instruction which gives you the highest or lowest set bit in a word. It can go by many names; some ISAs call it "bit scan" (e.g. bsr and bsl on x86), and others "count leading/trailing zeroes", but I'm going to call it floor_log_2 here.

Again, you may need to test the cases:

switch (floor_log_2(bit)) {
    case 0: if (bit != 0x0001) break; case_bit_0(); break; /* This test is technically not needed */
    case 1: if (bit != 0x0002) break; case_bit_1(); break;
    case 2: if (bit != 0x0004) break; case_bit_2(); break;
    /* etc etc */
    case 15: if (bit != 0x8000) break; case_bit_15(); break;
}

In general, you may be able to find some kind of cheap transformation which maps the sparse cases into dense cases.

Branch-free binary search

Every modern CPU has some way to perform a comparison and return 0 if the comparison is false and 1 if the comparison is true.

This gives you a way to search a sorted array in a way that involves no branches in the "loop".

First, you pad the number of cases to the next power of 2. In this case, the number of cases is already a power of 2, so we're fine.

Now you can compile this into a branch-free binary search followed by a dense switch:

static const uint16_t jumpvalues[] = {
    0x0001, 0x0002, 0x0004, 0x0008,
    0x0010, 0x0020, 0x0040, 0x0080,
    0x0100, 0x0200, 0x0400, 0x0800,
    0x1000, 0x2000, 0x4000, 0x8000
};

/* The first two lines could, of course, be optimised to:

       int j = (bit >= 0x0100) << 3;

   I'm writing it out in full for exposition purposes.
*/
int j = 0;
j += (bit >= jumpvalues[j + (1<<3)]) << 3;
j += (bit >= jumpvalues[j + (1<<2)]) << 2;
j += (bit >= jumpvalues[j + (1<<1)]) << 1;
j += (bit >= jumpvalues[j + (1<<0)]) << 0;
if (bit != jumpvalues[j]) { /* Statically predict as not taken */
    goto default_case;
}
switch (j) {
    case 0: case_bit_0(); break;
    case 1: case_bit_1(); break;
    case 2: case_bit_2(); break;
    /* etc etc */
    case 15: case_bit_15(); break;
}
default_case:

If you don't have a convenient "0 if false, 1 if true" instruction but you do have a conditional move instruction, then the unrolled loop might be better expressed like this:

int j = 0, k;
k = j + 8;  if (bit >= jumpvalues[k]) j = k;
k = j + 4;  if (bit >= jumpvalues[k]) j = k;
k = j + 2;  if (bit >= jumpvalues[k]) j = k;
k = j + 1;  if (bit >= jumpvalues[k]) j = k;

This has the obvious advantage that it always works, but I've never seen a compiler generate code that looks like this. There may be a good reason why not; perhaps the unrolled loop is difficult to schedule?

EDIT This originally contained a much less space-efficient flattened tree. I realised that this wasn't necessary.

Bit vector rank

This technique relies on having an advanced bit manipulation instruction such as Hamming weight (which I will call popcount here).

Suppose you stored all the valid cases in a bit vector. Then you can test if a case is one of the ones that's interesting in constant time by simply looking at the bit in the bit vector.

We define the rank of some bit to be the number of set bits (i.e. the number of bits that are set to 1) to the left of it in the bit vector. We can calculate this by precomputing for every word, and using bit manipulation instructions to count within a word.

As an example, suppose we are switching on these values:

switch (x) {
    case 1:
    case 2:
    case 5:
    case 10:
    case 20:
    case 50:
    case 100:
    case 200:
    case 500:
}

We can store these values in a bit vector, along with a separate array that records the number of bits set to the left of each word:

static const uint64_t jump_bitvector[] = {
    /* 1 << 1 | 1 << 2 | 1 << 5 | 1 << 10 | 1 << 20 | 1 << 50 */
    0x0004000000100426,
    /* 1 << (100 - 64) */
    0x0000001000000000,
    0x0000000000000000,
    /* 1 << (200 - 192), etc etc */
    0x0000000000000100,
    0x0000000000000000,
    0x0000000000000000,
    0x0000000000000000,
    0x0010000000000000
};
static const uint8_t jump_bitvector_rank[] = {
    0,
    6, /* The number of set bits in jump_bitvector[0] */
    7, /* The number of set bits in jump_bitvector[0..1] */
    7, /* The number of set bits in jump_bitvector[0..2], etc */
    8,
    8,
    8,
    8
};

And now we can implement the switch like this:

if (x > 500) goto default_case;

uint64_t word_index = x / 64;
uint64_t bit = 1 << (x & 63);
uint64_t jump_bitvector_word = jump_bitvector[word_index];

if (!(jump_bitvector_word & bit)) goto default_case;

/* At this point, we KNOW that x is one of the cases. */
int rank = jump_bitvector_rank[word_index]
         + popcount(jump_bitvector_word & (bit - 1));
switch (rank) {
   case 0: /* x == 1 */
   case 1: /* x == 2 */
   case 2: /* x == 5 */
   case 3: /* x == 10 */
   /* etc etc */
}
$\endgroup$
2
  • 2
    $\begingroup$ You skipped over perfect hashing very quickly, but it may warrant further consideration. There's nothing that restricts it to strings (only that hashing strings can be very helpful to turn them into table indices). Perfect hashing can work for range reduction on integers, too. There's a cost to it that needs to be weighed against other techniques of course (particularly the cost at compile time - you wouldn't want to do it for unoptimised builds). $\endgroup$ Aug 16, 2023 at 14:25
  • $\begingroup$ @TobySpeight It's certainly possible. Most of the minimal perfect hash algorithms that I know involve a relatively expensive instruction (e.g. remainder), or a sparse-to-dense reduction step (which is the problem we're trying to solve in the first place!). If you know of any that might be suitable, feel free to write an answer. $\endgroup$
    – Pseudonym
    Aug 16, 2023 at 23:43
6
$\begingroup$

The easiest option is to compile the cases as if they are a chain of if/else if/else statements; this may be acceptable performance-wise if the number of cases is small. The number of comparisons can be reduced by ordering the conditions from most-likely to least-likely, which may be determined if profiling data is available.

Another option is to do a binary search: compare the scrutinee with the median of the cases, then the median of the remaining cases in each branch, and so on until the exact case is determined. This allows the correct branch to be found with a logarithmic number of comparisons, instead of a linear number.

Alternatively, a jump table may still be used if the cases can be mapped into a smaller range. In the best case, since the case values are known at compile-time, the compiler can find a perfect hash function which maps the scrutinee into a range of consecutive integers, so that the hash of the scrutinee can be used as an index into the jump table. It will still be necessary to perform a comparison of the scrutinee with the case's value, to check for a collision ─ there won't be collisions between hashes of different case values (since the hash function is perfect), but a collision could happen if the scrutinee is not one of the case values.

$\endgroup$
1
$\begingroup$

If the case values are single integers, it's not very dense and the number of values is not too small, just use a hash table. It may have collisions, but at least better than the naive branching way.

If you don't like small hash tables for some reasons, you could use a big hash table to contain the information of all switch statements, and hash the switch statement id and case values together. Switch statement ids don't need to be stored in the hash table, as you could check whether the target is in a specific range, as it is static. Deliberate collisions could be dealt with randomness in complication. You could run some tests to decide the actual data structure to use, and what is dense or sparse, and how much is too small.

If you need to support ranges, where hash tables are not an option, and if it is relatively sparse, but dense enough to have much more cases than the number of bits in the case values, a theoretically better data structure is X-fast trie, or Y-fast trie in some cases if memory usage is important. You start by hashing the first half of the bits in the input, and advance another 1/4 if it is found, and retract 1/4 if not, then repeat and advance or retract for 1/8, and so on. It is supposed to be used only on data not longer than a CPU word, and you should use a normal trie on top of it for longer data. This is a bit complex, and has more overhead. I don't know how good it works in practice.

$\endgroup$
2
  • $\begingroup$ I don't know of any hashtable implementation which avoids branching. How do you resolve collisions, or queries where the value is not present? I would really like to see some support for your claim that a hashtable lookup can be cheaper than branching. $\endgroup$
    – kaya3
    Aug 16, 2023 at 13:15
  • $\begingroup$ @kaya3 Well, I was just careless about the choosing of terms. For what is cheaper, and cheaper in what cases, I suggest running a test. $\endgroup$
    – user23013
    Aug 16, 2023 at 17:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .