It’s important not to confuse the C# switch statement with the CIL switch instruction.
The CIL switch is a jump table, that requires an index into a set of jump addresses.
This is only useful if the C# switch’s cases are adjacent:
case 3: blah; break;
case 4: blah; break;
case 5: blah; break;
But of little use if they aren’t:
case 10: blah; break;
case 200: blah; break;
case 3000: blah; break;
(You’d need a table ~3000 entries in size, with only 3 slots used)
With non-adjacent expressions, the compiler may start to perform linear if-else-if-else checks.
With larger non- adjacent expression sets, the compiler may start with a binary tree search, and finally if-else-if-else the last few items.
With expression sets containing clumps of adjacent items, the compiler may binary tree search, and finally a CIL switch.
This is full of “mays” & “mights”, and it is dependent on the compiler (may differ with Mono or Rotor).
I replicated your results on my machine using adjacent cases:
total time to execute a 10 way switch, 10000 iterations (ms) : 25.1383
approximate time per 10 way switch (ms) : 0.00251383total time to execute a 50 way switch, 10000 iterations (ms) : 26.593
approximate time per 50 way switch (ms) : 0.0026593total time to execute a 5000 way switch, 10000 iterations (ms) : 23.7094
approximate time per 5000 way switch (ms) : 0.00237094total time to execute a 50000 way switch, 10000 iterations (ms) : 20.0933
approximate time per 50000 way switch (ms) : 0.00200933
Then I also did using non-adjacent case expressions:
total time to execute a 10 way switch, 10000 iterations (ms) : 19.6189
approximate time per 10 way switch (ms) : 0.00196189total time to execute a 500 way switch, 10000 iterations (ms) : 19.1664
approximate time per 500 way switch (ms) : 0.00191664total time to execute a 5000 way switch, 10000 iterations (ms) : 19.5871
approximate time per 5000 way switch (ms) : 0.00195871A non-adjacent 50,000 case switch statement would not compile.
“An expression is too long or complex to compile near ‘ConsoleApplication1.Program.Main(string[])’
What’s funny here, is that the binary tree search appears a little (probably not statistically) quicker than the CIL switch instruction.
Brian, you’ve used the word “constant“, which has a very definite meaning from a computational complexity theory perspective. While the simplistic adjacent integer example may produce CIL that is considered O(1) (constant), a sparse example is O(log n) (logarithmic), clustered examples lie somewhere in between, and small examples are O(n) (linear).
This doesn’t even address the String situation, in which a static Generic.Dictionary<string,int32> may be created, and will suffer definite overhead on first use. Performance here will be dependent on the performance of Generic.Dictionary.
If you check the C# Language Specification (not the CIL spec)
you’ll find “15.7.2 The switch statement” makes no mention of “constant time” or that the underlying implementation even uses the CIL switch instruction (be very careful of assuming such things).
At the end of the day, a C# switch against an integer expression on a modern system is a sub-microsecond operation, and not normally worth worrying about.
Of course these times will depend on machines and conditions. I wouldn’t pay attention to these timing tests, the microsecond durations we’re talking about are dwarfed by any “real” code being run (and you must include some “real code” otherwise the compiler will optimise the branch away), or jitter in the system. My answers are based on using IL DASM to examine the CIL created by the C# compiler. Of course, this isn’t final, as the actual instructions the CPU runs are then created by the JIT.
I have checked the final CPU instructions actually executed on my x86 machine, and can confirm a simple adjacent set switch doing something like:
jmp ds:300025F0[eax*4]
Where a binary tree search is full of:
cmp ebx, 79Eh
jg 3000352B
cmp ebx, 654h
jg 300032BB
…
cmp ebx, 0F82h
jz 30005EEE