Problem
According to what I’ve read, the ternary operator is faster than, or at least equivalent to, the if-else block.
However, I conducted the following investigation and discovered that this is 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());
The code above took 85 milliseconds to run on my PC. It will take roughly 157 milliseconds if I comment out the if-else block and uncomment the ternary operator line.
What’s up with this?
Asked by WSBT
Solution #1
To get an explanation, we’ll look at the assembly code generated by the X86 and X64 JITs in each of these scenarios.
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
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
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
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 and foremost, why is the X86 code so much slower than the X64 code?
This is because of the code’s features:
Second, on both X86 and X64, why is the ternary operator slower?
This is because the JIT’s optimizer is affected by a minor variation in the order of operations. Rather than explicitly coding 2 and 3 in the add machine instructions, the JIT creates an intermediary variable (in a register) to hold the result to JIT the ternary operator. Before being added to value, this register is sign-extended from 32 to 64 bits. Despite the large increase in complexity for the ternary operator, the net impact is slightly lessened because everything is done in registers for X64.
The X86 JIT, on the other hand, is more impacted because adding a new intermediate value in the inner loop leads it to “spill” another value, resulting in at least two extra memory accesses in the inner loop (see the accesses to [ebp-14h] in the X86 ternary code).
Answered by Sam Harwell
Solution #2
EDIT: Everything has changed… check the section below for further information.
On the x64 CLR, I can’t duplicate your results, but on the x86 CLR, I can. I can observe a minor difference between the conditional operator and the if/else on x64 (less than 10%), but it’s far smaller than you’re seeing.
The following possible modifications have been made:
The following are the results of using /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
The following are the results of using /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:
So, unlike before, I believe you are noticing a significant difference, and it is entirely due to the x86 JIT. I’m not going to explain what’s causing the difference; if I can get into cordbg, I’ll update the post with further information later.
Surprisingly, if I run the tests without first sorting the array, they take around 4.5 times as long, at least on x64. This, I believe, has something 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);
}
}
Answered by Jon Skeet
Solution #3
The difference between if/else and ternary has little to do with it.
Looking at the jittered disassemblies (which I won’t repeat here; instead, see @280Z28’s response), it appears that you’re comparing apples to oranges. In one case, you create two alternative += operations with constant values, and which one you choose is determined by a condition; in the other case, you create a += where the value to add is determined by a condition.
If you really want to compare if/else and ternary, this is a better comparison (now both are “slow,” or we could even argue ternary is a little faster):
int diff;
if (i > 0)
diff = 2;
else
diff = 3;
value += diff;
vs.
value += i > 0 ? 2 : 3;
The disassembly for the if/else now looks like this. This is a little worse than the ternary case, because it also stops using the registers for the loop variable(i).
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]
Answered by Eren Ersönmez
Solution #4
Edit:
A new example was added that uses the if-else statement rather than the conditional operator.
Please read [Which is faster?] on Mr. Lippert’s blog before answering. And I believe Mr. Ersönmez’s response is the most accurate.
I’m trying to emphasize something important to remember when using a high-level programming language.
To begin with, I’ve never heard that the conditional operator or the if-else statement in C are supposed to be faster or perform as well.
The explanation for this is simple: what if the if-else statement doesn’t have any operations:
if (i > 0)
{
value += 2;
}
else
{
}
The conditional operator necessitates the presence of a value on either side, and in C, both sides of: must be of the same type. This just distinguishes it from the if-else sentence. As a result, your query becomes a question about how the machine code instruction is created, resulting in the performance disparity.
In terms of semantics, the conditional operator is:
There is a value for any expression that is evaluated.
However, using an if-else statement:
If the expression is true, do something; if it isn’t, do something else.
With an if-else expression, a value isn’t always required. Only optimization allows you to make your assumption.
Another example to explain the distinction between them is as follows:
var array1=new[] { 1, 2, 3 };
var array2=new[] { 5, 6, 7 };
if(i>0)
array1[1]=4;
else
array2[2]=4;
However, if you replace the if-else line with the conditional operator, the code will not compile:
var array1=new[] { 1, 2, 3 };
var array2=new[] { 5, 6, 7 };
(i>0?array1[1]:array2[2])=4; // incorrect usage
When doing the same thing, the conditional operator and the if-else statements are conceptually the same; however, the conditional operator in C may be faster because C is closer to the platform assembly.
The conditional operator is used in a foreach-loop in the original code you gave, which makes it difficult to see the difference between them. As a result, I propose 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);
}
}
The optimized and non-optimized versions of the IL are shown below. I’m using an image to demonstrate them because they’re long: The right hand side is the optimized one:
The IL of the conditional operator appears to be shorter in both versions of the code than the if-else statement, and there is still some question about the machine code generated. The directions for both methods are as follows, with the former image being non-optimized and the latter being optimized:
The code in the latter is only performed if i=0, whereas the code in the former is only executed when i>0. The if-else statement is shorter in both versions of the instructions.
It’s worth noting that the [CPI] isn’t always the same for different instructions. More instructions, therefore, cost a longer cycle for the same instruction. However, when instruction fetching time and pipe/cache time are included in, the real total execution time is dependent on the processor. The processor is also capable of foreseeing the branching.
Because modern CPUs have many cores, things can become more complicated. If you use Intel processors, [Intel® 64 and IA-32 Architectures Optimization Reference Manual] may be of interest to you.
I’m not sure if there was a hardware-implemented CLR, but if there was, the conditional operator is definitely faster because the IL is plainly lower.
Note that all of the machine code is written in x86.
Answered by Ken Kin
Solution #5
I did what Jon Skeet did and ran through 1 iteration and 1,000 iterations and received a different result from both OP and Jon. The ternary is slightly faster in my case. 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();
}
My program’s result is as follows:
In milliseconds, another run:
I ran this without debugging in 64-bit XP.
Edit – x86 compatibility:
Using x86 makes a significant difference. This was done without debugging on the identical xp 64-bit computer as was used previously, but constructed for x86 CPUs. This appears to be the same as the OP’s.
Answered by Shaz
Post is based on https://stackoverflow.com/questions/17328641/ternary-operator-is-twice-as-slow-as-an-if-else-block