switches and jump tables

In my last post I had discussed about how only constants can be used with C# switches. From the post's comments and later discussing with other folks I learnt something that came to me as a surprise. A lot of people working on managed code consider switch-case to be a stylistic variant of if-else, and that is all.

However, in the C/C++ world switch is not just a variant of if-else (neither is it in .NET), it's a fast (O(1)) variant of if-else (O(n)). Stating that switch is just a better way to express multiple comparison against the same variable is stating Dictionary<T> is just another form of List<T>. They are not (Dictionary can give you O(1) lookup results). 

For example C restricts the case to have constant-expression. This is done so that the compiler can generate optimized jump-table for its execution. Let's consider the following code.

switch(i) {
case 4:...
case 5:...
case 6:...
case 7:...
// many more cases...

For this code the machine code generated is similar to the steps below.

  1. Compile time jump table creation: For each case statement a fixed block of memory is reserved. Say 8 bytes. These 8 bytes contain a jump (jmp) instruction to the location where the actual code for the case resides. The base address of this table is labeled as say JMPTABLEBASE.

  2. Normalizes the value of i as i = i - 4 (the first value of the case) 

  3. Boundary check: For the i it sees if the value is larger than the largest case (7-4 = 3), in case it is the execution flows to default.

  4. Jump to address JMPTABLEBASE + (i * 8)

As you can see from above the whole thing happens at constant time.

Some embedded C compilers (like the TI C-compiler) generates separate code section named .switch for the jumptable. Later this section can be targetted to the high-speed internal DARAM for faster execution in case the switch needs such special treatment.

Obviously compilers vary a lot in this manner

Comments (2)
  1. Sreejith A says:

    What if the value of i are in wequential order..will the jump table be craeated…if so how is the indexing done?

  2. Sreejith A says:

    sorry the above query may not be readable..

    The actual query is :

    What if the value of i are in sequential order..will the jump table be created…if so how is the indexing done?

Comments are closed.

Skip to main content