Ternary operator is twice as slow as an if-else block?
C#PerformanceConditional OperatorC# Problem Overview
I read everywhere that ternary operator is supposed to be faster than, or at least the same as, its equivalent if-else block.
However, I did the following test and found out it's not the case:
Random r = new Random();
int[] array = new int[20000000];
for(int i = 0; i < array.Length; i++)
{
array[i] = r.Next(int.MinValue, int.MaxValue);
}
Array.Sort(array);
long value = 0;
DateTime begin = DateTime.UtcNow;
foreach (int i in array)
{
if (i > 0)
{
value += 2;
}
else
{
value += 3;
}
// if-else block above takes on average 85 ms
// OR I can use a ternary operator:
// value += i > 0 ? 2 : 3; // takes 157 ms
}
DateTime end = DateTime.UtcNow;
MessageBox.Show("Measured time: " + (end-begin).TotalMilliseconds + " ms.\r\nResult = " + value.ToString());
My computer took 85 ms to run the code above. But if I comment out the if-else chunk, and uncomment the ternary operator line, it will take about 157 ms.
Why is this happening?
C# Solutions
Solution 1 - C#
To answer this question, we'll examine the assembly code produced by the X86 and X64 JITs for each of these cases.
X86, if/then
32: foreach (int i in array)
0000007c 33 D2 xor edx,edx
0000007e 83 7E 04 00 cmp dword ptr [esi+4],0
00000082 7E 1C jle 000000A0
00000084 8B 44 96 08 mov eax,dword ptr [esi+edx*4+8]
33: {
34: if (i > 0)
00000088 85 C0 test eax,eax
0000008a 7E 08 jle 00000094
35: {
36: value += 2;
0000008c 83 C3 02 add ebx,2
0000008f 83 D7 00 adc edi,0
00000092 EB 06 jmp 0000009A
37: }
38: else
39: {
40: value += 3;
00000094 83 C3 03 add ebx,3
00000097 83 D7 00 adc edi,0
0000009a 42 inc edx
32: foreach (int i in array)
0000009b 39 56 04 cmp dword ptr [esi+4],edx
0000009e 7F E4 jg 00000084
30: for (int x = 0; x < iterations; x++)
000000a0 41 inc ecx
000000a1 3B 4D F0 cmp ecx,dword ptr [ebp-10h]
000000a4 7C D6 jl 0000007C
X86, ternary
59: foreach (int i in array)
00000075 33 F6 xor esi,esi
00000077 83 7F 04 00 cmp dword ptr [edi+4],0
0000007b 7E 2D jle 000000AA
0000007d 8B 44 B7 08 mov eax,dword ptr [edi+esi*4+8]
60: {
61: value += i > 0 ? 2 : 3;
00000081 85 C0 test eax,eax
00000083 7F 07 jg 0000008C
00000085 BA 03 00 00 00 mov edx,3
0000008a EB 05 jmp 00000091
0000008c BA 02 00 00 00 mov edx,2
00000091 8B C3 mov eax,ebx
00000093 8B 4D EC mov ecx,dword ptr [ebp-14h]
00000096 8B DA mov ebx,edx
00000098 C1 FB 1F sar ebx,1Fh
0000009b 03 C2 add eax,edx
0000009d 13 CB adc ecx,ebx
0000009f 89 4D EC mov dword ptr [ebp-14h],ecx
000000a2 8B D8 mov ebx,eax
000000a4 46 inc esi
59: foreach (int i in array)
000000a5 39 77 04 cmp dword ptr [edi+4],esi
000000a8 7F D3 jg 0000007D
57: for (int x = 0; x < iterations; x++)
000000aa FF 45 E4 inc dword ptr [ebp-1Ch]
000000ad 8B 45 E4 mov eax,dword ptr [ebp-1Ch]
000000b0 3B 45 F0 cmp eax,dword ptr [ebp-10h]
000000b3 7C C0 jl 00000075
X64, if/then
32: foreach (int i in array)
00000059 4C 8B 4F 08 mov r9,qword ptr [rdi+8]
0000005d 0F 1F 00 nop dword ptr [rax]
00000060 45 85 C9 test r9d,r9d
00000063 7E 2B jle 0000000000000090
00000065 33 D2 xor edx,edx
00000067 45 33 C0 xor r8d,r8d
0000006a 4C 8B 57 08 mov r10,qword ptr [rdi+8]
0000006e 66 90 xchg ax,ax
00000070 42 8B 44 07 10 mov eax,dword ptr [rdi+r8+10h]
33: {
34: if (i > 0)
00000075 85 C0 test eax,eax
00000077 7E 07 jle 0000000000000080
35: {
36: value += 2;
00000079 48 83 C5 02 add rbp,2
0000007d EB 05 jmp 0000000000000084
0000007f 90 nop
37: }
38: else
39: {
40: value += 3;
00000080 48 83 C5 03 add rbp,3
00000084 FF C2 inc edx
00000086 49 83 C0 04 add r8,4
32: foreach (int i in array)
0000008a 41 3B D2 cmp edx,r10d
0000008d 7C E1 jl 0000000000000070
0000008f 90 nop
30: for (int x = 0; x < iterations; x++)
00000090 FF C1 inc ecx
00000092 41 3B CC cmp ecx,r12d
00000095 7C C9 jl 0000000000000060
X64, ternary
59: foreach (int i in array)
00000044 4C 8B 4F 08 mov r9,qword ptr [rdi+8]
00000048 45 85 C9 test r9d,r9d
0000004b 7E 2F jle 000000000000007C
0000004d 45 33 C0 xor r8d,r8d
00000050 33 D2 xor edx,edx
00000052 4C 8B 57 08 mov r10,qword ptr [rdi+8]
00000056 8B 44 17 10 mov eax,dword ptr [rdi+rdx+10h]
60: {
61: value += i > 0 ? 2 : 3;
0000005a 85 C0 test eax,eax
0000005c 7F 07 jg 0000000000000065
0000005e B8 03 00 00 00 mov eax,3
00000063 EB 05 jmp 000000000000006A
00000065 B8 02 00 00 00 mov eax,2
0000006a 48 63 C0 movsxd rax,eax
0000006d 4C 03 E0 add r12,rax
00000070 41 FF C0 inc r8d
00000073 48 83 C2 04 add rdx,4
59: foreach (int i in array)
00000077 45 3B C2 cmp r8d,r10d
0000007a 7C DA jl 0000000000000056
57: for (int x = 0; x < iterations; x++)
0000007c FF C1 inc ecx
0000007e 3B CD cmp ecx,ebp
00000080 7C C6 jl 0000000000000048
First: why is the X86 code so much slower than X64?
This is due to the following characteristics of the code:
- X64 has several additional registers available, and each register is 64-bits. This allows the X64 JIT to perform the inner loop entirely using registers aside from loading
ifrom the array, while the X86 JIT places several stack operations (memory access) in the loop. valueis a 64-bit integer, which requires 2 machine instructions on X86 (addfollowed byadc) but only 1 on X64 (add).
Second: why is the ternary operator slower on both X86 and X64?
This is due to a subtle difference in the order of operations impacting the JIT's optimizer. To JIT the ternary operator, rather than directly coding 2 and 3 in the add machine instructions themselves, the JIT creating an intermediate variable (in a register) to hold the result. This register is then sign-extended from 32-bits to 64-bits before adding it to value. Since all of this is performed in registers for X64, despite the significant increase in complexity for the ternary operator the net impact is somewhat minimized.
The X86 JIT on the other hand is impacted to a greater extent because the addition of a new intermediate value in the inner loop causes it to "spill" another value, resulting in at least 2 additional memory accesses in the inner loop (see the accesses to [ebp-14h] in the X86 ternary code).
Solution 2 - C#
EDIT: All change... see below.
I can't reproduce your results on the x64 CLR, but I can on x86. On x64 I can see a small difference (less than 10%) between the conditional operator and the if/else, but it's much smaller than you're seeing.
I've made the following potential changes:
- Run in a console app
- Build with
/o+ /debug-, and run outside the debugger - Run both pieces of code once to JIT them, then lots of times for more accuracy
- Use
Stopwatch
Results with /platform:x64 (without the "ignore" lines):
if/else with 1 iterations: 17ms
conditional with 1 iterations: 19ms
if/else with 1000 iterations: 17875ms
conditional with 1000 iterations: 19089ms
Results with /platform:x86 (without the "ignore" lines):
if/else with 1 iterations: 18ms
conditional with 1 iterations: 49ms
if/else with 1000 iterations: 17901ms
conditional with 1000 iterations: 47710ms
My system details:
- x64 i7-2720QM CPU @2.20GHz
- 64-bit Windows 8
- .NET 4.5
So unlike before, I think you are seeing a real difference - and it's all to do with the x86 JIT. I wouldn't like to say exactly what is causing the difference - I may update the post later on with more details if I can bother to go into cordbg :)
Interestingly, without sorting the array first, I end up with tests which take about 4.5x as long, at least on x64. My guess is that this is to do with branch prediction.
Code:
using System;
using System.Diagnostics;
class Test
{
static void Main()
{
Random r = new Random(0);
int[] array = new int[20000000];
for(int i = 0; i < array.Length; i++)
{
array[i] = r.Next(int.MinValue, int.MaxValue);
}
Array.Sort(array);
// JIT everything...
RunIfElse(array, 1);
RunConditional(array, 1);
// Now really time it
RunIfElse(array, 1000);
RunConditional(array, 1000);
}
static void RunIfElse(int[] array, int iterations)
{
long value = 0;
Stopwatch sw = Stopwatch.StartNew();
for (int x = 0; x < iterations; x++)
{
foreach (int i in array)
{
if (i > 0)
{
value += 2;
}
else
{
value += 3;
}
}
}
sw.Stop();
Console.WriteLine("if/else with {0} iterations: {1}ms",
iterations,
sw.ElapsedMilliseconds);
// Just to avoid optimizing everything away
Console.WriteLine("Value (ignore): {0}", value);
}
static void RunConditional(int[] array, int iterations)
{
long value = 0;
Stopwatch sw = Stopwatch.StartNew();
for (int x = 0; x < iterations; x++)
{
foreach (int i in array)
{
value += i > 0 ? 2 : 3;
}
}
sw.Stop();
Console.WriteLine("conditional with {0} iterations: {1}ms",
iterations,
sw.ElapsedMilliseconds);
// Just to avoid optimizing everything away
Console.WriteLine("Value (ignore): {0}", value);
}
}
Solution 3 - C#
The difference really doesn't have much to do with if/else vs ternary.
Looking at the jitted disassemblies (I won't repaste here, pls see @280Z28's answer), it turns out you're comparing apples and oranges. In one case, you create two different += operations with constant values and which one you pick depends on a condition, and in the other case, you create a += where the value to add depends on a condition.
If you want to truly compare if/else vs ternary, this would be a more fair comparison (now both will be equally "slow", or we could even say ternary is a bit faster):
int diff;
if (i > 0)
diff = 2;
else
diff = 3;
value += diff;
vs.
value += i > 0 ? 2 : 3;
Now the disassembly for the if/else becomes as shown below. Note that this is bit worse than the ternary case, since it quit using the registers for the loop variable(i) as well.
if (i > 0)
0000009d cmp dword ptr [ebp-20h],0
000000a1 jle 000000AD
{
diff = 2;
000000a3 mov dword ptr [ebp-24h],2
000000aa nop
000000ab jmp 000000B4
}
else
{
diff = 3;
000000ad mov dword ptr [ebp-24h],3
}
value += diff;
000000b4 mov eax,dword ptr [ebp-18h]
000000b7 mov edx,dword ptr [ebp-14h]
000000ba mov ecx,dword ptr [ebp-24h]
000000bd mov ebx,ecx
000000bf sar ebx,1Fh
000000c2 add eax,ecx
000000c4 adc edx,ebx
000000c6 mov dword ptr [ebp-18h],eax
000000c9 mov dword ptr [ebp-14h],edx
000000cc inc dword ptr [ebp-28h]
Solution 4 - C#
Edit:
Added an example which can be done with the if-else statement but not the conditional operator.
Before the answer, please have a look of [Which is faster?] on Mr. Lippert's blog. And I think Mr. Ersönmez's answer is the most correct one here.
I'm trying to mention something we should keep in mind with a high-level programming language.
First off, I've never heard that the conditional operator is supposed to be faster or the equally performance with if-else statement in C♯.
The reason is simple that what if there's no operation with the if-else statement:
if (i > 0)
{
value += 2;
}
else
{
}
The requirement of conditional operator is there must be a value with either side, and in C♯ it also requires that both side of : has the same type. This just makes it different from the if-else statement. Thus your question becomes a question asking how the instruction of the machine code is generated so that the difference of performance.
With the conditional operator, semantically it is:
Whatever the expression is evaluated, there's a value.
But with if-else statement:
If the expression is evaluated to true, do something; if not, do another thing.
A value is not necessarily involved with if-else statement. Your assumption is only possible with optimization.
Another example to demonstrate the difference between them would be like the following:
var array1=new[] { 1, 2, 3 };
var array2=new[] { 5, 6, 7 };
if(i>0)
array1[1]=4;
else
array2[2]=4;
the code above compiles, however, replace if-else statement with the conditional operator just won't compile:
var array1=new[] { 1, 2, 3 };
var array2=new[] { 5, 6, 7 };
(i>0?array1[1]:array2[2])=4; // incorrect usage
The conditional operator and the if-else statements are conceptual the same when you do the same thing, it possibly even faster with the conditional operator in C, since C is more closer to the assembly of the platform.
For the original code you provided, the conditional operator is used in a foreach-loop, which would mess things up to see the difference between them. So I'm proposing the following code:
public static class TestClass {
public static void TestConditionalOperator(int i) {
long value=0;
value+=i>0?2:3;
}
public static void TestIfElse(int i) {
long value=0;
if(i>0) {
value+=2;
}
else {
value+=3;
}
}
public static void TestMethod() {
TestConditionalOperator(0);
TestIfElse(0);
}
}
and the following are two version of the IL of optimized and not. Since they are long, I'm using an image to show, the right hand side is the optimized one:
> (Click to see full-size image.)
>
In both version of code, the IL of the conditional operator looks shorter than the if-else statement, and there still is a doubt of the machine code finally generated. The following are the instructions of both method, and the former image is non-optimized, the latter is the optimized one:
-
Non-optimized instructions: (Click to see full-size image.)
-
Optimized instructions: (Click to see full-size image.)
In the latter, the yellow block is the code only executed if i<=0, and the blue block is when i>0. In either version of instructions, the if-else statement is shorter.
Note that, for different instructions, the [CPI] is not necessarily the same. Logically, for the identical instruction, more instructions cost longer cycle. But if the instruction fetching time and pipe/cache were also take into account, then the real total time of execution depends on the processor. The processor can also predict the branches.
Modern processors have even more cores, things can be more complex with that. If you were an Intel processor user, you might want to have a look of [Intel® 64 and IA-32 Architectures Optimization Reference Manual].
I don't know if there was a hardware-implemented CLR, but if yes, you probably get faster with conditional operator because the IL is obviously lesser.
Note: All the machine code are of x86.
Solution 5 - C#
I did what Jon Skeet did and ran through 1 iteration and 1,000 iterations and got a different result from both OP and Jon. In mine, the ternary is just slightly faster. Below is the exact code:
static void runIfElse(int[] array, int iterations)
{
long value = 0;
Stopwatch ifElse = new Stopwatch();
ifElse.Start();
for (int c = 0; c < iterations; c++)
{
foreach (int i in array)
{
if (i > 0)
{
value += 2;
}
else
{
value += 3;
}
}
}
ifElse.Stop();
Console.WriteLine(String.Format("Elapsed time for If-Else: {0}", ifElse.Elapsed));
}
static void runTernary(int[] array, int iterations)
{
long value = 0;
Stopwatch ternary = new Stopwatch();
ternary.Start();
for (int c = 0; c < iterations; c++)
{
foreach (int i in array)
{
value += i > 0 ? 2 : 3;
}
}
ternary.Stop();
Console.WriteLine(String.Format("Elapsed time for Ternary: {0}", ternary.Elapsed));
}
static void Main(string[] args)
{
Random r = new Random();
int[] array = new int[20000000];
for (int i = 0; i < array.Length; i++)
{
array[i] = r.Next(int.MinValue, int.MaxValue);
}
Array.Sort(array);
long value = 0;
runIfElse(array, 1);
runTernary(array, 1);
runIfElse(array, 1000);
runTernary(array, 1000);
Console.ReadLine();
}
The output from my program: >Elapsed time for If-Else: 00:00:00.0140543 > >Elapsed time for Ternary: 00:00:00.0136723 > >Elapsed time for If-Else: 00:00:14.0167870 > >Elapsed time for Ternary: 00:00:13.9418520
Another run in milliseconds:
>Elapsed time for If-Else: 20 > >Elapsed time for Ternary: 19 > >Elapsed time for If-Else: 13854 > >Elapsed time for Ternary: 13610
This is running in 64-bit XP, and I ran without debugging.
Edit - Running in x86:
There's a big difference using x86. This was done without debugging on and on the same xp 64-bit machine as before, but built for x86 CPUs. This looks more like OP's.
>Elapsed time for If-Else: 18 > >Elapsed time for Ternary: 35 > >Elapsed time for If-Else: 20512 > >Elapsed time for Ternary: 32673
Solution 6 - C#
The assembler code generated will tell the story:
a = (b > c) ? 1 : 0;
Generates:
mov edx, DWORD PTR a[rip]
mov eax, DWORD PTR b[rip]
cmp edx, eax
setg al
Whereas:
if (a > b) printf("a");
else printf("b");
Generates:
mov edx, DWORD PTR a[rip]
mov eax, DWORD PTR b[rip]
cmp edx, eax
jle .L4
;printf a
jmp .L5
.L4:
;printf b
.L5:
So the ternary can be shorter and faster simply due to using fewer instructions and no jumps if you are looking for true/false. If you use values other than 1 and 0, you will get the same code as an if/else, for example:
a = (b > c) ? 2 : 3;
Generates:
mov edx, DWORD PTR b[rip]
mov eax, DWORD PTR c[rip]
cmp edx, eax
jle .L6
mov eax, 2
jmp .L7
.L6:
mov eax, 3
.L7:
Which is the same as the if/else.
Solution 7 - C#
Run without debugging ctrl+F5 it seems the debugger slows down both ifs and ternary significantly but it seems it slows down the ternary operator much more.
When I run the following code here are my results. I think the small millisecond difference is caused by the compiler optimizing the max=max and removing it but is probably not making that optimization for the ternary operator. If someone could check the assembly and confirm this it would be awesome.
--Run #1--
Type | Milliseconds
Ternary 706
If 704
%: .9972
--Run #2--
Type | Milliseconds
Ternary 707
If 704
%: .9958
--Run #3--
Type | Milliseconds
Ternary 706
If 704
%: .9972
Code
for (int t = 1; t != 10; t++)
{
var s = new System.Diagnostics.Stopwatch();
var r = new Random(123456789); //r
int[] randomSet = new int[1000]; //a
for (int i = 0; i < 1000; i++) //n
randomSet[i] = r.Next(); //dom
long _ternary = 0; //store
long _if = 0; //time
int max = 0; //result
s.Start();
for (int q = 0; q < 1000000; q++)
{
for (int i = 0; i < 1000; i++)
max = max > randomSet[i] ? max : randomSet[i];
}
s.Stop();
_ternary = s.ElapsedMilliseconds;
max = 0;
s = new System.Diagnostics.Stopwatch();
s.Start();
for (int q = 0; q < 1000000; q++)
{
for (int i = 0; i < 1000; i++)
if (max > randomSet[i])
max = max; // I think the compiler may remove this but not for the ternary causing the speed difference.
else
max = randomSet[i];
}
s.Stop();
_if = s.ElapsedMilliseconds;
Console.WriteLine("--Run #" + t+"--");
Console.WriteLine("Type | Milliseconds\nTernary {0}\nIf {1}\n%: {2}", _ternary, _if,((decimal)_if/(decimal)_ternary).ToString("#.####"));
}
Solution 8 - C#
Looking at the IL generated, there are 16 less operations in that than in the if/else statement (copying and pasting @JonSkeet's code). However, that doesn't mean it should be a quicker process!
To summarise the differences in IL, the if/else method translates to pretty much the same as the C# code reads (performing the addition within the branch) whereas the conditional code loads either 2 or 3 onto the stack (depending on the value) and then adds it to value outside of the conditional.
The other difference is the branching instruction used. The if/else method uses a brtrue (branch if true) to jump over the first condition, and an unconditional branch to jump from the first out of the if statement. The conditional code uses a bgt (branch if greater than) instead of a brtrue, which could possibly be a slower comparison.
Also (having just read about branch prediction) there may be a performance penalty for the branch being smaller. The conditional branch only has 1 instruction within the branch but the if/else has 7. This would also explain why there's a difference between using long and int, because changing to an int reduces the number of instructions in the if/else branches by 1 (making the read-ahead less)
Solution 9 - C#
In the following code if/else seems to be roughly 1.4 times faster than the ternary operator. However, I found that introducing a temporary variable decreases the ternary operator's run time approximately 1.4 times:
> If/Else: 98 ms > > Ternary: 141 ms > > Ternary with temp var: 100 ms
using System;
using System.Diagnostics;
namespace ConsoleApplicationTestIfElseVsTernaryOperator
{
class Program
{
static void Main(string[] args)
{
Random r = new Random(0);
int[] array = new int[20000000];
for (int i = 0; i < array.Length; i++)
{
array[i] = r.Next(int.MinValue, int.MaxValue);
}
Array.Sort(array);
long value;
Stopwatch stopwatch = new Stopwatch();
value = 0;
stopwatch.Restart();
foreach (int i in array)
{
if (i > 0)
{
value += 2;
}
else
{
value += 3;
}
// 98 ms
}
stopwatch.Stop();
Console.WriteLine("If/Else: " + stopwatch.ElapsedMilliseconds.ToString() + " ms");
value = 0;
stopwatch.Restart();
foreach (int i in array)
{
value += (i > 0) ? 2 : 3;
// 141 ms
}
stopwatch.Stop();
Console.WriteLine("Ternary: " + stopwatch.ElapsedMilliseconds.ToString() + " ms");
value = 0;
int tempVar = 0;
stopwatch.Restart();
foreach (int i in array)
{
tempVar = (i > 0) ? 2 : 3;
value += tempVar;
// 100ms
}
stopwatch.Stop();
Console.WriteLine("Ternary with temp var: " + stopwatch.ElapsedMilliseconds.ToString() + " ms");
Console.ReadKey(true);
}
}
}
Solution 10 - C#
Too many great answers but I found something interesting, very simple changes make the impact. After making below change, to execute if-else and ternary operator it will take same time.
instead of writing below line
value += i > 0 ? 2 : 3;
I used this,
int a = i > 0 ? 2 : 3;
value += a;
One of the below answer also mention that what is bad way to write ternary operator.
I hope this will help you to write ternary operator, instead of thinking of which one is better.
Nested Ternary Operator: I found nested ternary operator and multiple if else block will also takes same time to execute.