Critique my usage of manual iteration to check distance between all pairs of certain entities! :)

EDIT: CORRECTED THANKS FOR THE HELP!:
https://gist.github.com/Defunctionalize/75156fad916c8ae9ab334fcb7de364f1

LINK TO GIST
https://gist.github.com/Defunctionalize/9a5bf89dae26ae8016ead1e1128b0bc5
ORIGINAL POST:
I'm not necessarily saying this is an appropriate choice for implementing this specific task in a game, but would this work? It seems like this is adhering to all the constraints of the Burst compiler, right? Im working off of the manual iteration example in the 0.11 documentation

Points of note:

• My job stuct execute function is indexing into 2 chunks in memory instead of one -- will that screw anything up? Will this still be fast?
• Will the sub batching logic (chunk.Count is a subbatch) screw up this plan? Is this actually guaranteed to check all pairs of entities?
• Is there anything better I can be doing than those duplicated variables (translations, translations2 etc)? I'm scared of breaking Burst..
• is 32 the right choice for the innerloopbatch size? I couldnt find any guidelines on how to set that number

here it is - code to check, for each entity with this component, whether or not there is at least one other entity within its threshold distance that has this component

Code (CSharp):

1.  
2. using System.Linq;
3. using Unity.Burst;
4. using Unity.Collections;
5. using Unity.Entities;
6. using Unity.Jobs;
7. using Unity.Mathematics;
8. using Unity.Transforms;
9.  
10. public struct MyComponent : IComponentData
11. {
12.     public float threshold;
13.     public bool closeEnough;
14. }
15.  
16. public class CheckAllPairsSystem : SystemBase
17. {
18.     [BurstCompile]
19.     struct CheckAllPairsJob : IJobParallelFor
20.     {
21.         [DeallocateOnJobCompletion] public NativeArray<ArchetypeChunk> Chunks;
22.         [DeallocateOnJobCompletion] public NativeArray<int2> Combos;
23.         public ArchetypeChunkComponentType<Translation> TranslationType;
24.         [ReadOnly] public ArchetypeChunkComponentType<MyComponent> MyComponentType;
25.    
26.         public void Execute(int comboIndex)
27.         {
28.             var combo = Combos[comboIndex];
29.             var chunk = Chunks[combo.x];
30.             var chunk2 = Chunks[combo.y];
31.             var translations = chunk.GetNativeArray(TranslationType);
32.             var translations2 = chunk2.GetNativeArray(TranslationType);
33.             var mycomponents = chunk.GetNativeArray(MyComponentType);
34.             var mycomponents2 = chunk2.GetNativeArray(MyComponentType);
35.             var instanceCount = chunk.Count;
36.             var instanceCount2 = chunk2.Count;
37.  
38.             for (int i = 0; i < instanceCount; i++)
39.             {
40.                 for (int j = 0; j < instanceCount2; j++)
41.                 {
42.                     // if checking against the same chunk, dont check against the same index,
43.                     // because that would be the same entity
44.                     if (combo.x == combo.y && i == j) { continue; }
45.  
46.                     var a = mycomponents[i];
47.                     var aTrans = translations[i];
48.                     var b = mycomponents2[j];
49.                     var bTrans = translations2[j];
50.                     var distance = math.distance(aTrans.Value, bTrans.Value);
51.                     a.closeEnough = a.closeEnough || distance < a.threshold;
52.                     b.closeEnough = b.closeEnough || distance < b.threshold;
53.                 }
54.             }
55.         }
56.    
57.     }
58.  
59.     EntityQuery query;
60.  
61.     protected override void OnCreate()
62.     {
63.         query = GetEntityQuery(typeof(MyComponent), ComponentType.ReadOnly<Translation>());
64.     }
65.  
66.     protected override void OnUpdate()
67.     {
68.         var translationType = GetArchetypeChunkComponentType<Translation>(true);
69.         var myComponentType =    GetArchetypeChunkComponentType<MyComponent>();
70.         var chunks = query.CreateArchetypeChunkArray(Allocator.TempJob);
71.         var comboSeq = (
72.             from i in Enumerable.Range(0, chunks.Length)
73.             from j in Enumerable.Range(0, chunks.Length)
74.             select new int2(i, j)).ToArray();
75.         var combos = new NativeArray<int2>(comboSeq.Length, Allocator.TempJob);
76.         combos.CopyFrom(comboSeq);
77.    
78.         var checkAlignedJob = new CheckAllPairsJob()
79.         {
80.             Chunks = chunks,
81.             Combos = combos,
82.             MyComponentType = myComponentType,
83.             TranslationType = translationType
84.         };
85.         checkAlignedJob.Schedule(combos.Length,32, this.Dependency);
86.     }
87. }
88.  
89.  

 

I haven't read the code thoroughly yet but here are some quick notes:

• Use

  math.distancesq

  instead of distance if you just want to compare, it is a lot cheaper
• Don't use LINQ queries, especially in update. It is expensive and generates a lot of memory garbage that make GC spikes in your game.

I think you don't need manual iteration for this and there's a simpler way, I'll check back later

For inner loop batch count, the general rule is lower number for heavy jobs, and higher number for lighter jobs (although usually I never get benefits past 64). But you'd need to test and profile yourself to get the best values for your specific job.

 

Cool. the LINQ in the update was specifically something I wanted feedback on
Oh, and when you say light vs heavy jobs, do you mean memory or compute heavy?

 

Compute heavy

 

I'm sorry to say this, but your code isn't even close to working the way you want it to.
Problem 1) Inside your inner loop, you are only ever calculating values that get assigned to stack variables in the inner loop scope. Since those variables get destroyed each loop iteration, you are effectively doing nothing. To fix that, you would need to write a and b back to the arrays, which you can't because...
Problem 2) You marked MyComponentType as ReadOnly. You are going to have to get rid of that, which will cause more problems because...
Problem 3) You are allowing the same chunk to be accessed by two threads at once. That means you can't write back to your components without causing race conditions. If you actually bothered to run your code, you would have received an error about accessing Chunks in parallel in a non-thread-safe manner.

My suggestion would be to forget about multithreading and just use IJob for now and see if you can get the algorithm to work with Burst. And don't worry so much about creating local variables and whatnot. Burst is surprisingly good at figuring out your intent and optimizing out a lot of those variables in clever ways.

Once you get that working, come back and we can discuss options for multi-threading. This kind of problem is not the most trivial to multi-thread. Most likely you will need some intermediate buffers, or a NativeStream, or perhaps a clever acceleration structure that can spatially partition elements and perform spatially distinct queries in parallel.

 

Outstanding! Thank you! You're right about my not having run it yet - guilty

But this is precisely the form of criticism I was hoping would be leveled. I really appreciate that you took the time to read it and tear it apart. I apologize for leaving in the low hanging fruit (problems 1 and 2)

 

Huh. I was assuming those stack bindings were to array references

 

They are not ref returns.

 

Cool! Well, I modified it to be a bit less parallel (but still parallel) until I can come up with some clever strategies to make that combinatorial approach work.
More importantly I actually ran it to make sure it works

Thanks exceedingly, your criticism has been instructive and well reasoned.

https://gist.github.com/Defunctionalize/75156fad916c8ae9ab334fcb7de364f1

Code (CSharp):

1. using System.Linq;
2. using Unity.Burst;
3. using Unity.Collections;
4. using Unity.Entities;
5. using Unity.Jobs;
6. using Unity.Mathematics;
7. using Unity.Transforms;
8.  
9.  
10.  
11. [GenerateAuthoringComponent]
12. public struct MyThreshold : IComponentData
13. {
14.     public float threshold;
15. }
16.  
17.  
18. [GenerateAuthoringComponent]
19. public struct MyComponent : IComponentData
20. {
21.     public bool closeEnough;
22. }
23.  
24.  
25.  
26. public class CheckAllPairsSystem : SystemBase
27. {
28.     [BurstCompile]
29.     struct CheckAllPairsJob : IJobParallelFor
30.     {
31.         [DeallocateOnJobCompletion] public NativeArray<ArchetypeChunk> Chunks;
32.         [ReadOnly] public ArchetypeChunkComponentType<Translation> TranslationType;
33.         [ReadOnly] public ArchetypeChunkComponentType<MyThreshold> MyThresholdType;
34.         public ArchetypeChunkComponentType<MyComponent> MyComponentType;
35.      
36.         public void Execute(int jobIndex)
37.         {
38.             var chunk = Chunks[jobIndex];
39.             var translations = chunk.GetNativeArray(TranslationType);
40.             var mycomponents = chunk.GetNativeArray(MyComponentType);
41.             var mythresholds = chunk.GetNativeArray(MyThresholdType);
42.  
43.             var instanceCount = chunk.Count;
44.             ArchetypeChunk chunk2;
45.             NativeArray<Translation> translations2;
46.             int instanceCount2;  
47.          
48.             for (int i = 0; i < Chunks.Length; i++)
49.             {
50.                 chunk2 = Chunks[i];
51.                 translations2 = chunk2.GetNativeArray(TranslationType);
52.                 instanceCount2 = chunk2.Count;
53.  
54.                 for (int j = 0; j < instanceCount; j++)
55.                 {
56.                     for (int k = 0; k < instanceCount2; k++)
57.                     {
58.  
59.                         // if checking against the same chunk, dont check against the same index,
60.                         // because that would be the same entity
61.                         if (i == jobIndex && j == k) { continue; }
62.  
63.                         var a = mycomponents[j];
64.                         var aTheshold = mythresholds[j];
65.                         var aTrans = translations[j];
66.                         var bTrans = translations2[k];
67.                         var distance = math.distance(aTrans.Value, bTrans.Value);
68.                         a.closeEnough = a.closeEnough || distance < aTheshold.threshold;
69.                         mycomponents[j] = a;
70.                     }
71.                 }
72.             }
73.         }
74.      
75.     }
76.  
77.     EntityQuery query;
78.  
79.     protected override void OnCreate()
80.     {
81.         query = GetEntityQuery(typeof(MyComponent),
82.             ComponentType.ReadOnly<MyThreshold>(),
83.             ComponentType.ReadOnly<Translation>());
84.     }
85.  
86.     protected override void OnUpdate()
87.     {
88.         var translationType = GetArchetypeChunkComponentType<Translation>(true);
89.         var myComponentType =    GetArchetypeChunkComponentType<MyComponent>();
90.         var myThesholdType =    GetArchetypeChunkComponentType<MyThreshold>(true);
91.         var chunks = query.CreateArchetypeChunkArray(Allocator.TempJob);
92.      
93.         var checkAlignedJob = new CheckAllPairsJob()
94.         {
95.             Chunks = chunks,
96.             MyComponentType = myComponentType,
97.             MyThresholdType = myThesholdType,
98.             TranslationType = translationType
99.         };
100.         this.Dependency = checkAlignedJob.Schedule(chunks.Length,32, this.Dependency);
101.     }
102. }
103.  
104.