Is the conditional operator slow?
I was looking at some code with a huge switch statement and an if-else statement on each case and instantly felt the urge to optimize. As a good developer always should do I set out to get some hard timing facts and started with three variants:
The original code looks like this:
public static bool SwitchIfElse(Key inKey, out char key, bool shift) { switch (inKey) { case Key.A: if (shift) { key = 'A'; } else { key = 'a'; } return true; case Key.B: if (shift) { key = 'B'; } else { key = 'b'; } return true; case Key.C: if (shift) { key = 'C'; } else { key = 'c'; } return true; ... case Key.Y: if (shift) { key = 'Y'; } else { key = 'y'; } return true; case Key.Z: if (shift) { key = 'Z'; } else { key = 'z'; } return true; ... //some more cases with special keys... } key = (char)0; return false; }The second variant converted to use the conditional operator:
public static bool SwitchConditionalOperator(Key inKey, out char key, bool shift) { switch (inKey) { case Key.A: key = shift ? 'A' : 'a'; return true; case Key.B: key = shift ? 'B' : 'b'; return true; case Key.C: key = shift ? 'C' : 'c'; return true; ... case Key.Y: key = shift ? 'Y' : 'y'; return true; case Key.Z: key = shift ? 'Z' : 'z'; return true; ... //some more cases with special keys... } key = (char)0; return false; }A twist using a dictionary pre-filled with key/character pairs:
public static bool DictionaryLookup(Key inKey, out char key, bool shift) { key = '\0'; if (shift) return _upperKeys.TryGetValue(inKey, out key); else return _lowerKeys.TryGetValue(inKey, out key); }
Note: the two switch statements have the exact same cases and the dictionaries have an equal amount of characters.
I was expecting that 1) and 2) was somewhat similar in performance and that 3) would be slightly slower.
For each method running two times 10.000.000 iterations for warm-up and then timed, to my amazement I get the following results:
- 0.0000166 milliseconds per call
- 0.0000779 milliseconds per call
- 0.0000413 milliseconds per call
How can this be? The conditional operator is four times slower than if-else statements and almost two times slower than dictionary look-ups. Am I missing something essential here or is the conditional operator inherently slow?
Update 1: A few words about my test harness. I run the following (pseudo)code for each of the above variants under a Release compiled .Net 3.5 project in Visual Studio 2010. Code optimization is turned on an开发者_运维技巧d DEBUG/TRACE constants are turned off. I run the method under measurement once for warm-up before doing a timed run. The run method executed the method for a large number of iterations, with shift set to both true and false and with a select set of input keys:
Run(method);
var stopwatch = Stopwatch.StartNew();
Run(method);
stopwatch.Stop();
var measure = stopwatch.ElapsedMilliseconds / iterations;
The Run method looks like this:
for (int i = 0; i < iterations / 4; i++)
{
method(Key.Space, key, true);
method(Key.A, key, true);
method(Key.Space, key, false);
method(Key.A, key, false);
}
Update 2: Digging further, I have looked at the IL generated for 1) and 2) and find that the main switch structures are identical as I would expect, yet the case bodies have slight differences. Here is the IL I'm looking at:
1) If/else statement:
L_0167: ldarg.2
L_0168: brfalse.s L_0170
L_016a: ldarg.1
L_016b: ldc.i4.s 0x42
L_016d: stind.i2
L_016e: br.s L_0174
L_0170: ldarg.1
L_0171: ldc.i4.s 0x62
L_0173: stind.i2
L_0174: ldc.i4.1
L_0175: ret
2) The Conditional Operator:
L_0165: ldarg.1
L_0166: ldarg.2
L_0167: brtrue.s L_016d
L_0169: ldc.i4.s 0x62
L_016b: br.s L_016f
L_016d: ldc.i4.s 0x42
L_016f: stind.i2
L_0170: ldc.i4.1
L_0171: ret
Some observations:
- The conditional operator branches when
shiftequals true while if/else branches whenshiftis false. - While 1) actually compiles to a few more instructions than 2), the number of instructions executed when
shiftis either true or false, are equal for the two. - The instruction ordering for 1) is such that only one stack slot is occupied at all times, while 2) always loads two.
Do any of these observations imply that the conditional operator will perform slower? Is there other side-effects that come into play?
Very odd, perhaps .NET optimization is backfireing in your case:
The author disassembled several versions of ternary expressions and found that they are identical to if-statements, with one small difference. The ternary statement sometimes produces code that tests the opposite condition that you would expect, as in it tests that the subexpression is false instead of testing if it is true. This reorders some of the instructions and can occasionally boost performance.
http://dotnetperls.com/ternary
You want might consider the ToString on the enum value (for the non-special cases):
string keyValue = inKey.ToString();
return shift ? keyValue : keyValue.ToLower();
EDIT:
I've compared the if-else method with the ternary operator and with 1000000 cycles the ternary operator is always at least as fast as the if-else method (sometimes a few millisec faster, which supports the text above). I think that you've made somekind of error in measuring the time it took.
I would be curious to know if you are testing this with a Debug or Release build. If it is a debug build, then the difference could quite likely be a difference due to the LACK of low-level optimizations that the compiler adds when you use Release mode (or manually disable debug mode and enable compiler optimizations.)
I would expect with optimizations on, however, that the ternary operator is either the same speed or a bit faster than the if/else statement, while the dictionary lookup is slowest. Here are my results, 10 million warm-up iterations followed by 10 million timed, for each:
DEBUG MODE
If/Else: 00:00:00.7211259
Ternary: 00:00:00.7923924
Dictionary: 00:00:02.3319567
RELEASE MODE
If/Else: 00:00:00.5217478
Ternary: 00:00:00.5050474
Dictionary: 00:00:02.7389423
I think it is interesting to note here that before optimizations were enabled, ternary computation was slower than if/else, while after, it was faster.
EDIT:
After a bit more testing, in a practical sense, there is little to no difference between if/else and ternary. While the ternary code results in smaller IL, they perform pretty much the same as each other. In a dozen different tests with a release mode binary, the if/else and ternary results were either identical, or off by a fraction of a millisecond for 10,000,000 iterations. Sometimes if/else was slightly faster, sometimes ternary was, but in all practicality, they perform the same.
Dictionary performs significantly worse, on the other hand. When it comes to these kinds of optimizations, I would not waste my time choosing between if/else and ternary if the code already exists. However, if you currently have a dictionary implementation, I would definitely refactor it to use a more efficient approach, and improve your performance by some 400% (for the given function, anyway.)
Interesting, I went off and developed a small class IfElseTernaryTest here, ok, the code is not really 'optimized' or good example but nonetheless...for the sake of the discussion:
public class IfElseTernaryTest
{
private bool bigX;
public void RunIfElse()
{
int x = 4; int y = 5;
if (x > y) bigX = false;
else if (x < y) bigX = true;
}
public void RunTernary()
{
int x = 4; int y = 5;
bigX = (x > y) ? false : ((x < y) ? true : false);
}
}
This was the IL dump of the code...the interesting part was that the ternary instructions in IL was actually shorter than the if....
.class /*02000003*/ public auto ansi beforefieldinit ConTern.IfElseTernaryTest
extends [mscorlib/*23000001*/]System.Object/*01000001*/
{
.field /*04000001*/ private bool bigX
.method /*06000003*/ public hidebysig instance void
RunIfElse() cil managed
// SIG: 20 00 01
{
// Method begins at RVA 0x205c
// Code size 44 (0x2c)
.maxstack 2
.locals /*11000001*/ init ([0] int32 x,
[1] int32 y,
[2] bool CS$4$0000)
.line 19,19 : 9,10 ''
//000013: }
//000014:
//000015: public class IfElseTernaryTest
//000016: {
//000017: private bool bigX;
//000018: public void RunIfElse()
//000019: {
IL_0000: /* 00 | */ nop
.line 20,20 : 13,23 ''
//000020: int x = 4; int y = 5;
IL_0001: /* 1A | */ ldc.i4.4
IL_0002: /* 0A | */ stloc.0
.line 20,20 : 24,34 ''
IL_0003: /* 1B | */ ldc.i4.5
IL_0004: /* 0B | */ stloc.1
.line 21,21 : 13,23 ''
//000021: if (x > y) bigX = false;
IL_0005: /* 06 | */ ldloc.0
IL_0006: /* 07 | */ ldloc.1
IL_0007: /* FE02 | */ cgt
IL_0009: /* 16 | */ ldc.i4.0
IL_000a: /* FE01 | */ ceq
IL_000c: /* 0C | */ stloc.2
IL_000d: /* 08 | */ ldloc.2
IL_000e: /* 2D | 09 */ brtrue.s IL_0019
.line 21,21 : 24,37 ''
IL_0010: /* 02 | */ ldarg.0
IL_0011: /* 16 | */ ldc.i4.0
IL_0012: /* 7D | (04)000001 */ stfld bool ConTern.IfElseTernaryTest/*02000003*/::bigX /* 04000001 */
IL_0017: /* 2B | 12 */ br.s IL_002b
.line 22,22 : 18,28 ''
//000022: else if (x < y) bigX = true;
IL_0019: /* 06 | */ ldloc.0
IL_001a: /* 07 | */ ldloc.1
IL_001b: /* FE04 | */ clt
IL_001d: /* 16 | */ ldc.i4.0
IL_001e: /* FE01 | */ ceq
IL_0020: /* 0C | */ stloc.2
IL_0021: /* 08 | */ ldloc.2
IL_0022: /* 2D | 07 */ brtrue.s IL_002b
.line 22,22 : 29,41 ''
IL_0024: /* 02 | */ ldarg.0
IL_0025: /* 17 | */ ldc.i4.1
IL_0026: /* 7D | (04)000001 */ stfld bool ConTern.IfElseTernaryTest/*02000003*/::bigX /* 04000001 */
.line 23,23 : 9,10 ''
//000023: }
IL_002b: /* 2A | */ ret
} // end of method IfElseTernaryTest::RunIfElse
.method /*06000004*/ public hidebysig instance void
RunTernary() cil managed
// SIG: 20 00 01
{
// Method begins at RVA 0x2094
// Code size 27 (0x1b)
.maxstack 3
.locals /*11000002*/ init ([0] int32 x,
[1] int32 y)
.line 25,25 : 9,10 ''
//000024: public void RunTernary()
//000025: {
IL_0000: /* 00 | */ nop
.line 26,26 : 13,23 ''
//000026: int x = 4; int y = 5;
IL_0001: /* 1A | */ ldc.i4.4
IL_0002: /* 0A | */ stloc.0
.line 26,26 : 24,34 ''
IL_0003: /* 1B | */ ldc.i4.5
IL_0004: /* 0B | */ stloc.1
.line 27,27 : 13,63 ''
//000027: bigX = (x > y) ? false : ((x < y) ? true : false);
IL_0005: /* 02 | */ ldarg.0
IL_0006: /* 06 | */ ldloc.0
IL_0007: /* 07 | */ ldloc.1
IL_0008: /* 30 | 0A */ bgt.s IL_0014
IL_000a: /* 06 | */ ldloc.0
IL_000b: /* 07 | */ ldloc.1
IL_000c: /* 32 | 03 */ blt.s IL_0011
IL_000e: /* 16 | */ ldc.i4.0
IL_000f: /* 2B | 01 */ br.s IL_0012
IL_0011: /* 17 | */ ldc.i4.1
IL_0012: /* 2B | 01 */ br.s IL_0015
IL_0014: /* 16 | */ ldc.i4.0
IL_0015: /* 7D | (04)000001 */ stfld bool ConTern.IfElseTernaryTest/*02000003*/::bigX /* 04000001 */
.line 28,28 : 9,10 ''
//000028: }
IL_001a: /* 2A | */ ret
} // end of method IfElseTernaryTest::RunTernary
So it seems, that ternary operator is apparently shorter and I would guess, faster as less instructions is used...but on that basis, it seems to contradict your case #2 which is surprising...
Edit: After Sky's comment, suggesting 'code bloat for #2', this will disprove what Sky said!!! Ok, the Code is different, the context is different, it's an example exercise to check the IL dump to see...
I would expect #1 and #2 to be the same. The optimizer should result in the same code. The dictionary in #3 would expected to be slow, unless it is optimized somehow to not actual use a hash.
When coding real-time systems, we always used a look-up table--a simple array--to translate as given in your example. It's the fastest when the range of input is fairly small.
I don't quite understand why you would expect an if statement to be slower than a dictionary lookup. At the very least a hashcode needs to be calculated and then it needs to be looked up in a list. I don't see why you would assume this is faster than a cmp/jmp.
Specifically, I don't even think the method you're optimising is that great; it seems that it could be made better at the calling stage (though I can't be sure, as you haven't provided the context).
Assuming you're concerned about the performance of that method (and if you're not, why bother posting it?), you should consider storing the char values in an array and converting the Key values to an index into the array.
I don't have VS to hand but surely there's a simple built-in way to get the key as a character? Something like a toString method so you can replace that monstrous switch with this:
if (shift)
return inKey.toString().toUppercase();
else
return inKey.toString().toLowercase();
I would choose the third option only because it is more readable/maintainable. I bet this code isn't the bottleneck of your application performance.
加载中,请稍侯......
精彩评论