'switch' statement efficiency in C#
-
Christian Graus wrote:
What on earth makes you think that ?
One of the books on C# stated "One intriguing point about the switch statement in C# is that the order of the cases doesn’t matter—we can even put the default case first!" This statement made me think..
scody wrote:
One of the books on C# stated "One intriguing point about the switch statement in C# is that the order of the cases doesn’t matter—we can even put the default case first!" This statement made me think..
That statement is talking about the syntax of the switch construct, not the performance. The performance is a whole different matter: The order of the case labels matters if you only have five of less of them. Then you should place the most commonly used ones first. If you have more than five case labels the switch uses a hash table, so then the order of the case labels doesn't matter at all. (I determined this by performance testing a switch in C# 3 (VS2008) targetting framework 3.5. The implementation may of course differ in older versions of the compiler or framework, but I doubt that this was ever any different.)
Despite everything, the person most likely to be fooling you next is yourself.
-
scody wrote:
but in C#, order of the 'cases' doesn’t matter.
What on earth makes you think that ? Yes, put your most common cases near the top, as they will get checked first, the MSIL for a switch is no different to a bunch of if/then/else statements. switch is just more human readable.
Christian Graus No longer a Microsoft MVP, but still happy to answer your questions.
Christian Graus wrote:
scody wrote: but in C#, order of the 'cases' doesn’t matter. What on earth makes you think that ?
What on earth makes you think it does matter?
Christian Graus wrote:
the MSIL for a switch is no different to a bunch of if/then/else statements
The MSIL for a switch is jumptable, not if/else branching. For integral types, the target offset is simply computed (not sure what happens internally), in your typical state machine fashion. For strings the behaviour could be different.
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008) -
scody wrote:
One of the books on C# stated "One intriguing point about the switch statement in C# is that the order of the cases doesn’t matter—we can even put the default case first!" This statement made me think..
That statement is talking about the syntax of the switch construct, not the performance. The performance is a whole different matter: The order of the case labels matters if you only have five of less of them. Then you should place the most commonly used ones first. If you have more than five case labels the switch uses a hash table, so then the order of the case labels doesn't matter at all. (I determined this by performance testing a switch in C# 3 (VS2008) targetting framework 3.5. The implementation may of course differ in older versions of the compiler or framework, but I doubt that this was ever any different.)
Despite everything, the person most likely to be fooling you next is yourself.
Guffa wrote:
The order of the case labels matters if you only have five of less of them. Then you should place the most commonly used ones first. If you have more than five case labels the switch uses a hash table, so then the order of the case labels doesn't matter at all.
References?
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008) -
scody wrote:
One of the books on C# stated "One intriguing point about the switch statement in C# is that the order of the cases doesn’t matter—we can even put the default case first!" This statement made me think..
That statement is talking about the syntax of the switch construct, not the performance. The performance is a whole different matter: The order of the case labels matters if you only have five of less of them. Then you should place the most commonly used ones first. If you have more than five case labels the switch uses a hash table, so then the order of the case labels doesn't matter at all. (I determined this by performance testing a switch in C# 3 (VS2008) targetting framework 3.5. The implementation may of course differ in older versions of the compiler or framework, but I doubt that this was ever any different.)
Despite everything, the person most likely to be fooling you next is yourself.
Guffa wrote:
If you have more than five case labels the switch uses a hash table, so then the order of the case labels doesn't matter at all.
Wow - I did not know that. I doubt very much that has always been the case, the C# 1.0 book I read delved into MSIL a lot and never mentioned it. I worked out this week that the TryParse methods arrived in 2.0, I suspect that sort of stuff did not come before 2.0 at least.
Christian Graus No longer a Microsoft MVP, but still happy to answer your questions.
-
Guffa wrote:
If you have more than five case labels the switch uses a hash table, so then the order of the case labels doesn't matter at all.
Wow - I did not know that. I doubt very much that has always been the case, the C# 1.0 book I read delved into MSIL a lot and never mentioned it. I worked out this week that the TryParse methods arrived in 2.0, I suspect that sort of stuff did not come before 2.0 at least.
Christian Graus No longer a Microsoft MVP, but still happy to answer your questions.
Christian Graus wrote:
Wow - I did not know that.
Yeah I just tested it. The claim is BS. It creates the same construct regardless of the number of cases. It will reorganize cases to make the lookup more efficient, but there is NO hashtable!
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008) -
Christian Graus wrote:
scody wrote: but in C#, order of the 'cases' doesn’t matter. What on earth makes you think that ?
What on earth makes you think it does matter?
Christian Graus wrote:
the MSIL for a switch is no different to a bunch of if/then/else statements
The MSIL for a switch is jumptable, not if/else branching. For integral types, the target offset is simply computed (not sure what happens internally), in your typical state machine fashion. For strings the behaviour could be different.
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)leppie wrote:
The MSIL for a switch is jumptable, not if/else branching.
If you have five or less case labels, the code generated uses if/else logic. You can easily determine this by testing the performance, and see the difference between selecting different values.
Despite everything, the person most likely to be fooling you next is yourself.
-
Christian Graus wrote:
Wow - I did not know that.
Yeah I just tested it. The claim is BS. It creates the same construct regardless of the number of cases. It will reorganize cases to make the lookup more efficient, but there is NO hashtable!
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)leppie wrote:
It creates the same construct regardless of the number of cases.
Not at all. Here is the generated code for a switch containing five case labels and one containing six case labels. Do you see the fundamental difference?
00000084 mov esi,dword ptr [ebp-44h]
00000087 test esi,esi
00000089 je 000000ED
0000008b mov edx,dword ptr ds:[02C33098h]
00000091 mov ecx,esi
00000093 call 7795C574
00000098 mov edi,eax
0000009a test edi,edi
0000009c jne 000000ED
0000009e mov edx,dword ptr ds:[02C3309Ch]
000000a4 mov ecx,esi
000000a6 call 7795C574
000000ab mov edi,eax
000000ad test edi,edi
000000af jne 000000ED
000000b1 mov edx,dword ptr ds:[02C330A0h]
000000b7 mov ecx,esi
000000b9 call 7795C574
000000be mov edi,eax
000000c0 test edi,edi
000000c2 jne 000000ED
000000c4 mov edx,dword ptr ds:[02C330A4h]
000000ca mov ecx,esi
000000cc call 7795C574
000000d1 mov edi,eax
000000d3 test edi,edi
000000d5 jne 000000ED
000000d7 mov edx,dword ptr ds:[02C330A8h]
000000dd mov ecx,esi
000000df call 7795C574
000000e4 mov edi,eax
000000e6 test edi,edi
000000e8 jne 000000ED
000000ea nop
000000eb jmp 000000ED0000008a mov ebx,dword ptr [ebp-44h]
0000008d test ebx,ebx
0000008f je 00000148
00000095 cmp dword ptr ds:[02B284BCh],0
0000009c jne 0000011F
000000a2 mov ecx,7913386Ch
000000a7 call FCAC0A5C
000000ac mov esi,eax
000000ae mov ecx,esi
000000b0 mov edx,6
000000b5 call 75929474
000000ba push 0
000000bc mov edx,dword ptr ds:[02B23098h]
000000c2 mov ecx,esi
000000c4 call 75954260
000000c9 push 1
000000cb mov edx,dword ptr ds:[02B2309Ch]
000000d1 mov ecx,esi
000000d3 call 75954260
000000d8 push 2
000000da mov edx,dword ptr ds:[02B230A0h]
000000e0 mov ecx,esi
000000e2 call 75954260
000000e7 push 3
000000e9 mov edx,dword ptr ds:[02B230A4h]
000000ef mov ecx,esi
000000f1 call 75954260
000000f6 pu -
leppie wrote:
It creates the same construct regardless of the number of cases.
Not at all. Here is the generated code for a switch containing five case labels and one containing six case labels. Do you see the fundamental difference?
00000084 mov esi,dword ptr [ebp-44h]
00000087 test esi,esi
00000089 je 000000ED
0000008b mov edx,dword ptr ds:[02C33098h]
00000091 mov ecx,esi
00000093 call 7795C574
00000098 mov edi,eax
0000009a test edi,edi
0000009c jne 000000ED
0000009e mov edx,dword ptr ds:[02C3309Ch]
000000a4 mov ecx,esi
000000a6 call 7795C574
000000ab mov edi,eax
000000ad test edi,edi
000000af jne 000000ED
000000b1 mov edx,dword ptr ds:[02C330A0h]
000000b7 mov ecx,esi
000000b9 call 7795C574
000000be mov edi,eax
000000c0 test edi,edi
000000c2 jne 000000ED
000000c4 mov edx,dword ptr ds:[02C330A4h]
000000ca mov ecx,esi
000000cc call 7795C574
000000d1 mov edi,eax
000000d3 test edi,edi
000000d5 jne 000000ED
000000d7 mov edx,dword ptr ds:[02C330A8h]
000000dd mov ecx,esi
000000df call 7795C574
000000e4 mov edi,eax
000000e6 test edi,edi
000000e8 jne 000000ED
000000ea nop
000000eb jmp 000000ED0000008a mov ebx,dword ptr [ebp-44h]
0000008d test ebx,ebx
0000008f je 00000148
00000095 cmp dword ptr ds:[02B284BCh],0
0000009c jne 0000011F
000000a2 mov ecx,7913386Ch
000000a7 call FCAC0A5C
000000ac mov esi,eax
000000ae mov ecx,esi
000000b0 mov edx,6
000000b5 call 75929474
000000ba push 0
000000bc mov edx,dword ptr ds:[02B23098h]
000000c2 mov ecx,esi
000000c4 call 75954260
000000c9 push 1
000000cb mov edx,dword ptr ds:[02B2309Ch]
000000d1 mov ecx,esi
000000d3 call 75954260
000000d8 push 2
000000da mov edx,dword ptr ds:[02B230A0h]
000000e0 mov ecx,esi
000000e2 call 75954260
000000e7 push 3
000000e9 mov edx,dword ptr ds:[02B230A4h]
000000ef mov ecx,esi
000000f1 call 75954260
000000f6 puEish, we are really splitting micro-bits here! ;P What are you case labels for either case? IMO, this JIT is way too low level to care about. Maybe doing the native layout, etc for more than 5 cases are a bit expensive. I was looking at MSIL level though, so I didnt really know (and still dont care) about what happens under those covers (but good to know none the less) :) Thanks leppie
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008) -
Eish, we are really splitting micro-bits here! ;P What are you case labels for either case? IMO, this JIT is way too low level to care about. Maybe doing the native layout, etc for more than 5 cases are a bit expensive. I was looking at MSIL level though, so I didnt really know (and still dont care) about what happens under those covers (but good to know none the less) :) Thanks leppie
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)leppie wrote:
Eish, we are really splitting micro-bits here!
Yes, but it can at least be good to know that if you have a lot of case labels, you don't have to try to order them for performance.
leppie wrote:
What are you case labels for either case?
Just labels with strings and no code, so that it tests the performance of the switch only:
switch (selection) {
case "00":
case "01":
case "02":
case "03":
case "04":
case "05":
default: break;
}(I tested it with code in the cases also, so that I know that it behaves in the same manner.) My results for a 10000000 loop for each case label, with switches having five and six case labels:
00 : 105 ms.
01 : 205 ms.
02 : 303 ms.
03 : 421 ms.
04 : 500 ms.00 : 602 ms.
01 : 605 ms.
02 : 589 ms.
03 : 622 ms.
04 : 615 ms.
05 : 577 ms.There is definitely a measurable performance difference for the first labels in the shorter switch, but even 60 ns. isn't much to whine about. :)
Despite everything, the person most likely to be fooling you next is yourself.
-
leppie wrote:
Eish, we are really splitting micro-bits here!
Yes, but it can at least be good to know that if you have a lot of case labels, you don't have to try to order them for performance.
leppie wrote:
What are you case labels for either case?
Just labels with strings and no code, so that it tests the performance of the switch only:
switch (selection) {
case "00":
case "01":
case "02":
case "03":
case "04":
case "05":
default: break;
}(I tested it with code in the cases also, so that I know that it behaves in the same manner.) My results for a 10000000 loop for each case label, with switches having five and six case labels:
00 : 105 ms.
01 : 205 ms.
02 : 303 ms.
03 : 421 ms.
04 : 500 ms.00 : 602 ms.
01 : 605 ms.
02 : 589 ms.
03 : 622 ms.
04 : 615 ms.
05 : 577 ms.There is definitely a measurable performance difference for the first labels in the shorter switch, but even 60 ns. isn't much to whine about. :)
Despite everything, the person most likely to be fooling you next is yourself.
-
I am new to C#, and have come across a situation where I need to perform different tasks based on the criteria value (string). Thought of using 'switch' statement, I know (from C++), if you order the 'case' statements according to most frequenly occuring 'cases' at the top, it will optimise the 'switch' statement (don't know for sure, but I practiced it), but in C#, order of the 'cases' doesn’t matter. In my situation, I would end up with around 50 'cases', so I would like to know if there are any other alternatives (to improve efficiency) apart from 'switch' statement? Any thought/help would be greatly appreciated.
Or you could try a Dictionary of delegates. It may at least help with maintenance issues.