Question Please help me understand why second job is slower

I have decided to implement Conway's Game of life using the job system and optimise it best as I can.
I have created the first job GameOfLifeJob (source code below). It uses pre-calculated codes for neighbours so there are no ifs checking for map border. It works quite well then I'm using select from math to set alive or dead state. There is another job that then copies this state back to tiles.
Then I have decided to try to get rid of this select. So I came with an idea to also precalculate dead alive state for all combinations of neighbours and current cell alive state and store it int blob asset. Then I calculate neighbours and current cell alive code and read it from this array.
I do not understand why this is much slower than the previous approach. About 20% slower.
Is math.select so fast it is not worth optimising?

Code (CSharp):

1.  
2. [BurstCompile]
3.     public struct GameOfLifeJob:IJobParallelFor
4.     {
5.  
6.         [ReadOnly] public NativeArray<MapTile> Tiles;
7.         [ReadOnly] public BlobAssetReference<MapDataBlob> MapBlob;
8.  
9.         [WriteOnly] public NativeArray<byte> State;
10.         public void Execute(int index)
11.         {
12.             var tile = Tiles[index];
13.             var directionsStartEnd = MapBlob.Value.CodeStartEndIndex[tile.availableDirectionsCode];
14.             byte aliveNeighbours = 0;
15.             for (int i = directionsStartEnd.startIndex; i < directionsStartEnd.endIndex; i++)
16.             {
17.                 var direction = MapBlob.Value.DirectionData[i];
18.                 var newTile = Tiles[index + direction.IndexOffset];
19.                 aliveNeighbours += newTile.isOccupied;
20.             }
21.  
22.             State[index] = (byte) math.select(0, 1,
23.                 (tile.isOccupied == 1 && aliveNeighbours == 2) || aliveNeighbours == 3);
24.  
25.  
26.         }
27.  
28.     }
29.     [BurstCompile]
30.     public struct GameOfLifePrecalculatedJob:IJobParallelFor
31.     {
32.  
33.         [ReadOnly] public NativeArray<MapTile> Tiles;
34.         [ReadOnly] public BlobAssetReference<MapDataBlob> MapBlob;
35.         [WriteOnly] public NativeArray<byte> State;
36.  
37.         public void Execute(int index)
38.         {
39.             var tile = Tiles[index];
40.             var directionsStartEnd = MapBlob.Value.CodeStartEndIndex[tile.availableDirectionsCode];
41.             int code = tile.isOccupied << 8;
42.             for (int i = directionsStartEnd.startIndex,bit = 0; i < directionsStartEnd.endIndex; i++,bit++)
43.             {
44.                 var direction = MapBlob.Value.DirectionData[i];
45.                 var newTile = Tiles[index + direction.IndexOffset];
46.                 code += newTile.isOccupied << bit;
47.             }
48.  
49.             State[index] = MapBlob.Value.LifeState[code];
50.  
51.         }
52.  
53.     }

 

I have somehow the same result as for performance.https://forum.unity.com/threads/a-fast-blobcurve.985941/
By access blob memory the second time for some pre-calculated data make it slower.
re-calculate them may be the better choice, as long as your calculation is less than several instructions. The difference is not easy to compare it depends on your cpu's cache status and the size of blob data. continues memory access is always better.

And yes, math.select is fast. Much better than

c?a:b

in most case. as math.select involves absolutely no branching. When a or b is an expression instead of a simple variable

c?a:b

is very likely to generate branch. because the compiler does not know if there are alias or maybe expression a could change value of b.
with select both a and b are pre-calculated before passing to the function so there's no branch for sure.

also select can be auto vectorized to operate on 4 elements at a time (SIMD) by burst.
you first job look perfectly fine to be auto vectorized

 

math.select is typically faster than a memory read, especially if the memory read misses L1 (which I suspect given the performance impact despite the operation happening in the outer loop).

 

Thank you for your detailed replay. So right now slowest part is assigning the result to the array. This job takes about 1.5 ms when I have replaced:

State[index] = (byte) math.select(0, 1, (tile.isOccupied == 1 && aliveNeighbours == 2) || aliveNeighbours == 3);
with
tile.isOccupied = (byte) math.select(0, 1, (tile.isOccupied == 1 && aliveNeighbours == 2) || aliveNeighbours == 3);

When assigning to array this job takes about 25 ms. Does assign to array is so slow or is it due to false sharing or burst compiler is so clever to detect that this code does nothing meaningful and just does not run it at all?

 

Probably all of the above. You can check the Burst inspector to see if it is stripping that logic. I can't comment much on the others as I don't know your data layouts.

 

Yes! burst compiler is so clever to detect that this code does nothing meaningful and just does not run it at all.
Same as my test in curve. I was once thinking my curve is 300 times faster than unity's curve. But the job turns out to be constant timed no matter how large is the input data size.

 

Also, If performance is so critical. you can try stack allocate an array of bytes store calculation data in it. and process data in batch and use UnsafeUtility.MemCpy to pass data back.
Something like

Code (CSharp):

1.  
2.         public struct MapTile
3.         {
4.             public const int ByteSize = 5;
5.             public int availableDirectionsCode;
6.             public byte isOccupied;
7.         }
8.         public struct MapDataBlob
9.         {
10.             public BlobArray<StartEnd> CodeStartEndIndex;
11.             public BlobArray<Direction> DirectionData;
12.         }
13.         public struct StartEnd
14.         {
15.             public int startIndex;
16.             public int endIndex;
17.         }
18.         public struct Direction
19.         {
20.             public int IndexOffset;
21.         }
22.         [BurstCompile]
23.         public struct GameOfLifeJob : IJobParallelForBatch
24.         {
25.             [ReadOnly] public NativeArray<MapTile> Tiles;
26.             [ReadOnly] public BlobAssetReference<MapDataBlob> MapBlob;
27.             [WriteOnly] public NativeArray<byte> State;
28.             public int MapTileByteSize;
29.  
30.             unsafe public void Execute(int startIndex, int count)
31.             {
32.                 MapTile* tileCache = stackalloc MapTile[count];
33.                 UnsafeUtility.MemCpy(tileCache, Tiles.GetUnsafePtr<MapTile>(), count * MapTile.ByteSize);
34.                 byte* stateCache = stackalloc byte[count];
35.  
36.                 for (int j = 0; j < count; j++)
37.                 {
38.                     ref var tile = ref tileCache[j];
39.                     var directionsStartEnd = MapBlob.Value.CodeStartEndIndex[tile.availableDirectionsCode];
40.                     byte aliveNeighbours = 0;
41.                     for (int i = directionsStartEnd.startIndex; i < directionsStartEnd.endIndex; i++)
42.                     {
43.                         var direction = MapBlob.Value.DirectionData[i];
44.                         //var newTile = tileCache[j + direction.IndexOffset];//Not working
45.                         var newTile = Tiles[startIndex + j + direction.IndexOffset];
46.                         aliveNeighbours += newTile.isOccupied;
47.                     }
48.                     stateCache[j] = (byte)math.select(0, 1, (tile.isOccupied == 1 && aliveNeighbours == 2) || aliveNeighbours == 3);
49.                 }
50.                 UnsafeUtility.MemCpy(State.GetUnsafePtr<byte>(), stateCache, count);
51.             }
52.         }

I am just guessing your data type, MapTile.ByteSize can be some const value;

so with a larger batch, you should be reducing memory access dramatically.

I'm not sure if this is faster overall. But the inner loop will always hit cache. so it's blazing fast.
Let me know when you have a test result.
You may also try not to store data in a blob and calculate them on the fly. so you don't need to access remote memory in inner-loop at all. As I am not sure what it is in the blob, I am just keeping it as it is.

Edit:
As I look into your logic

var newTile = tileCache[j + direction.IndexOffset]

is not going to work. as you need to access adjacent row/colmn.
I changed it back to native array access.
Maybe you can figure out a local adherent container type(that's a bit of tricky).
or copy just a block of tile in batch intilization (2 extra column and 2 extra row, before and after batch range)

I am also thinking about an extended GOL game by the way.

May Mr. Conway rest in peace.

 

Yes, you are right MapTile has contact size. I will implement it today and let you know how it has affected the performance. Blob is calculated at the start stores mainly two things, an array of neighbour data like, index offset. And an array which index is a code, and it stores start and end index to neighbour data array for particular code. So every tile has a code that corresponds to its valid neighbours. I have implemented this for my flowfield. Probably I should strip down this array only to valid codes fo game of life map.

 

I have implemented it, but I had to make some modifications to make it to work. And it runs comparable to the previous version.

Code (CSharp):

1. public struct GameOfLifeBatchJob:IJobParallelForBatch
2.     {
3.  
4.         [NativeDisableParallelForRestriction]
5.         public NativeArray<MapTile> Tiles;
6.         [ReadOnly] public BlobAssetReference<MapDataBlob> MapBlob;
7.  
8.         [NativeDisableParallelForRestriction]
9.         [WriteOnly] public NativeArray<byte> State;
10.         unsafe public void Execute(int startIndex, int count)
11.         {
12.             MapTile* tileCache = stackalloc MapTile[count];
13.             NativeSlice<MapTile> mapTiles = new NativeSlice<MapTile>(Tiles, startIndex, count);
14.             NativeSlice<byte> states = new NativeSlice<byte>(State, startIndex, count);
15.             UnsafeUtility.MemCpy(tileCache, mapTiles.GetUnsafePtr<MapTile>(), count * MapTile.ByteSize);
16.             byte* stateCache = stackalloc byte[count];
17.  
18.             for (int j = 0; j < count; j++)
19.             {
20.                 ref var tile = ref tileCache[j];
21.                 var directionsStartEnd = MapBlob.Value.CodeStartEndIndex[tile.availableDirectionsCode];
22.                 byte aliveNeighbours = 0;
23.                 for (int i = directionsStartEnd.startIndex; i < directionsStartEnd.endIndex; i++)
24.                 {
25.                     var direction = MapBlob.Value.DirectionData[i];
26.                     //var newTile = tileCache[j + direction.IndexOffset];//Not working
27.                     var newTile = Tiles[startIndex + j + direction.IndexOffset];
28.                     aliveNeighbours += newTile.isOccupied;
29.                 }
30.                 stateCache[j] = (byte)math.select(0, 1, (tile.isOccupied == 1 && aliveNeighbours == 2) || aliveNeighbours == 3);
31.             }
32.             UnsafeUtility.MemCpy(states.GetUnsafePtr<byte>(), stateCache, count);
33.  
34.  
35.         }
36.  
37.     }

I was getting at line 45 of your code. And I have added NativeSlice, because I think Mem copy on tiles and State does not use start index so it always gets first elements of an array or I am missing something?

 

Oh I did not offset the memcpy, it should be:

UnsafeUtility.MemCpy(states.GetUnsafePtr<byte>()+startIndex, stateCache, count);

and the job

Code (CSharp):

1. public struct GameOfLifeBatchJob:IJobParallelForBatch
2.     {
3.         [NativeDisableParallelForRestriction]
4.         public NativeArray<MapTile> Tiles;
5.         [ReadOnly] public BlobAssetReference<MapDataBlob> MapBlob;
6.         [NativeDisableParallelForRestriction]
7.         [WriteOnly] public NativeArray<byte> State;
8.         unsafe public void Execute(int startIndex, int count)
9.         {
10.             MapTile* tileCache = stackalloc MapTile[count];
11.             NativeSlice<MapTile> mapTiles = new NativeSlice<MapTile>(Tiles, startIndex, count);
12.             NativeSlice<byte> states = new NativeSlice<byte>(State, startIndex, count);
13.             UnsafeUtility.MemCpy(tileCache, mapTiles.GetUnsafePtr<MapTile>(), count * MapTile.ByteSize);
14.             byte* stateCache = stackalloc byte[count];
15.             for (int j = 0; j < count; j++)
16.             {
17.                 ref var tile = ref tileCache[j];
18.                 var directionsStartEnd = MapBlob.Value.CodeStartEndIndex[tile.availableDirectionsCode];
19.                 byte aliveNeighbours = 0;
20.                 for (int i = directionsStartEnd.startIndex; i < directionsStartEnd.endIndex; i++)
21.                 {
22.                     var direction = MapBlob.Value.DirectionData[i];
23.                     //var newTile = tileCache[j + direction.IndexOffset];//Not working
24.                     var newTile = Tiles[startIndex + j + direction.IndexOffset];
25.                     aliveNeighbours += newTile.isOccupied;
26.                 }
27.                 stateCache[j] = (byte)math.select(0, 1, (tile.isOccupied == 1 && aliveNeighbours == 2) || aliveNeighbours == 3);
28.             }
29.             UnsafeUtility.MemCpy(states.GetUnsafePtr<byte>()+startIndex, stateCache, count);
30.         }
31.     }

Try run the job with a larger batch size like 512/1204

 

I can't offset pointer this way. There is an error saying that there is no +operator for void* and int.
Edit:
Ok I have cast it to byte* and it is working but when I turn on Burst it crashes.

 

sorry

UnsafeUtility.MemCpy(((byte*)states.GetUnsafePtr<byte>())+startIndex, stateCache, count);

 

I didn't refresh the page, As I wrote in edit now is crushes when burst compiled. Performnce when not bursted is comparable. Ok, I made mistake in MemCpy now it is working ad it is about 10% faster than my implementation.

 

Okay, there are 3 more remote memory read in your job

1. MapBlob.Value.DirectionData[i];

   
   

2. var directionsStartEnd = MapBlob.Value.CodeStartEndIndex[tile.availableDirectionsCode];

   
   

3. var newTile = Tiles[startIndex + j + direction.IndexOffset];

and 2 and 3 iteration count depends on directionsStartEnd;
by removing one of remove memory access you get about 10% performance gain.
if they are all somehow calculated local or pre-cached locally into some data chunk.
it could be much faster.
That basically what ECS and ArcheytypeChunk do.

 

I have found a way to get rid off use of BlobArrays in loop but strangely it is slower now. The previous version about 24-26ms and the new one a 36-40 ms.

Code (CSharp):

1. [BurstCompile]
2.     public struct GameOfLifeJob:IJobParallelForBatch
3.     {
4.  
5.         [ReadOnly] public NativeArray<MapTile> Tiles;
6.         [ReadOnly] public BlobAssetReference<MapDataBlob> MapBlob;
7.         [WriteOnly] public NativeArray<byte> State;
8.         unsafe public void Execute(int startIndex, int count)
9.         {
10.             byte* stateCache = stackalloc byte[count];
11.             int* directions = stackalloc int[8];
12.             UnsafeUtility.MemCpy(directions, ((int*)MapBlob.Value.MoveDirectionIndexOffset.GetUnsafePtr()), 32);
13.             for (int j = 0; j < count; j++)
14.             {
15.                 var tile = Tiles[startIndex+j];;
16.                 var code = tile.availableDirectionsCode;
17.                 byte aliveNeighbours = 0;
18.                 for (int i = 0; i < 8; i++)
19.                 {
20.                     var valid = (byte) ((code >> i ) & 1);
21.                     var direction = valid * directions[i];
22.                      var newTile = Tiles[startIndex + j + direction];
23.                     aliveNeighbours += (byte)(newTile.isOccupied * valid);
24.                 }
25.                
26.                 stateCache[j] = (byte)math.select(0, 1, (tile.isOccupied == 1 && aliveNeighbours == 2) || aliveNeighbours == 3);
27.             }
28.             UnsafeUtility.MemCpy(((byte*)State.GetUnsafePtr<byte>()) + startIndex, stateCache, count);
29.  
30.  
31.         }
32.  
33.     }

EDIT:
Strangely without Burst new solution is much faster than the old one, but with Burst the old one is faster.

 

Okay, so your blob is only 32 bytes in size. It will fit in cache anyway. Burst will magically make it fast because blob has no alias for sure. MemCpy is not necessary and will make it slower. and the new one did not cache tiles. so tile memory read is making it slower too. the 32 byte blob can be held in a struct and pass to the job directly by value. And process one row in each batch will allow you to cache Tile pretty well.
you just need to cache three rows of tile in stack row[n-1,n,n+1] when processing row[n].
And you will be able to work only on local data in the inner loop.

 

Yes, I have tied to do tiles in the local cache but still, it is slower than the older version.

Code (CSharp):

1. [BurstCompile]
2.     public struct GameOfLifeJob:IJobParallelForBatch
3.     {
4.  
5.         [ReadOnly] public NativeArray<MapTile> Tiles;
6.         [ReadOnly] public NativeArray<int> MoveDirectionIndexOffset;
7.         [WriteOnly] public NativeArray<byte> State;
8.         public unsafe void Execute(int startIndex, int count)
9.         {
10.             const byte one = 1;
11.             int shiftLeft = startIndex == 0 ? 0 : count;
12.             int shiftRight = startIndex == Tiles.Length - count - 1 ? 0 : count;
13.  
14.             var tilesCacheSize = count + shiftLeft + shiftRight;
15.             MapTile* tiles = stackalloc MapTile[tilesCacheSize];
16.             UnsafeUtility.MemCpy(tiles , ((MapTile*) Tiles.GetUnsafeReadOnlyPtr()) - shiftLeft + startIndex, MapTile.ByteSize*tilesCacheSize);
17.             byte* stateCache = stackalloc byte[count];
18.  
19.             for (var j = 0; j < count; j++)
20.             {
21.                 var index = shiftLeft + j;
22.                 ref var tile = ref tiles[index];
23.                 //var index = startIndex + j;
24.                 //var tile = Tiles[index];
25.                 int code = (tile.availableDirectionsCode);
26.  
27.                 byte aliveNeighbours = 0;
28.                 for (var i = 0; i < 8; i++)
29.                 {
30.                     var move = code >> i;
31.                     var valid = (byte) (move & one);
32.                     var direction = valid * MoveDirectionIndexOffset[i];
33.                     var newTile = tiles[index + direction];
34.                     //var newTile = Tiles[index + direction];
35.                     aliveNeighbours += (byte)(newTile.isOccupied * valid);
36.                 }
37.                 stateCache[j] = (byte)math.select(0, 1, (tile.isOccupied == 1 && aliveNeighbours == 2) || aliveNeighbours == 3);
38.             }
39.             UnsafeUtility.MemCpy(((byte*)State.GetUnsafePtr()) + startIndex, stateCache, count);
40.  
41.  
42.         }
43.  
44.     }

I am scheduling my job like this

Handle = lifeJob.ScheduleBatch(_Map.tiles.Length, mapWith);

My question is Does it guarantee that every job will have count number equal to mapWidth? Because it is necessary to process it row by row. When not Bursted on a single thread the new job is like 3 times faster. 68 ms to 214 ms on my machine.

 

So, Maybe Burst is doing the job of keeping Tile memory in the cache. MemCpy for reading will only make it slower?
Only the writing cache is necessary.
If that's the case you have already hit the upper limit somehow.

 

OK thank you for your help and explanation of everything. I have learned a lot from you .