<p>A <code>switch</code> statement, as in languages like C, Java or Javascript, allows branching based on different cases of some value (the &quot;scrutinee&quot;). It's well known that <code>switch</code> statements can be compiled using a <a href="https://en.wikipedia.org/wiki/Branch_table" rel="noreferrer">jump table</a>, 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.</p>
<p>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 <code>switch</code> statement if the cases are not densely distributed within some narrow range?</p>

<compilers><switch-statement>
How can switch statements with sparse cases be compiled?
<p>The easiest option is to compile the cases as if they are a chain of <code>if</code>/<code>else if</code>/<code>else</code> 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 <a href="https://en.wikipedia.org/wiki/Profile-guided_optimization" rel="noreferrer">profiling data</a> is available.</p>
<p>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.</p>
<p>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 <a href="https://en.wikipedia.org/wiki/Perfect_hash_function" rel="noreferrer">perfect hash function</a> 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.</p>

CC BY-SA 4.0
2023-05-20T15:57:01.973Z
2023-05-20T16:05:16.787Z
2023-05-20T16:05:16.787Z
kaya3
<p>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.</p>
<p>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.</p>
<p>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 <a href="https://en.wikipedia.org/wiki/X-fast_trie" rel="nofollow noreferrer">X-fast trie</a>, or <a href="https://en.wikipedia.org/wiki/Y-fast_trie" rel="nofollow noreferrer">Y-fast trie</a> 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.</p>

CC BY-SA 4.0
2023-08-16T06:27:26.440Z
2023-08-16T17:44:27.733Z
2023-08-16T17:44:27.733Z
user23013
CC BY-SA 4.0
2023-08-16T13:15:42.573Z
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.
kaya3
CC BY-SA 4.0
2023-08-16T17:48:25.417Z
@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.
user23013
<p>In general, it depends how many cases there are and exactly how sparse the cases are.</p>
<p>One way to think about the sparseness problem that may help is to rephrase the question as &quot;How do I turn a sparse switch into a dense switch?&quot; 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.</p>
<h2>Chain or tree of if-then-else statements</h2>
<p>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.</p>
<p>This was a very popular technique back in the day before the cost of a mispredicted branch became extremely high. Minimising the number of <em>difficult-to-predict</em> 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.</p>
<h2>Use a table to make the switch dense</h2>
<p>If the range of possible values isn't <em>too</em> 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:</p>
<pre class="lang-c prettyprint-override"><code>switch (x) {
    case 1:
    case 5:
        do_something();
        break;
    case 3:
    case 10:
        do_something_else();
        break;
    default:
        do_default();
        break;
}
</code></pre>
<p>could be made dense like this:</p>
<pre class="lang-c prettyprint-override"><code>static uint8_t switch_1[11] = { 2, 0, 2, 1, 2, 0, 2, 2, 2, 2, 1 };
if (x &gt; 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;
}
</code></pre>
<p>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 <em>two-level jump table</em>.</p>
<p>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:</p>
<pre class="lang-c prettyprint-override"><code>void f(uint16_t x)
{
    while (x) {
        uint16_t bit = x &amp; -x; /* Extract the least-significant set bit */
        x &amp;= ~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;
        }
    }
}
</code></pre>
<p>I'm going to use this as an archetype in the examples that follow.</p>
<h2>Split the range</h2>
<p>You could perform a top-level switch on some of the range and then a switches to discriminate between leaf cases:</p>
<pre class="lang-c prettyprint-override"><code>switch (bit &gt;&gt; 8) {
    case 0:
        switch (bit &amp; 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;
}
</code></pre>
<p>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.</p>
<h2>Arithmetic or logic transformation</h2>
<p>This doesn't always apply, but when it does, it pays off handsomely.</p>
<p>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 &quot;bit scan&quot; (e.g. <code>bsr</code> and <code>bsl</code> on x86), and others &quot;count leading/trailing zeroes&quot;, but I'm going to call it <code>floor_log_2</code> here.</p>
<p>Again, you may need to test the cases:</p>
<pre class="lang-c prettyprint-override"><code>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;
}
</code></pre>
<p>In general, you may be able to find some kind of cheap transformation which maps the sparse cases into dense cases.</p>
<h2>Branch-free binary search</h2>
<p>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.</p>
<p>This gives you a way to search a sorted array in a way that involves no branches in the &quot;loop&quot;.</p>
<p>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.</p>
<p>Now you can compile this into a branch-free binary search followed by a dense switch:</p>
<pre class="lang-c prettyprint-override"><code>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 &gt;= 0x0100) &lt;&lt; 3;

   I'm writing it out in full for exposition purposes.
*/
int j = 0;
j += (bit &gt;= jumpvalues[j + (1&lt;&lt;3)]) &lt;&lt; 3;
j += (bit &gt;= jumpvalues[j + (1&lt;&lt;2)]) &lt;&lt; 2;
j += (bit &gt;= jumpvalues[j + (1&lt;&lt;1)]) &lt;&lt; 1;
j += (bit &gt;= jumpvalues[j + (1&lt;&lt;0)]) &lt;&lt; 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:
</code></pre>
<p>If you don't have a convenient &quot;0 if false, 1 if true&quot; instruction but you do have a conditional move instruction, then the unrolled loop might be better expressed like this:</p>
<pre class="lang-c prettyprint-override"><code>int j = 0, k;
k = j + 8;  if (bit &gt;= jumpvalues[k]) j = k;
k = j + 4;  if (bit &gt;= jumpvalues[k]) j = k;
k = j + 2;  if (bit &gt;= jumpvalues[k]) j = k;
k = j + 1;  if (bit &gt;= jumpvalues[k]) j = k;
</code></pre>
<p>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?</p>
<p><strong>EDIT</strong> This originally contained a much less space-efficient flattened tree. I realised that this wasn't necessary.</p>
<h2>Bit vector rank</h2>
<p>This technique relies on having an advanced bit manipulation instruction such as Hamming weight (which I will call <code>popcount</code> here).</p>
<p>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.</p>
<p>We define the <em>rank</em> of some bit to be the number of set bits (i.e. the number of bits that are set to 1) to the <em>left</em> 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.</p>
<p>As an example, suppose we are switching on these values:</p>
<pre class="lang-c prettyprint-override"><code>switch (x) {
    case 1:
    case 2:
    case 5:
    case 10:
    case 20:
    case 50:
    case 100:
    case 200:
    case 500:
}
</code></pre>
<p>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:</p>
<pre class="lang-c prettyprint-override"><code>static const uint64_t jump_bitvector[] = {
    /* 1 &lt;&lt; 1 | 1 &lt;&lt; 2 | 1 &lt;&lt; 5 | 1 &lt;&lt; 10 | 1 &lt;&lt; 20 | 1 &lt;&lt; 50 */
    0x0004000000100426,
    /* 1 &lt;&lt; (100 - 64) */
    0x0000001000000000,
    0x0000000000000000,
    /* 1 &lt;&lt; (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
};
</code></pre>
<p>And now we can implement the switch like this:</p>
<pre class="lang-c prettyprint-override"><code>if (x &gt; 500) goto default_case;

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

if (!(jump_bitvector_word &amp; 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 &amp; (bit - 1));
switch (rank) {
   case 0: /* x == 1 */
   case 1: /* x == 2 */
   case 2: /* x == 5 */
   case 3: /* x == 10 */
   /* etc etc */
}
</code></pre>

CC BY-SA 4.0
2023-05-21T01:32:05.653Z
2023-08-16T06:22:58.133Z
2023-08-16T06:22:58.133Z
Pseudonym
CC BY-SA 4.0
2023-08-16T14:25:22.467Z
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).
Toby Speight
CC BY-SA 4.0
2023-08-16T23:43:47.973Z
@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.
Pseudonym
# How can switch statements with sparse cases be compiled?
Posted by: username_0 on 2023-05-20
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](https://en.wikipedia.org/wiki/Branch_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?
**Tags:** compilers switch-statement
---
## 3 answers
### Answer by username_2 on 2023-05-21. Score: 27 | Accepted answer
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 */
}
> **Comments:**
> **username_3** (2023-08-16): 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).  
> **username_2** (2023-08-16): @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.  
---
### Answer by username_0 on 2023-05-20. Score: 6
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](https://en.wikipedia.org/wiki/Profile-guided_optimization) 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](https://en.wikipedia.org/wiki/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.
---
### Answer by username_1 on 2023-08-16. Score: 1
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](https://en.wikipedia.org/wiki/X-fast_trie), or [Y-fast trie](https://en.wikipedia.org/wiki/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.
> **Comments:**
> **username_0** (2023-08-16): 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.  
> **username_1** (2023-08-16): @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.  
---
