Burst Fumbles over NativeArray indexing but not pointers

DreamingImLatios · Aug 17, 2022

Context: I'm experimenting with manually unrolling a single-axis sweep-and-prune algorithm. This particular attempt writes pairs packed as a ulong into a cache buffer and then conditionally increments the write index into the cache buffer. There's a few variants of this technique I'm still playing with, but I wanted to highlight something I discovered.

When using NativeArray indexing, I got several instructions generated in the inner loop between tests. However, when I grabbed pointers from the NativeArrays and indexed them with ulong directly, things cleaned up quite a bit and I got more consistent usage of registers. The version using pointers performed better too, and was more or less the codegen I was trying to achieve.

Am I being naive? Is this an issue with NativeArray? Is this an issue with Burst?

I'm using Burst 1.8 prev 2 for this.

Code:

Code (CSharp):

public struct EntityPair : IEquatable<EntityPair>

{

public Entity a;

public Entity b;

public EntityPair(Entity aa, Entity bb)

{

a = aa;

b = bb;

}

public bool Equals(EntityPair other)

{

return a == other.a && b == other.b;

}

public static bool operator ==(EntityPair a, EntityPair b)

{

return a.Equals(b);

}

public static bool operator !=(EntityPair a, EntityPair b)

{

return !a.Equals(b);

}

}

[BurstCompile(OptimizeFor = OptimizeFor.Performance)]

public struct UnrolledSweepPoor : IJob

{

[ReadOnly] public NativeArray<float> xmins;

[ReadOnly] public NativeArray<float> xmaxs;

[ReadOnly] public NativeArray<float4> minYZmaxYZsFlipped;

[ReadOnly] public NativeArray<Entity> entities;

public NativeList<EntityPair> overlaps;

public void Execute()

{

Hint.Assume(xmins.Length == xmaxs.Length);

Hint.Assume(xmins.Length == minYZmaxYZsFlipped.Length);

var hitCache = new NativeArray<ulong>(1024, Allocator.Temp, NativeArrayOptions.UninitializedMemory);

int nextHitIndex = 0;

for (int i = 0; i < xmins.Length - 1; i++)

{

float4 current = -minYZmaxYZsFlipped[i].zwxy;

float4 currentX = xmaxs[i];

int j = i + 1;

ulong pair = (((ulong)i) << 32) | (uint)j;

ulong final = (((ulong)i) << 32) | ((uint)xmins.Length);

while (pair + 3 < final)

{

var nextMins = xmins.ReinterpretLoad<float4>((int)j);

if (Hint.Unlikely(math.any(nextMins >= currentX)))

break;

hitCache[nextHitIndex] = pair;

if (math.bitmask(current < minYZmaxYZsFlipped[j]) == 0)

nextHitIndex++;

pair++;

hitCache[nextHitIndex] = pair;

if (math.bitmask(current < minYZmaxYZsFlipped[j + 1]) == 0)

nextHitIndex++;

pair++;

hitCache[nextHitIndex] = pair;

if (math.bitmask(current < minYZmaxYZsFlipped[j + 2]) == 0)

nextHitIndex++;

pair++;

hitCache[nextHitIndex] = pair;

if (math.bitmask(current < minYZmaxYZsFlipped[j + 3]) == 0)

nextHitIndex++;

pair++;

j += 4;

if (Hint.Unlikely(nextHitIndex >= 1020))

{

Drain(hitCache, nextHitIndex);

nextHitIndex = 0;

}

}

while (pair < final && xmins[(int)j] < currentX.x)

{

hitCache[nextHitIndex] = pair;

if (math.bitmask(current < minYZmaxYZsFlipped[j]) == 0)

nextHitIndex++;

pair++;

j++;

}

if (nextHitIndex >= 1020)

{

Drain(hitCache, nextHitIndex);

nextHitIndex = 0;

}

}

Drain(hitCache, nextHitIndex);

}

[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.NoInlining)]

void Drain(NativeArray<ulong> cache, int cacheCount)

{

for (int i = 0; i < cacheCount; i++)

{

ulong pair = cache[i];

int first = (int)(pair >> 32);

int second = (int)(pair & 0xffffffff);

overlaps.Add(new EntityPair(entities[first], entities[second]));

}

}

}

[BurstCompile(OptimizeFor = OptimizeFor.Performance)]

public struct UnrolledSweep : IJob

{

[ReadOnly] public NativeArray<float> xmins;

[ReadOnly] public NativeArray<float> xmaxs;

[ReadOnly] public NativeArray<float4> minYZmaxYZsFlipped;

[ReadOnly] public NativeArray<Entity> entities;

public NativeList<EntityPair> overlaps;

public unsafe void Execute()

{

Hint.Assume(xmins.Length == xmaxs.Length);

Hint.Assume(xmins.Length == minYZmaxYZsFlipped.Length);

var hitCache = new NativeArray<ulong>(1024, Allocator.Temp, NativeArrayOptions.UninitializedMemory);

ulong nextHitIndex = 0;

var hitCachePtr = (ulong*)hitCache.GetUnsafePtr();

var minMaxPtr = (float4*)minYZmaxYZsFlipped.GetUnsafeReadOnlyPtr();

for (int i = 0; i < xmins.Length - 1; i++)

{

float4 current = -minYZmaxYZsFlipped[i].zwxy;

float4 currentX = xmaxs[i];

ulong j = (ulong)i + 1;

ulong pair = (((ulong)i) << 32) | j;

ulong final = (((ulong)i) << 32) | ((uint)xmins.Length);

while (pair + 3 < final)

{

var nextMins = xmins.ReinterpretLoad<float4>((int)j);

if (Hint.Unlikely(math.any(nextMins >= currentX)))

break;

hitCachePtr[nextHitIndex] = pair;

if (math.bitmask(current < minMaxPtr[j]) == 0)

nextHitIndex++;

pair++;

hitCachePtr[nextHitIndex] = pair;

if (math.bitmask(current < minMaxPtr[j + 1]) == 0)

nextHitIndex++;

pair++;

hitCachePtr[nextHitIndex] = pair;

if (math.bitmask(current < minMaxPtr[j + 2]) == 0)

nextHitIndex++;

pair++;

hitCachePtr[nextHitIndex] = pair;

if (math.bitmask(current < minMaxPtr[j + 3]) == 0)

nextHitIndex++;

pair++;

j += 4;

if (Hint.Unlikely(nextHitIndex >= 1020))

{

Drain(hitCache, nextHitIndex);

nextHitIndex = 0;

}

}

while (pair < final && xmins[(int)j] < currentX.x)

{

hitCachePtr[nextHitIndex] = pair;

if (math.bitmask(current < minMaxPtr[j]) == 0)

nextHitIndex++;

pair++;

j++;

}

if (nextHitIndex >= 1020)

{

Drain(hitCache, nextHitIndex);

nextHitIndex = 0;

}

}

Drain(hitCache, nextHitIndex);

}

[System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.NoInlining)]

void Drain(NativeArray<ulong> cache, ulong cacheCount)

{

for (int i = 0; i < (int)cacheCount; i++)

{

ulong pair = cache[i];

int first = (int)(pair >> 32);

int second = (int)(pair & 0xffffffff);

overlaps.Add(new EntityPair(entities[first], entities[second]));

}

}

}

NativeArray gen (poor)

Code (CSharp):

.LBB7_16:

=== FindPairsSimplified.cs(1424, 1) if (Hint.Unlikely(math.any(nextMins >= currentX)))

lea rax, [r13 + r14]

mov rdx, qword ptr [rcx]

.Ltmp96:

add rdx, r9

.Ltmp97:

vcmpleps xmm0, xmm6, xmmword ptr [rdx + 4*r14]

vmovmskps edx, xmm0

test edx, edx

jne .LBB7_5

=== FindPairsSimplified.cs(1428, 1) if (math.bitmask(current < minYZmaxYZsFlipped[j]) == 0)

lea rdi, [r13 + r14 + 3]

.Ltmp98:

movsxd rdx, r8d

mov qword ptr [r12 + 8*rdx], rax

.Ltmp99:

mov rax, qword ptr [rcx + 112]

.Ltmp100:

vcmpltps xmm0, xmm7, xmmword ptr [rax + rbx]

vmovmskps esi, xmm0

cmp esi, 1

adc edx, 0

.Ltmp101:

lea rsi, [r13 + r14 + 1]

movsxd rdx, edx

mov qword ptr [r12 + 8*rdx], rsi

.Ltmp102:

lea esi, [r15 + r14 + 2]

movsxd rsi, esi

shl rsi, 4

.Ltmp103:

=== FindPairsSimplified.cs(1433, 1) if (math.bitmask(current < minYZmaxYZsFlipped[j + 1]) == 0)

vcmpltps xmm0, xmm7, xmmword ptr [rax + rsi]

vmovmskps esi, xmm0

cmp esi, 1

adc edx, 0

.Ltmp104:

lea rsi, [r13 + r14 + 2]

movsxd rdx, edx

mov qword ptr [r12 + 8*rdx], rsi

.Ltmp105:

lea esi, [r15 + r14 + 3]

movsxd rsi, esi

shl rsi, 4

.Ltmp106:

=== FindPairsSimplified.cs(1438, 1) if (math.bitmask(current < minYZmaxYZsFlipped[j + 2]) == 0)

vcmpltps xmm0, xmm7, xmmword ptr [rax + rsi]

vmovmskps esi, xmm0

cmp esi, 1

adc edx, 0

.Ltmp107:

movsxd r8, edx

mov qword ptr [r12 + 8*r8], rdi

.Ltmp108:

lea edx, [r15 + r14 + 4]

movsxd rdx, edx

shl rdx, 4

.Ltmp109:

=== FindPairsSimplified.cs(1443, 1) if (math.bitmask(current < minYZmaxYZsFlipped[j + 3]) == 0)

vcmpltps xmm0, xmm7, xmmword ptr [rax + rdx]

vmovmskps eax, xmm0

cmp eax, 1

adc r8d, 0

=== FindPairsSimplified.cs(1448, 1) if (Hint.Unlikely(nextHitIndex >= 1020))

cmp r8d, 1019

jg .LBB7_18

.LBB7_3:

=== FindPairsSimplified.cs(1421, 1) while (pair + 3 < final)

lea rax, [r13 + r14 + 7]

add r14, 4

add rbx, 64

cmp rax, qword ptr [rbp - 8]

jb .LBB7_16

jmp .LBB7_4

.LBB7_18:

=== FindPairsSimplified.cs(1450, 1) Drain(hitCache, nextHitIndex);

mov qword ptr [rbp - 64], r12

vmovups xmmword ptr [rbp - 56], xmm8

mov rax, qword ptr [rbp]

mov qword ptr [rbp - 40], rax

mov eax, dword ptr [rbp + 8]

mov dword ptr [rbp - 32], eax

mov eax, dword ptr [rbp + 12]

mov dword ptr [rbp - 28], eax

mov qword ptr [rbp - 24], 0

mov qword ptr [rbp - 16], 2

lea rdx, [rbp - 64]

mov rsi, r9

mov qword ptr [rbp - 96], r10

mov rdi, r11

call "OptimizationAdventures.UnrolledSweepPoor.Drain(OptimizationAdventures.UnrolledSweepPoor* this, Unity.Collections.NativeArray`1<ulong> cache, int cacheCount) -> void_9136ab577d8b85bf6b250ef6053d3a6d from OptimizationAdventures, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null@@24"

mov r11, rdi

mov r10, qword ptr [rbp - 96]

mov r9, rsi

mov rcx, qword ptr [rbp - 72]

xor r8d, r8d

jmp .LBB7_3

Pointer-based gen (faster)

Code (CSharp):

.LBB7_23:

=== FindPairsSimplified.cs(1329, 1) if (Hint.Unlikely(math.any(nextMins >= currentX)))

lea rax, [r13 + r14]

.Ltmp95:

mov rbx, qword ptr [rcx]

mov rdx, r12

and rdx, rsi

.Ltmp96:

vcmpleps xmm0, xmm6, xmmword ptr [rbx + rdx]

vmovmskps edx, xmm0

test edx, edx

jne .LBB7_6

=== FindPairsSimplified.cs(1332, 1) hitCachePtr[nextHitIndex] = pair;

lea rdx, [r13 + r14 + 3]

mov qword ptr [rdi + 8*r8], rax

=== FindPairsSimplified.cs(1333, 1) if (math.bitmask(current < minMaxPtr[j]) == 0)

vcmpltps xmm0, xmm7, xmmword ptr [r15 + 4*r12]

vmovmskps eax, xmm0

cmp eax, 1

adc r8, 0

=== FindPairsSimplified.cs(1337, 1) hitCachePtr[nextHitIndex] = pair;

lea rax, [r13 + r14 + 1]

mov qword ptr [rdi + 8*r8], rax

=== FindPairsSimplified.cs(1338, 1) if (math.bitmask(current < minMaxPtr[j + 1]) == 0)

vcmpltps xmm0, xmm7, xmmword ptr [r15 + 4*r12 + 16]

vmovmskps eax, xmm0

cmp eax, 1

adc r8, 0

=== FindPairsSimplified.cs(1342, 1) hitCachePtr[nextHitIndex] = pair;

lea rax, [r13 + r14 + 2]

mov qword ptr [rdi + 8*r8], rax

=== FindPairsSimplified.cs(1343, 1) if (math.bitmask(current < minMaxPtr[j + 2]) == 0)

vcmpltps xmm0, xmm7, xmmword ptr [r15 + 4*r12 + 32]

vmovmskps eax, xmm0

cmp eax, 1

adc r8, 0

=== FindPairsSimplified.cs(1347, 1) hitCachePtr[nextHitIndex] = pair;

mov qword ptr [rdi + 8*r8], rdx

=== FindPairsSimplified.cs(1348, 1) if (math.bitmask(current < minMaxPtr[j + 3]) == 0)

vcmpltps xmm0, xmm7, xmmword ptr [r15 + 4*r12 + 48]

vmovmskps eax, xmm0

cmp eax, 1

adc r8, 0

=== FindPairsSimplified.cs(1353, 1) if (Hint.Unlikely(nextHitIndex >= 1020))

cmp r8, 1019

ja .LBB7_17

.LBB7_4:

=== FindPairsSimplified.cs(1326, 1) while (pair + 3 < final)

lea rax, [r13 + r14 + 7]

add r14, 4

add r12, 16

cmp rax, qword ptr [rbp - 8]

jb .LBB7_23

jmp .LBB7_5

.LBB7_17:

=== FindPairsSimplified.cs(1355, 1) Drain(hitCache, nextHitIndex);

mov qword ptr [rbp - 64], rdi

vmovups xmmword ptr [rbp - 56], xmm8

mov rax, qword ptr [rbp]

mov qword ptr [rbp - 40], rax

mov eax, dword ptr [rbp + 8]

mov dword ptr [rbp - 32], eax

mov eax, dword ptr [rbp + 12]

mov dword ptr [rbp - 28], eax

mov qword ptr [rbp - 24], 0

mov qword ptr [rbp - 16], 2

lea rdx, [rbp - 64]

mov rbx, r10

mov qword ptr [rbp - 96], r11

mov rsi, r9

call "OptimizationAdventures.UnrolledSweep.Drain(OptimizationAdventures.UnrolledSweep* this, Unity.Collections.NativeArray`1<ulong> cache, ulong cacheCount) -> void_9136ab577d8b85bf6b250ef6053d3a6d from OptimizationAdventures, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null@@24"

mov r9, rsi

movabs rsi, 8589934588

mov r11, qword ptr [rbp - 96]

mov r10, rbx

mov rcx, qword ptr [rbp - 72]

xor r8d, r8d

jmp .LBB7_4

Zuntatos · Aug 17, 2022

Check what you get if you make `i` an uint and `j` an ulong in the UnrolledSweepPoor. And make sure that with that change the loop comparison is a uint comparison without promoting the comparison to long. You'll still have to cast to (int) on every indexer though, because sadly there isn't indexer overloading in C#. Maybe with Hint.Assumes() you can promise the compiler that the ulong is in int range.

I don't have a benchmark environment with your code, so I can't check that. But it does give interesting code gen differences compared to int i, j.

sheredom · Aug 17, 2022

Have you got some perf data running each one to show please? Just curious before I dive in what the delta is.

DreamingImLatios · Aug 17, 2022

sheredom said: ↑

Have you got some perf data running each one to show please?
Click to expand...

1000: Poor - 212.7 microseconds, Pointers - 156.0 microseconds
2000: Poor - 1.534 milliseconds, Pointers - 1.082 milliseconds
5000: Poor - 3.443 milliseconds, Pointers - 2.502 milliseconds
10000: Poor - 14.36 milliseconds, Pointers - 10.01 milliseconds

For additional context, I have a few other variants in my test lineup. I have an "OptimalOrder" which is what I've been using for my projects and rather than sign flip the max values of the y and z components, it uses shuffles to group the mins and maxes into separate registers for both comparison boxes. That used to be the fastest until the newest Burst versions. "Poor" performs worse than that. With the latest Burst versions, two other variants all of a sudden started performing better. There's one that uses the max component sign flipping trick these unrolled versions also use, and there's one which also uses a sentinel box to terminate the loop without counter checks. Those also dispatch immediately on found pairs. The pointer-based unrolled version outperforms both of these by a very slim (a couple percent) margin.

I guess what surprises me the most is that following the conventional API tripped up Burst so much, even though I've also seen Burst completely change the way two nested loops work and the variables involved such that it would be difficult to associate with the original code (but the results were correct and fast ). But again, I could just be naive here. I'm no expert in the rules of C# or IL. I just have a general idea of what I want to see in the Burst inspector and how that might correlate to what I am measuring in VTune.

Speaking of VTune, here's the pointer-based version running on 5000 elements 5000 times:

sheredom · Aug 18, 2022

One difference between both is the int index in the NativeArray case, and the ulong in the pointer case. With the int, you see that before it actually stores into the hitCache it is doing movsxd - it is sign extending the integer up to a 64-bit index (which isn't free!).

It might be enough to make that a uint and cast it to int before the indexing on the NativeArray - not ideal but worth checking.

DreamingImLatios · Aug 18, 2022

sheredom said: ↑

One difference between both is the int index in the NativeArray case, and the ulong in the pointer case. With the int, you see that before it actually stores into the hitCache it is doing movsxd - it is sign extending the integer up to a 64-bit index (which isn't free!).

It might be enough to make that a uint and cast it to int before the indexing on the NativeArray - not ideal but worth checking.
Click to expand...

Yeah. Seeing that sign extension was what led me to explore using pointers in the first place. With pointers, the code is perfectly clear about what it is doing. With NativeArrays that require casting on every index operation, that's just fighting the API and obfuscating things.

I'm getting the performance I was looking for, so I don't have any real incentive to try any hacks and workarounds because I already have one that gets exactly what I want. The reason I posted this is because it was a surprising performance pitfall that a lot of people are going to fall into, because that's what the API and all examples suggest doing.

Spy-Master · Aug 19, 2022

Zuntatos said: ↑

You'll still have to cast to (int) on every indexer though, because sadly there isn't indexer overloading in C#.
Click to expand...

Code (CSharp):

public unsafe struct UnsafeList<T> where T : unmanaged

{

public T* Ptr;

public int Length;

public T this[int index]

{

readonly get => Ptr[index];

set => Ptr[index] = value;

}

public T this[uint index]

{

readonly get => Ptr[index];

set => Ptr[index] = value;

}

public T this[long index]

{

readonly get => Ptr[index];

set => Ptr[index] = value;

}

public T this[ulong index]

{

readonly get => Ptr[index];

set => Ptr[index] = value;

}

public T this[string index]

{

readonly get => Ptr[index.Length];

set => Ptr[index.Length] = value;

}

public T this[HttpClient index]

{

readonly get => Ptr[(int)index.PostAsync("https://google.com", new StringContent("")).Result.StatusCode];

set => Ptr[index.GetStreamAsync("https://forum.unity.com").Result.Length] = value;

}

}

public unsafe struct NativeList<T> where T : unmanaged

{

internal UnsafeList<T>* m_ListData;

public T this[int index]

{

readonly get => (*m_ListData)[index];

set => (*m_ListData)[index] = value;

}

public T this[uint index]

{

readonly get => (*m_ListData)[index];

set => (*m_ListData)[index] = value;

}

public T this[long index]

{

readonly get => (*m_ListData)[index];

set => (*m_ListData)[index] = value;

}

public T this[ulong index]

{

readonly get => (*m_ListData)[index];

set => (*m_ListData)[index] = value;

}

}

Zuntatos · Aug 19, 2022

dude_rtfm said: ↑

[...]
Click to expand...

Hah, point taken. I've even overloaded the indexer on my own UnsafeNativeArray

Search Unity

Burst Fumbles over NativeArray indexing but not pointers

DreamingImLatios

Zuntatos

sheredom

Unity Technologies

DreamingImLatios

sheredom

Unity Technologies

DreamingImLatios

Spy-Master

Zuntatos

Search Unity

Unity ID

Useful Searches

Burst Fumbles over NativeArray indexing but not pointers

Unity Technologies

Unity Technologies