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.
- 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.
- Normalizes the value of i as i = i - 4 (the first value of the case)
- 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.
- 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
