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…
default:…
}

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?