Are switch-case constructs implemented as binary search?

Question

I'm wondering how a switch-case statement is implemented:

Example

say one has the following code:

Scanner sc = new Scanner(System.in);
int v = sc.nextInt();
switch(v) {
    case 0 :
        System.out.println("Zero");
        break;
    case 1 :
        System.out.println("One");
        break;
    case 2 :
        System.out.println("Two");
        break;
    //...
    default :
        System.out.println("No one digit number");
}

One can implement this as:

if(v == 0) {
    System.out.println("Zero");
}
else if(v == 1) {
    System.out.println("One");
}
else if(v == 2) {
    System.out.println("Two");
}
//...
else {
    System.out.println("No one digit number");
}

But a more efficient program is:

if(v >= 0 && v <= 9) {
    if(v <= 5) {
        if(v <= 2) {
            if(v <= 1) {
                if(v == 0) {
                    System.out.println("Zero");
                }
                else {
                    System.out.println("One");
                }
            else {
                System.out.println("Two");
            }
        }
        //...
    }
    //...
}
else {
    System.out.println("No one digit number");
}

This can be important since there are programs (like compiler compilers) that write Java/C#/C++ source code and thus generate very large switch statements.

Answer 1

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).

So the answer is, yes, sometimes, but not that simple.

It is possible to fill in "empty" case slots with default jumps to allow construction of a dense range. For small branches, or branches against non-integer values switches are rewritten as if conditionals (such as languages that allow switching on strings or regular expressions). In your example, cases for digits 0-9 would certainly be encoded as a lookup table because it is a dense group.

In all cases, binary decision trees are an important part of emitting efficient switch / case constructs.

The .NET CLR even has an opcode that accepts jumptables, and it hides the handling of the default case, this allows the runtime to validate the code as safe without full flow analysis.

Answer 2

The way switch statements are implemented depends on the 'case' list. When the set of 'case' is dense, a jump table can be used (like a goto Label[v] statement, if that existed). This is much faster than binary search.