Compilation Optimization for Switch Statement

Switch/case statements are implemented with a combination of binary decision trees and jump tables, depending on the case ranges.

  1. For simple switch statements (2 – 3 cases) it is often more efficient to emit simple if statement, depending on how dense the values are (1 2 3 vs 1 2 9 for example).
  2. For larger cardinality switches with a single dense group, it is common to use a jump table based directly or indirectly on the test value.
  3. With sparse groups, or mix of dense and sparse groups, binary decision trees are used to bisect the group lists and a jump table is used within the group (the leaf of tree).
Codenheim – Stack Overflow

Test Code

  • I designed 3 categories of enums (Sparse, Dense, and Mix) to test Codenheim’s statement.

Sparse Switch

void SparseSwitch(int c)
{
    enum {NUM_001 = 1,
          NUM_010 = 10,
          NUM_100 = 100,
          NUM_200 = 200};
    switch(c)
    {
        case NUM_001: break;
        case NUM_010: break;
        case NUM_100: break;
        case NUM_200: break;
    }
}


Dense Switch

void DenseSwitch(int c)
{
    enum {NUM_001 = 1,
          NUM_002 = 2,
          NUM_003 = 3, 
          NUM_004 = 4};
    switch(c)
    {
        case NUM_001: break;
        case NUM_002: break;
        case NUM_003: break;
        case NUM_004: break;
    }
}


Mix Switch

void MixSwitch(int c)
{
    enum {NUM_001 = 1,
          NUM_002 = 2,
          NUM_003 = 3,
          NUM_004 = 4,
          NUM_100 = 100};
    switch(c)
    {
        case NUM_001: break;
        case NUM_002: break;
        case NUM_003: break;
        case NUM_004: break;
        case NUM_100: break;
    }
}
  • Then I tested these codes in Compiler Explorer (godbolt.org) with clang 16.0.0 and gcc 13.1 on x86-64 architecture separately. As a result, clang 16.0.0 emits both Sparse Switch and Mix Switch to if statement, while generates Jump Table for Dense Switch; gcc 13.1 not only emits Mix Switch to if statement but also Dense Switch, and uses Binary Search strategy for Sparse Switch.

Conclusion

  • Use Switch Statement instead of If Statement whenever possible, even if the latter also has similar optimizations. However, the Time Complexity of the former is between O(1) and O(logN), while the latter is usually O(N).
  • Make the case conditions as dense as possible. In general, it’s the best practice to use enums, but you may also need modulo or hashing.

Leave a Reply

Your email address will not be published. Required fields are marked *