RyuJIT optimization problem with double constants in a loop

[GSPP]

In the code posted below RyuJIT loads double values in the loop from memory each iteration. This is not necessary and slow. They should be in registers. This appears to be either a bug or a missing optimization. I request that this issue be investigated and fixed if possible.

using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;

public static class CSharpTest
{
 private const int ITERATIONS = 1000 * 1000 * 100;

 public static void Main()
 {
 Test1();
 }

 private static void Test1()
 {
 Point a = new Point(1, 1);
 Point b = new Point(1, 1);

 for (int i = 0; i < ITERATIONS; i++)
 a = AddByVal(a, b);

 GC.KeepAlive(a.X + b.X + a.Y + b.Y); //consume result
 }

 [MethodImpl(MethodImplOptions.AggressiveInlining)]
 private static Point AddByVal(Point a, Point b)
 {
 return new Point(a.X + b.Y, a.Y + b.X);
 }
}

public struct Point
{
 public Point(double x, double y) { X = x; Y = y; }
 public readonly double X;
 public readonly double Y;
}

 Point a = new Point(1, 1);
00000000 sub rsp,48h 
00000004 movaps xmmword ptr [rsp+30h],xmm6 
00000009 movaps xmmword ptr [rsp+20h],xmm7 
0000000e movsd xmm6,mmword ptr [0000000000000098h] 
00000016 movsd xmm7,mmword ptr [00000000000000A0h] 

 for (int i = 0; i < ITERATIONS; i++)
0000001e xor ecx,ecx 
 a = AddByVal(a, b);
00000020 movaps xmm0,xmm6 
00000023 addsd xmm0,mmword ptr [00000000000000A8h] //This should not exist
0000002b movsd xmm6,xmm0 
0000002f movaps xmm0,xmm7 
00000032 addsd xmm0,mmword ptr [00000000000000B0h] //This should not exist
0000003a movsd xmm7,xmm0 
0000003e movsd xmm0,xmm6 
00000042 movsd xmm6,xmm0 
 for (int i = 0; i < ITERATIONS; i++)
00000046 inc ecx 
00000048 cmp ecx,5F5E100h 
0000004e jl 0000000000000020 

 GC.KeepAlive(a.X + b.X + a.Y + b.Y); //consume result
00000050 mov rcx,7FFCC2205688h 
0000005a call 000000005F65E850 
0000005f mov rcx,rax 
00000062 movaps xmm0,xmm6 
00000065 addsd xmm0,mmword ptr [00000000000000B8h] 
0000006d addsd xmm0,xmm7 
00000071 addsd xmm0,mmword ptr [00000000000000C0h] 
00000079 movsd mmword ptr [rcx+8],xmm0 
0000007e call 000000005E63F020 
00000083 nop 
 }
00000084 movaps xmm6,xmmword ptr [rsp+30h] 
00000089 movaps xmm7,xmmword ptr [rsp+20h] 
0000008e add rsp,48h 
00000092 ret 

Also, I think the loop should be unrolled at least 2 times. 2x unrolling seems like a conservative behavior that can be applied liberally. Especially in tight floating point loops.

[mikedn]

This appears to be either a bug or a missing optimization.

Probably a case of over aggressive constant propagation, the same thing happens with scalar variables which excludes any struct related issues:

double a = 1.0, b = 1.0;

for (int i = 0; i < ITERATIONS; i++)
 a = a + b;

generates

vmovsd xmm0,qword ptr [00007FFB31D844C0h] 
xor eax,eax 
vaddsd xmm0,xmm0,mmword ptr [00007FFB31D844C8h] 
inc eax 
cmp eax,5F5E100h 
jl 00007FFB31D844AB

If b was kept as a normal local variable it would have likely been enregistered and that would have produced the expected code.

[mikedn]

That said, this issue doesn't seem to affect performance in any way. On my Core i5 Haswell CPU 1 billion AddByVal take ~960ms with or without enregistered constants. Same thing about unrolling, no amount of unrolling makes a difference.

Test code:

 public static void Main()
 {
 Point a = new Point(1, 1);
 Point b = new Point(1, 1);

 Stopwatch sw = Stopwatch.StartNew();
 a = Foo(a, b);
 Console.WriteLine(sw.ElapsedMilliseconds);
 }

 [MethodImpl(MethodImplOptions.NoInlining)]
 private static Point Foo(Point a, Point b)
 {
 Point r = a;
 Point c = b; // change to new Point(1, 1) to get the original code

 for (int i = 0; i < 1000000000; i++)
 r = AddByVal(r, c);

 return r;
 }

 [MethodImpl(MethodImplOptions.AggressiveInlining)]
 private static Point AddByVal(Point a, Point b)
 {
 return new Point(a.X + b.Y, a.Y + b.X);
 }

[GSPP]

Maybe there should be a compiler pass fairly late that "outlines" expensive constants that previously were propagated and "inlined". First, push all constants forward, simplify and compute all statically known results. Then, turn those constants back into regular values that are expensive to create.

Maybe constants need to be tagged as cheap or expensive internally in the compiler so that LICM understand to pull the expensive ones out.

You are right, though, that this benchmark fails to find any performance loss. Here is a more clear piece of code to demonstrate that:

 Stopwatch sw = Stopwatch.StartNew();
 //a = Foo(a, b);
 Foo2(11, 12);
 Console.WriteLine(sw.ElapsedMilliseconds);
 }

 [MethodImpl(MethodImplOptions.NoInlining)]
 private static double Foo2(double a, double b)
 {
 double temp = a;
 var cnst = b + 1234.5678 - b;

 for (int i = 0; i < 1000000000; i++)
 {
 temp = temp + cnst + b;
 temp = temp + 1234.5678 + b;
 }

 return temp;
 }

Swap the two lines in the inner loop. The cnst thing is to force register usage.

I managed to create a small performance differential of 10%:

 [MethodImpl(MethodImplOptions.NoInlining)]
 private static double Foo5(double a, double b)
 {
 var temp0 = a;
 var temp1 = a;
 var temp2 = a;
 var temp3 = a;

 var cnst0 = b + 1234.0 - b;
 var cnst1 = b + 1234.1 - b;
 var cnst2 = b + 1234.2 - b;
 var cnst3 = b + 1234.3 - b;

 for (int i = 0; i < 1000000000; i++)
 {
 /*temp0 = temp0 + cnst0;
 temp1 = temp1 + cnst1;
 temp2 = temp2 + cnst2;
 temp3 = temp3 + cnst3;*/

 temp0 = temp0 + 1234.0;
 temp1 = temp1 + 1234.1;
 temp2 = temp2 + 1234.2;
 temp3 = temp3 + 1234.3;
 }

 return temp0 + temp1 + temp2 + temp3;
 }

I think this is because there are less memory units than floating pointer add units so that the constant loading becomes a slight bottleneck.

Here's my loop unrolling test (no improvement at all):

 [MethodImpl(MethodImplOptions.NoInlining)]
 private static double Foo6(double a, double b)
 {
 var temp = a;
 var cnst = b + 1234.5678 - b;

 /*for (int i = 0; i < 1000000000; i++)
 {
 temp = temp + cnst;
 }*/

 /*for (int i = 0; i < 1000000000; i += 2)
 {
 temp = temp + cnst;
 temp = temp + cnst;
 }*/

 for (int i = 0; i < 1000000000; i += 4)
 {
 temp = temp + cnst;
 temp = temp + cnst;
 temp = temp + cnst;
 temp = temp + cnst;
 }

 return temp;
 }

Here's unrolling with broken dependency chains:

 [MethodImpl(MethodImplOptions.NoInlining)]
 private static double Foo7(double a, double b)
 {
 var temp0 = a;
 var temp1 = a;
 var temp2 = a;
 var temp3 = a;

 /*for (int i = 0; i < 1000000000; i += 1)
 {
 temp0 = temp0 + 1234.0;
 }*/

 /*for (int i = 0; i < 1000000000; i += 2)
 {
 temp0 = temp0 + 1234.0;
 temp1 = temp1 + 1234.1;
 }*/

 for (int i = 0; i < 1000000000; i += 4)
 {
 temp0 = temp0 + 1234.0;
 temp1 = temp1 + 1234.1;
 temp2 = temp2 + 1234.2;
 temp3 = temp3 + 1234.3;
 }

 return temp0 + temp1 + temp2 + temp3;
 }

This speeds up as much as you unroll the loop (2x => 2x and 4x => 4x). Unfortunately, with floats this is semantically not allowed.

I'm no longer convinced that the JIT team should spend its time on this issue.

[mikedn]

Maybe there should be a compiler pass fairly late that "outlines" expensive constants that previously were propagated and "inlined". First, push all constants forward, simplify and compute all statically known results. Then, turn those constants back into regular values that are expensive to create.

For the general case the simplest thing that can be done is to treat FP constants are memory loads, that's what they are after all (with the exception of 0). Then LICM could hoist them and the register allocator can decide to keep them in registers or reload them depending on usage and register pressure. Though it seems that LICM doesn't currently deal with memory loads so this is probably more complicated than simply replacing all GT_CNS_DOUBLE nodes with GT_IND nodes.

I think this is because there are less memory units than floating pointer add units so that the constant loading becomes a slight bottleneck.

Could be but I wasn't able to reproduce the 10% difference. In both cases I get 1303-1311ms. I'm pretty sure I'd see a difference if I run this on an old Core2 CPU I happen to have but I'm too lazy to start that PC at the moment 😄

This speeds up as much as you unroll the loop (2x => 2x and 4x => 4x). Unfortunately, with floats this is semantically not allowed.

Maybe it's time for a /fp:fast option for the JIT compiler. Some people might be willing to give up some precision for such a perf boost.

I'm no longer convinced that the JIT team should spend its time on this issue.

Maybe yes, maybe not. Things may be different with other processors not to mention other architectures like ARM. Let's say that it may be worth doing but at the moment it looks like low priority.

[BruceForstall]

/cc @CarolEidt

[CarolEidt]

First, let me acknowledge that there are plenty of opportunities for improvement in the JIT :-)
That said, I think that the issue here is the tension between constant propagation, register allocation, and (the lack of support for) rematerialization, where rematerialization allows some register candidates to be marked as rematerializable (ideally, with an associated cost) if the cost of rematerializing the value is cheaper than reloading it.
In an ideal world, all constants would be CSE'd and marked as rematerializable, so that the register allocator could make the appropriate choice. In the less than ideal world of a JIT, where CSE temps are not free, and compile time is at a premium, this would probably apply only to constants that are likely to be cheaper to keep in a register in most cases.
Note that the costs associated with rematerializing a constant differ both between target processors as well as the instruction at which they are used, so at best this would be an approximate heuristic.
So, in summary I DO think this problem is worth spending time on (albeit, at the current moment, not at the top of my priority list) - but I would describe it as this more general problem of rematerialization.

[DemiMarie]

What about client and server modes, offering a trade-off between compile time and runtime?

[GSPP]

@drbo I think that would be great. Like /O1 vs. /O2.

Even better would be a tiered JIT like the JVM uses it. That would always work and have even better startup time than RyuJIT. Most methods end up running a few times only and being interpreted. No JIT cost at all.

[DemiMarie]

Or use RyuJIT for medium-hot methods and LLILC for the hottest ones, as
LLVM optimizes better than RyuJIT ever will.
On Sep 13, 2015 5:49 PM, "GSPP" notifications@github.com wrote:

@drbo https://github.com/drbo I think that would be great. Like /O1 vs.
/O2.

Even better would be a tiered JIT like the JVM uses it. That would always
work and have even better startup time than RyuJIT. Most methods end up
running a few times only and being interpreted. No JIT cost at all.

—
Reply to this email directly or view it on GitHub
https://github.com/dotnet/coreclr/issues/1417#issuecomment-139921520.

[pgavlin]

I think that this specific issue is now tracked by dotnet/coreclr#6131, so I am going to close this issue. Please feel free to reopen if necessary.