How much does the order of case labels affect the efficiency of switch statements?
c, c#, c++, conditional-statements, performance
Solution
Some facts for modern hardware like x86 or x86_64:
- A unconditionally taken branch has almost no additional costs, besides the decoding. If you want a number, it's about a quarter clock cycle.
- A conditional branch, which was correctly predicted, has almost no additional costs.
- A conditional branch, which was not correctly predicted, has a penalty equal to the length of the processor pipelines, this is about 12-20 clocks, depending on the hardware.
- The prediction mechanisms are very sophisticated. Loops with a low number of iterations (on Core 2 for example up to 64) can be perfectly predicted. Small repeating patterns like "taken-taken-nottaken-taken" can be predicted, if they are not too long (IIRC 6 on Core2).
You can read more about branch prediction in Agner Fogs excellent manual.
Switch statements are usually replaced by a jump table by the compiler. In most cases the order of cases won't make a difference at all. There are prediction mechanisms for indirect jumps as well.
So the question isn't if your jumps are more likely to be taken, it is if they are well predictable, at least for the hardware you intend to run your code on. This isn't an easy question at all. But if you have branches depending on a random (or pseudo random) condition, you could try to reformulate it as a branchless statement if possible.
Problem
Consider: ``` if (condition1) { // Code block 1 } else { // Code block 2 } ``` If I know that `condition1` will be `true` the majority of the time, then I should code the logic as written, instead of: ``` if (!condition1) { // Code block 2 } else { // Code block 1 } ``` since I will avoid the penalty of the `jump` to the second code block (note: I have limited knowledge of assembly language). Does this idea carry forward to `switch` statements and `case` labels? ``` switch (myCaseValue) { case Case1: // Code block 1 break; case Case2: // Code block 2 break; // etc. } ``` If I know that one of the cases will happen more often, can I rearrange the order of the `case` labels so that it's more efficient? Should I? In my code I've been ordering the case labels alphabetically for code readability without really thinking about it. Is this micro-optimization?