Corefxlab: Investigate perf diff between the Span ctor that takes array vs pointer

[ahsonkhan]

https://github.com/dotnet/corefxlab/pull/1475#discussion_r112249006

cc @KrzysztofCwalina

[ahsonkhan]

cc @KrzysztofCwalina, @shiftylogic, @jkotas, @davidfowl

Conclusion:
The Span constructor that takes an array is faster than the one that takes a pointer by at least 30%.

Data:
Frequency - 3604600 ticks/second
SpanConstructorArray1 - 132 ticks => 0.0366 ms
SpanConstructorArray2 - 130 ticks => 0.0361 ms
SpanConstructorPointer- 196 ticks => 0.0543 ms

Test Program:
```C#
static unsafe void Main(string[] args)
{
SpanConstructorArray1(false);
SpanConstructorArray2(false);
SpanConstructorPointer(false);

SpanConstructorArray1();
SpanConstructorArray2();
SpanConstructorPointer();

}

public unsafe static Span SpanConstructorArray1(bool output = true)
{
Stopwatch sw = new Stopwatch();
int[] a = new int[10000];

fixed (int *pa = a)
{
    Span<int> span;
    sw.Restart();
    for (int j = 0; j < 100000; j++)
    {
        span  = new Span<int>(a);
    }
    sw.Stop();
    if (output) Console.WriteLine(sw.ElapsedTicks);
    return span;
}

}

public unsafe static Span SpanConstructorArray2(bool output = true)
{
Stopwatch sw = new Stopwatch();
int[] a = new int[10000];

Span<int> span;
sw.Restart();
for (int j = 0; j < 100000; j++)
{
    span  = new Span<int>(a);
}
sw.Stop();
if (output) Console.WriteLine(sw.ElapsedTicks);
return span;

}

public unsafe static Span SpanConstructorPointer(bool output = true)
{
Stopwatch sw = new Stopwatch();
int[] a = new int[10000];

fixed (int *pa = a)
{
    Span<int> span;
    sw.Restart();
    for (int j = 0; j < 100000; j++)
    {
        span = new Span<int>(pa, 10000);
    }
    sw.Stop();
    if (output) Console.WriteLine(sw.ElapsedTicks);
    return span;
}

}

```
API Source (fast span):
Array - https://github.com/dotnet/coreclr/blob/master/src/mscorlib/shared/System/Span.cs#L43-L52
Pointer - https://github.com/dotnet/coreclr/blob/master/src/mscorlib/shared/System/Span.cs#L123-L132

Disassembly:

               span  = new Span<int>(a);

00007FFB30FF3B41 lea r14,[rbp+10h]
00007FFB30FF3E91 mov r15d,3E8h

            span  = new Span<int>(a);

00007FFB30FF3E8D lea r14,[rbp+10h]
00007FFB30FF3E91 mov r15d,3E8h

               span = new Span<int>(pa, 10000);

00007FFB30FF3F68 mov rax,qword ptr [rsp+28h]
00007FFB30FF3F6D mov rbp,rax
00007FFB30FF3F70 mov rax,rbp
00007FFB30FF3F73 mov rbp,rax
00007FFB30FF3F76 mov r14d,3E8h

[benaadams]

Some busy work with movs that do nothing in the pointer span

[davidfowl]

Isn't that the same problem we saw before when using the fixed variable in a loop? If you change the code to this what does the performance look like:

```C#
public unsafe static Span SpanConstructorPointer(bool output = true)
{
Stopwatch sw = new Stopwatch();
int[] a = new int[10000];

fixed (int *pa = a)
{
    byte* p = pa;
    Span<int> span;
    sw.Restart();
    for (int j = 0; j < 100000; j++)
    {
        span = new Span<int>(p, 10000);
    }
    sw.Stop();
    if (output) Console.WriteLine(sw.ElapsedTicks);
    return span;
}

}
```

[ahsonkhan]

Isn't that the same problem we saw before when using the fixed variable in a loop?

Yes. I will update and add perf results tomorrow.

[ahsonkhan]

This is unexpected.

I updated the test code as @davidfowl suggested:
```C#
public unsafe static Span SpanConstructorPointer(bool output = true)
{
Stopwatch sw = new Stopwatch();
var a = new int[10000];

        fixed (int* pa = a)
        {
            int* p = pa;
            Span<int> span;
            sw.Restart();
            for (int j = 0; j < 100000; j++)
            {
               span = new Span<int>(p, 10000);
            }
            sw.Stop();
            if (output) Console.WriteLine(sw.ElapsedTicks);
            if (output) Console.WriteLine(Stopwatch.Frequency);
            return span;
        }
    }

```

And the runtime got significantly worst:
SpanConstructorPointer - From 196 ticks => 884 ticks now.

The diassembly shows a function call:

               span = new Span<int>(p, 10000);

00007FFB30FF3F92 mov rcx,rbp
00007FFB30FF3F95 call 00007FFB8FB71A30
00007FFB30FF3F9A mov r15,rax
00007FFB30FF3F9D mov r12d,2710h

@shiftylogic, @russellhadley - any ideas what's causing this?

[KrzysztofCwalina]

cc: @russellhadley, @jkotas

[russellhadley]

@ahsonkhan is the full dump available? (for any of the cases?) The moves look like we hit an allocation glass jaw. @CarolEidt for the RA side.

[jkotas]

The diassembly shows a function call:

It is a call to Unsafe.As. It fails to inline because of return type mismatch:

INLINER: during 'fgInline' result 'failed this call site' reason 'return type mismatch' for 'My:SpanConstructorPointer():struct' calling 'Unsafe:As(byref):byref'

dump.txt

[jkotas]

The CoreLib internal version of Unsafe.As is missing the workaround for this that was done in the public OOB version of Unsafe.As:

https://github.com/dotnet/corefx/blob/8399b5c9e2fe8dc5867aacf9ccaa1229198df9d0/src/System.Runtime.CompilerServices.Unsafe/src/System.Runtime.CompilerServices.Unsafe.il#L268

[ahsonkhan]

@jkotas, should we add that workaround? If not, how do we resolve this issue?

[jkotas]

@jkotas, should we add that workaround

Yes.

[ahsonkhan]

The CoreLib internal version of Unsafe.As is missing the workaround for this that was done in the public OOB version of Unsafe.As.

Where is the CoreLib internal version of Unsafe.As?

[jkotas]

https://github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/Runtime/CompilerServices/Unsafe.cs#L55
https://github.com/dotnet/coreclr/blob/master/src/vm/jitinterface.cpp#L6994

[jkotas]

Actually, I am wondering whether it would be better to fix the JIT instead. It looks like a bug in the JIT related to byrefs that can show up in seemingly random places. It would be better to fix the JIT so that we do not have to be adding workarounds like this when working with byrefs.

@russellhadley ?

[jkotas]

Minimal repro:

Span constructor gets fully inlined (expected):

            var a = new int[10000];
            fixed (int* pa = a)
            {
                Span<int> span = new Span<int>(pa, 10000);
            }

Span constructor does not get fully inlined because of return value type mismatch on Unsafe.As (bug):

            var a = new int[10000];
            fixed (int* pa = a)
            {
                int* tmp = pa;
                Span<int> span = new Span<int>(tmp, 10000);
            }

[jkotas]

I have opened https://github.com/dotnet/coreclr/issues/11211 on the JIT optimization bug with even smaller repro that does not involve Span or Unsafe.

[ahsonkhan]

After this change https://github.com/dotnet/coreclr/pull/11218:

cc @KrzysztofCwalina, @shiftylogic, @jkotas, @davidfowl, @AndyAyersMS

Conclusion:
The Span constructor that takes a pointer is ~2x faster than the one that takes an array.

Data:
Frequency - 3604598 ticks/second
SpanConstructorArray1 - 198 ticks => 0.0549 ms
SpanConstructorArray2 - 196 ticks => 0.0544 ms
SpanConstructorPointer- 98 ticks => 0.0272 ms (Before: > 196 ticks)

Disassembly:

            span  = new Span<int>(a); // Doing extra/unnecessary work here

00007FFCBF2A21BD lea rax,[rbp+10h]
00007FFCBF2A21C1 mov r14,rax
00007FFCBF2A21C4 mov rax,r14
00007FFCBF2A21C7 mov r14,rax
00007FFCBF2A21CA mov r15d,2710h

               span = new Span<int>(pa, 10000); // Not using local variable int* p = pa;

00007FFCBF2B2448 mov rax,qword ptr [rsp+28h]
00007FFCBF2B244D mov rbp,rax
00007FFCBF2B2450 mov rax,rbp
00007FFCBF2B2453 mov rbp,rax
00007FFCBF2B2456 mov r14d,2710h

               span = new Span<int>(p, 10000);

00007FFCBF2A244F mov r14,rbp
00007FFCBF2A2452 mov r15d,2710h

Test Program:
```C#
static void Main(string[] args)
{
SpanConstructorArray1(false);
SpanConstructorArray2(false);
SpanConstructorPointer(false);

SpanConstructorArray1();
SpanConstructorArray2();
SpanConstructorPointer();

}

public unsafe static Span SpanConstructorArray1(bool output = true)
{
Stopwatch sw = new Stopwatch();
int[] a = new int[10000];

fixed (int *pa = a)
{
    Span<int> span;
    sw.Restart();
    for (int j = 0; j < 100000; j++)
    {
        span  = new Span<int>(a);
    }
    sw.Stop();
    if (output) Console.WriteLine(sw.ElapsedTicks);
    return span;
}

}

public unsafe static Span SpanConstructorArray2(bool output = true)
{
Stopwatch sw = new Stopwatch();
int[] a = new int[10000];

Span<int> span;
sw.Restart();
for (int j = 0; j < 100000; j++)
{
    span  = new Span<int>(a);
}
sw.Stop();
if (output) Console.WriteLine(sw.ElapsedTicks);
return span;

}

public unsafe static Span SpanConstructorPointer(bool output = true)
{
Stopwatch sw = new Stopwatch();
int[] a = new int[10000];

fixed (int *pa = a)
{
    Span<int> span;
    int* p = pa;
    sw.Restart();
    for (int j = 0; j < 100000; j++)
    {
        span = new Span<int>(p, 10000);
    }
    sw.Stop();
    if (output) Console.WriteLine(sw.ElapsedTicks);
    return span;
}

}

```
API Source (fast span):
Array - https://github.com/dotnet/coreclr/blob/master/src/mscorlib/shared/System/Span.cs#L43-L52
Pointer - https://github.com/dotnet/coreclr/blob/master/src/mscorlib/shared/System/Span.cs#L123-L132

[ahsonkhan]

Why is the array constructor doing extra work? I believe there is an issue open for this already. @AndyAyersMS, do you remember the issue #?

Aside from the above point, I believe the investigation is complete.

Conclusion:
The Span constructor that takes a pointer is ~2x faster than the one that takes an array.

Thoughts?

[jkotas]

There is some work for JIT to do to eliminate the unnecessary register moves. We should have issue in CoreCLR repo to track it. I do not expect it to be hard to fix - we should be able to get the array version down to the exact same two instruction as the pointer version. @AndyAyersMS can comment on detail.

However, the micro-benchmark is somewhat misleading because of it does not represent what real code does: Real code won't create 100000 spans from the same constant sized array and do nothing interesting with 99999 of them - this pattern allows optimizations that won't apply for real code. Real code will create 100000 spans from different variable sized arrays and do something interesting with each of them. Once you start doing that the difference between the two constructor will become neglible, even with the current inefficiency. We should not be writing unnatural code because of the result of this test.

[AndyAyersMS]

Agree with Jan. If the jit was just a bit more savvy here it would have sunk the stores out of the loop and then realize the loop was empty and remove it and you' be testing nothing at all.

The register shuffling is related to what I think is a recent change in Roslyn about how it generates code for fixed constructs (there was a thread with @JosephTremoulet recently, but I can't find it and don't remember it if was email or here on GitHub). We now see the pinned local that fixed introduces referenced at use sites (with cast), rather than the expression or temp local being pinned, and this causes the jit to generate some convoluted code as gcness is getting cast away (at the conv.i):

  .locals init (...,   [1] int32& pinned pa, ...)   ;;  declare the pin
  ...
  ;; set the pin
  IL_0017:  ldelema    [System.Private.CoreLib]System.Int32
  IL_001c:  stloc.1
  ...
  ;; use the pin
  IL_0032:  ldloc.1
  IL_0033:  conv.i
  IL_0034:  ldc.i4     0x2710
  IL_0039:  call       instance void valuetype [System.Private.CoreLib]System.Span`1<int32>::.ctor(void*,
                                                                                                   int32)

The gcness returns inside the constructor (which is inlined) so jit sees a value go from GC->noGC->GC and it does not substitute across this even though there is no other use of the intermediate noGC value. Hence the shuffling. In jit IR (here V16 is the GC field in the output span, V19 a GC intermediary, V04 the pinned pointer, and V20 is the non-GC intermediary):

***** BB07, stmt 24
               [000261] ------------             *  stmtExpr  void  (IL 0x030...  ???)
               [000346] ------------             |  /--*  const     byref  0
               [000347] -A---+------             \--*  =         byref 
               [000345] D------N----                \--*  lclVar    byref  V19 tmp11        

***** BB07, stmt 25
               [000267] ------------             *  stmtExpr  void  (IL 0x030...  ???)
               [000350] -----+------             |     /--*  lclVar    long   V20 tmp12        
               [000352] -A---+------             |  /--*  comma     long  
               [000051] -----+------             |  |  |  /--*  lclVar    byref  V04 loc1         
               [000349] -A---+------             |  |  \--*  =         long  
               [000348] D----+-N----             |  |     \--*  lclVar    long   V20 tmp12        
               [000265] -A---+------             \--*  =         byref 
               [000264] D----+-N----                \--*  lclVar    byref  V19 tmp11        

***** BB07, stmt 26
               [000272] ------------             *  stmtExpr  void  (IL 0x030...  ???)
               [000354] -------N----             |  /--*  lclVar    byref  V19 tmp11        
               [000355] -A---+------             \--*  =         byref 
               [000353] D------N----                \--*  lclVar    byref  V16 tmp8         

linearized this is

V19(gc) = 0;
V20(nogc) = V04;
V19(gc) = V20;
V16(gc) = V19

The zeroing is dead coded but the three moves remain, and the RA picks RAX for V19, and RSI for V20 and V16, and [rsp+0x28] for V04 (loaded into a temp reg RAX), so we end up with:

       488B442428           mov      rax, bword ptr [rsp+28H]    ;; t = V04
       488BF0               mov      rsi, rax  ;; V20 = t
       488BC6               mov      rax, rsi  ;; V19 = V20
       488BF0               mov      rsi, rax   ;; V16 = V19

Seems like the jit ought to be able to substitute here and simplify. Opened dotnet/coreclr#11390 for this.

[ahsonkhan]

I do not expect it to be hard to fix - we should be able to get the array version down to the exact same two instruction as the pointer version.

So, do we expect the resolution of this issue to be that there is no perf diff between the Span ctor that takes array vs pointer. Should I keep this issue open until that becomes true or is the investigation complete regardless?

Once you start doing that the difference between the two constructor will become neglible, even with the current inefficiency.

Of course. However, the micro-benchmark does expose some unexpected code gen, even though it is forcibly unnatural.

[JosephTremoulet]

The register shuffling is related to what I think is a recent change in Roslyn about how it generates code for fixed constructs (there was a thread with @JosephTremoulet recently, but I can't find it and don't remember it if was email or here on GitHub).

dotnet/roslyn#18615 is tracking changing the C#->IL codegen for these cases

[KrzysztofCwalina]

@ahsonkhan, if we are happy with the investigation, please close this issue. Thanks.