How Switch Case Statement Implemented or Works Internally

How Switch case Statement Implemented or works internally?

It's actually up to the compiler how a switch statement is realized in code.

However, my understanding is that when it's suitable (that is, relatively dense cases), a jump table is used.

That would mean that something like:

switch(i) {
  case 0: doZero(); break;
  case 1: doOne();
  case 2: doTwo(); break;
  default: doDefault();
}

Would end up getting compiled to something like (horrible pseudo-assembler, but it should be clear, I hope).

load i into REG
compare REG to 2
if greater, jmp to DEFAULT
compare REG to 0
if less jmp to DEFAULT
jmp to table[REG]
data table
  ZERO
  ONE
  TWO
end data
ZERO: call doZero
jmp END
ONE: call doOne
TWO: call doTwo
jmp END
DEFAULT: call doDefault
END:

If that's not the case, there are other possible implementations that allow for some extent of "better than a a sequence of conditionals".

How does Java's switch work under the hood?

Neither. it uses the lookupswitch JVM instruction, which is essentially a table lookup. Take a look at the bytecode of the following example:

public static void main(String... args) {
  switch (1) {
  case 1:
    break;
  case 2:
    break;
  }
}

public static void main(java.lang.String[]);
  Code:
   Stack=1, Locals=1, Args_size=1
   0:   iconst_1
   1:   lookupswitch{ //2
                1: 28;
                2: 31;
                default: 31 }
   28:  goto    31
   31:  return

How does switch statement work?

This is best explained by quotations from the c standard.
I am quoting the relevant parts from the standard which apply to your question here.

6.8.4.2 The switch statement

Para 4:

A switch statement causes control to jump to, into, or past the statement that is the
switch body, depending on the value of a controlling expression, and on the presence of a
default label and the values of any case labels on or in the switch body......

Para 2:

If a switch statement has an associated case or default label within the scope of an
identifier with a variably modified type, the entire switch statement shall be within the
scope of that identifier.¹⁵⁴⁾

FootNote:

¹⁵⁴⁾ That is, the declaration either precedes the switch statement, or it follows the last case or default label associated with the switch that is in the block containing the declaration.

Para 7:
EXAMPLE In the artificial program fragment

switch (expr)
{
    int i = 4;
    f(i);
    case 0:
       i = 17;
       /* falls through into default code */
    default:
       printf("%d\n", i);
}

the object whose identifier is i exists with automatic storage duration (within the block) but is never initialized, and thus if the controlling expression has a nonzero value, the call to the printf function will access an indeterminate value. Similarly, the call to the function f cannot be reached.

---

The above mentioned applies to both of the code examples in the Question.

Example 1, i has an Indeterminate value since it was never initialized & hence prints garbage, While in

Example 2, printf call is not reached because the control jumps to the matching case label.

How Switch case Statement Implemented or works internally?

It's actually up to the compiler how a switch statement is realized in code.

However, my understanding is that when it's suitable (that is, relatively dense cases), a jump table is used.

That would mean that something like:

switch(i) {
  case 0: doZero(); break;
  case 1: doOne();
  case 2: doTwo(); break;
  default: doDefault();
}

Would end up getting compiled to something like (horrible pseudo-assembler, but it should be clear, I hope).

load i into REG
compare REG to 2
if greater, jmp to DEFAULT
compare REG to 0
if less jmp to DEFAULT
jmp to table[REG]
data table
  ZERO
  ONE
  TWO
end data
ZERO: call doZero
jmp END
ONE: call doOne
TWO: call doTwo
jmp END
DEFAULT: call doDefault
END:

If that's not the case, there are other possible implementations that allow for some extent of "better than a a sequence of conditionals".

break and switch appears to execute all case statements

The reason why switch works as it does is that this:

switch(p){  
        case (1):
            x--;
        case (2):
            x = 2;
        case (3):
            x = 3;
        default:
            x++;
    }

is really just syntactic sugar for this (basically):

if (p == 1)
    goto .L1;
else if (p == 2)
    goto .L2;
else if (p == 3)
    goto .L3;
else
    goto .L4;

.L1:
    x--;
.L2:
    x = 2;
.L3:
    x = 3;
.L4:
    x++;

Java doesn't have a goto statement, but C does, and that's where it comes from. So if p is 2, it jumps to .L2 and executes all the statements following that label.

When to use a switch statement in Java

Well, switch feels "lighter" in many cases than an if/else if ladder, in my opinion. Basically you don't have that much syntax with braces and parentheses in the way of your code. That being said, switch inherits C's syntax. That means you have break and only a single scope for variables unless you introduce new blocks.

Still, the compiler is able to optimize switch statements into a lookup table and perform compile-time checking for literals when dealing with enumerations. So, I'd suggest that it's usually preferable to use switch over if/else if if you're dealing with numeric or enum types.

What is the runtime complexity of a switch statement?

It is at worst O(n). Sometimes (and this is language and compiler dependent), it translates to a jump table lookup (for "nice" switches that don't have too large a case range). Then that is O(1).

If the compiler wants to be funky, I can think of ways that the complexity can be implemented to be anything in between (e.g. perform binary search on the cases, for logn). But in practice, you're going to get eiher linear time or constant time.

Default in switch case

Probably not. Both if...else and switch...case are high-level constructs. What slows you down is the branch prediction. The better your prediction is the faster your code will run. You should put your most occurring case in first if, second in the else if and so on, just like you wrote. For switch the result depends on the internal compiler implementation which can reorder the cases despite your own order. The default should be actually reserved for the less occurring situations because rest of the conditions must be checked before falling back to default.

To conclude all this, performance-wise usage of if...else is optimal as long as you set your conditions in the correct order. Regarding switch...case it's compiler specific and depends on the applied optimizations.

Also note that switch...case is more limited than if...else since it supports only simple comparison of values.

---

Related Topics