Use base index scale to access address in unsafe

[fo40225]

Consider those code

int[] a = { 1, 2 };
int temp;
fixed (int* ptrA = a)
{
    for (int i = 0; i < a.Length; i++)
    {
        temp = ptrA[i];
        temp = temp + i;
        Console.WriteLine(temp.ToString());
    }

    int* tempPtrA = ptrA;
    for (int i = 0; i < a.Length; i++, tempPtrA++)
    {
        temp = *tempPtrA;
        temp = temp + i;
        Console.WriteLine(temp.ToString());
    }
}

In C/C++, first loop will faster than second one because first loop will use

mov         eax,dword ptr a[esi*4]

use only one instruction and get value. and second loop will use extra two instructions to increase pointer

mov         eax,dword ptr [edi]
inc         esi 
lea         edi,[edi+4]

But in C# unsafe code, first loop will use

mov         rcx,qword ptr [rbp-20h]
mov         qword ptr [rbp-38h],rcx
mov         rcx,qword ptr [rbp-38h]
mov         eax,dword ptr [rbp-2Ch]
movsxd      rax,eax  
mov         edx,4  
movsxd      rdx,edx  
imul        rax,rdx  
mov         ecx,dword ptr [rcx+rax]

and cause first one slow than second one. The imul slow down the performance.

If there is no performance penalty for using a scaling factor, why don't just use that instead of imul.

or there have some reason so can't use it?

[mikedn]

In C/C++, first loop will faster than second one because first loop will use

That really depends on the compiler. Some may transform the slow version into the fast version and, some may transform the fast version into the slow version and some may do no transformation at all.

But in C# unsafe code, first loop will use

I cannot reproduce that, it looks like debug code. The code I get for that loop is:

G_M11821_IG06:
       488B442420           mov      rax, bword ptr [rsp+20H]
       4863D7               movsxd   edx, edi
       8B1C90               mov      ebx, dword ptr [rax+4*rdx]
       03DF                 add      ebx, edi
; Console.WriteLine stuff omitted for brevity
       FFC7                 inc      edi
       3BF7                 cmp      esi, edi
       7FD4                 jg       SHORT G_M11821_IG06

It looks reasonable. The reload of ptrA at the start of the loop could have been avoided, this is caused by fixed and has already been reported in #4872. The movsxd could have been avoided by widening the i to long, this has been mentioned a few times in other JIT issues. But there's no imul to be seen in this code.

[fo40225]

OK, I try to use attach visual studio debugger after launch program instead of use visual studio to debug Release build directly. And I got your result.

So the problem is array style has unnecessary movsxd cause slower the pointer arithmetic?

the ptrB[i] = ptrA[i]; loop will slower than *tb = *ta; in below code

var a = new int[536870911];
var rnd = new Random();

for (int i = 0; i < a.Length; i++)
{
    a[i] = rnd.Next();
}

var b = new int[536870911];
fixed (int* ptrA = a, ptrB = b)
{
    for (int i = 0; i < a.Length; i++)
    {
        ptrB[i] = ptrA[i];
    }
}

b = new int[536870911];
fixed (int* ptrA = a, ptrB = b)
{
    int* ta = ptrA;
    int* tb = ptrB;
    for (int i = 0; i < a.Length; i++, ta++, tb++)
    {
        *tb = *ta;
    }
}

[mikedn]

So the problem is array style has unnecessary movsxd cause slower the pointer arithmetic?

Have you measured and determined that it is indeed slower? For arrays that large the impact of memory loads and stores is significant enough that couple of additional fast instructions like movsxd or lea edi,[edi+4] won't make much of a difference. Even a non-pointer version of this loop will provide the same performance, 365-410ms on my machine.

the ptrB[i] = ptrA[i]; loop will slower than *tb = *ta; in below code

That fact that the second loop in your code avoid using the fixed pointers has more impact than the use of fixed arithmetic. You can change the first loop to:

int* ta = ptrA;
int* tb = ptrB;
for (int i = 0; i < a.Length; i++)
    tb[i] = ta[i];

and the result won't be very different from the second loop, at least with the giant array you are testing with.

[fo40225]

I try the small array and there is no significant difference between non-fixed pointer array style and star style.

With increase array size, fixed pointer will have observably slow.

In very large array, fixed pointer will slow than non-fixed. even managed access will faster than fixed one.

I have no idea because those x86 asm looks very likely.

Why fixed pointer has access performance impact?

test code

var x = new int[0x7FEFFFFF];
for (int i = 0; i < x.Length; i++)
{
    x[i] = rnd.Next();
}

var y = new int[0x7FEFFFFF];
for (int i = 0; i < x.Length; i++)
{
    y[i] = x[i];
}

y = new int[0x7FEFFFFF];
fixed (int* ptrX = x, ptrY = y)
{
    for (int i = 0; i < x.Length; i++)
    {
        ptrY[i] = ptrX[i];
    }
}

y = new int[0x7FEFFFFF];
fixed (int* ptrX = x, ptrY = y)
{
    int* tx = ptrX;
    int* ty = ptrY;
    for (int i = 0; i < x.Length; i++)
    {
        ty[i] = tx[i];
    }
}

y = new int[0x7FEFFFFF];
fixed (int* ptrX = x, ptrY = y)
{
    int* tx = ptrX;
    int* ty = ptrY;
    for (int i = 0; i < x.Length; i++, tx++, ty++)
    {
        *ty = *tx;
    }
}

[fo40225]

Oh I figure out, is that the same problem in #4872?

[mikedn]

If I understand correctly what you are asking then yes, it's the same problem as in #4872.

Let's look at the generated code for those 2 loops that use indexing:

            fixed (int* ptrX = x, ptrY = y)
            {
                for (int i = 0; i < x.Length; i++)
                {
                    ptrY[i] = ptrX[i];
                }
            }

generates

G_M52619_IG09:
       4C8B442438           mov      r8, bword ptr [rsp+38H] ; reload ptrY
       4C63C9               movsxd   r9d, ecx
       4C8B542440           mov      r10, bword ptr [rsp+40H] ; reload ptrX
       478B148A             mov      r10d, dword ptr [r10+4*r9]
       47891488             mov      dword ptr [r8+4*r9], r10d
       FFC1                 inc      ecx
       3BD1                 cmp      edx, ecx
       7FE5                 jg       SHORT G_M52619_IG09

and

            fixed (int* ptrX = x, ptrY = y)
            {
                int* tx = ptrX;
                int* ty = ptrY;
                for (int i = 0; i < x.Length; i++)
                {
                    ty[i] = tx[i];
                }
            }

generates

G_M52619_IG17:
       4D63C8               movsxd   r9d, r8d
       468B1488             mov      r10d, dword ptr [rax+4*r9]
       46891489             mov      dword ptr [rcx+4*r9], r10d
       41FFC0               inc      r8d
       413BD0               cmp      edx, r8d
       7FED                 jg       SHORT G_M52619_IG17

Note how in the first version ptrX and ptrY are reloaded from local variables on every iteration while in the second version they are not.

I think it's also worth looking at the non-pointer version:

            for (int i = 0; i < x.Length; i++)
            {
                y[i] = x[i];
            }

generates

G_M52619_IG04:
       4863CA               movsxd   ecx, edx
       448B448E10           mov      r8d, dword ptr [rsi+4*rcx+16]
       4489448810           mov      dword ptr [rax+4*rcx+16], r8d
       FFC2                 inc      edx
       81FAFFFFEF7F         cmp      edx, 0x7FEFFFFF
       7CE9                 jl       SHORT G_M52619_IG04

Usually only one of the necessary array bound checks is eliminated but in this particular case the JIT managed to eliminate both checks because the array lengths are known. The generating code is identical to the one generated by one of the pointer based versions.

[fo40225]

Thanks for the explanation.

So in this access array scenario, managed code and unmanaged code didn't have performance difference.

Can we say if JIT can eliminated the bound checks, there is nothing difference between managed and unsafe code?

[mikedn]

Can we say if JIT can eliminated the bound checks, there is nothing difference between managed and unsafe code?

Sort of. We've seen that both managed and unsafe versions can generate identical code so it would seem that the answer is simply yes. But in unsafe versions you may be able to do optimizations that aren't possible in the managed version.

In this particular case you could cast int* to long* and get a speed bump because it is faster to copy 8 bytes at a time instead of 4:

        [MethodImpl(MethodImplOptions.NoInlining)]
        private static void Test(int* px, int* py, long length)
        {
            long* lx = (long*)px;
            long* ly = (long*)py;

            for (long i = 0; i < length / 2; i++) // length / 2 assumes that length is a multiple of 2
                ly[i] = lx[i];
        }

These days you could achieve a similar effect without using unsafe code by using System.Numerics.Vector<T>. But before SIMD support was added to .NET there was no other way to do something like this, it isn't possible to cast int[] to long[] like you can cast int* to long*.

[jakobbotsch]

it isn't possible to cast int[] to long[] like you can cast int* to long*

private static void CopyFast(int[] from, int[] to)
{
    long[] fromAsLongs = new Caster {Int32Array = from}.Int64Array;
    long[] toAsLongs = new Caster {Int32Array = to}.Int64Array;

    // fromAsLongs.Length will be wrong. But since it's always larger
    // (as sizeof(int) < sizeof(long)), generated bounds checks are still
    // happy.
    int numLongs = from.Length/2;
    for (int i = 0; i < numLongs; i++)
        toAsLongs[i] = fromAsLongs[i];
}

[StructLayout(LayoutKind.Explicit)]
private struct Caster
{
    [FieldOffset(0)]
    public int[] Int32Array;
    [FieldOffset(0)]
    public long[] Int64Array;
}

Of course this trick is very dirty, unverifiable, type-safety breaking and relies on the layout of arrays of all types being equal. And it won't work for larger -> smaller, as the bounds checks will begin failing. But assuming the JIT hoists the bounds check, it should see that numLongs < toAsLongs.Length and fromAsLongs.Length and then it may be faster. I haven't actually checked the generated code, though.

EDIT: Hmm, I suppose the JIT does not hoist it as it would need two versions of the loop then.

[mikedn]

Of course this trick is very dirty, unverifiable, type-safety breaking and relies on the layout of arrays of all types being equal.

🙀, this makes unsafe code look very safe.

But assuming the JIT hoists the bounds check, it should see that numLongs < toAsLongs.Length and fromAsLongs.Length and then it may be faster.

I wonder what this does to loop cloning. I don't think I want to find out.

[jakobbotsch]

I wonder what this does to loop cloning. I don't think I want to find out.

I didn't know the JIT actually applied this optimization. Then it may be able to eliminate all bounds checks inside the loop.
If you do check it, feel free to share the results! 😃

[mikedn]

I didn't know the JIT actually applied this optimization.

Yep, RyuJIT does this. Though I find the feature questionable due to the large amount of code it generates.

Then it may be able to eliminate all bounds checks inside the loop.

I looked at the generated code (too large to include here, take a look at this gist if you want) and it seems that it would work. It simply decides whether to use the loop version with bound checks or the one without bound checks. Either version would work fine, as if no loop cloning was done.

[jakobbotsch]

I looked at the generated code (too large to include here, take a look at this gist if you want) and it seems that it would work.

Yeah, that actually looks pretty good. Better than the equivalent source. 😄
Though the hoisted checks look a little convoluted, but I have not checked if those could really be improved. And given that it's pure registers, there probably are no big speed implications.

[mikedn]

Yeah, that actually looks pretty good. Better than the equivalent source.

Note that I extracted the for loop to a separate method and assembly dump is only from that method.

Though the hoisted checks look a little convoluted, but I have not checked if those could really be improved. And given that it's pure registers, there probably are no big speed implications.

The null checks at the start seem useless. There also seems to be a redundant and possibly wrong check r8 >= 0 in G_M33861_IG03.

[fo40225]

In fact, if I want to do a array copy, I will use Array.Copy, Buffer.BlockCopy, Buffer.MemoryCopy

Those method will faster than unsafe code and I don't know way. maybe they have some black magic optimize in there.

Cast int array to long to double the copy operation looks very tricky. If I must do that I will use the System.Numerics.Vector<T> to do that SIMD operation. The code will look more reasonable.

The original sample code just want to show access array, not specific array copy.

Thanks all, I learned that I can use long to access array 8 bytes at once.

The struct Caster is awesome, never think before FieldOffset can be abused to do that.

About the bounds checks, the optimization role is loop condition can be determined and use the index to access array will eliminate all bounds checks. Do I understand right?