Tip: Avoid allocating per entity

Nothing I'm about to say is ground breaking and realistically is pretty obvious as a lot of people are aware allocating in jobs can be costly, but sometimes it's a necessary evil as many algorithms require some type of temp storage. Often your algorithm works on 1 (or at least a primary) entity and the easiest way is to just allocate it on a per entity basis when you need.

So let's skip to the why you should not do that.

I was optimizing a very large algorithm (job) which had 7 NativeList + NativeArray + NativeMulitHashMaps allocated per entity and wanted to improve the performance so moved to grouping the allocations and this is the results.



By removing just 7 (all) allocations per entity I nearly doubled the performance of the algorithm.

The algorithm still needs these containers but instead of allocating per entity, they are allocated per chunk or in this particular case, per key in a NativeMultiHashMap and are simply cleared per iteration.

Code (CSharp):

1.  
2. /// <inheritdoc />
3. public void ExecuteNext(int team)
4. {
5.     // Creates our visibility computer
6.     var computer = new VisibilityPolygonComputer(Allocator.Temp);
7.     var hits = new NativeList<int>(Allocator.Temp);
8.     var polygon = new NativeList<float2>(Allocator.Temp);
9.     var observedObstructions = new NativeHashMap<Entity, RigidBody>(128, Allocator.Temp);
10.     var observerHistory = new NativeHashMap<int, Empty>(128, Allocator.Temp);
11.  
12.     this.VisionData.TryGetFirstValue(team, out var visionData, out var it);
13.     this.Execute(team, visionData, computer, polygon, observedObstructions, hits, observerHistory);
14.  
15.     while (this.VisionData.TryGetNextValue(out visionData, ref it))
16.     {
17.         this.Execute(team, visionData, computer, polygon, observedObstructions, hits, observerHistory);
18.     }
19. }
20.  
21. private void Execute(
22.     int team,
23.     VisionData visionData,
24.     VisibilityPolygonComputer computer,
25.     NativeList<float2> polygon,
26.     NativeHashMap<Entity, RigidBody> observedObstructions,
27.     NativeList<int> hits,
28.     NativeHashMap<int, Empty> observerHistoryMap)
29. {
30.     computer.Clear();
31.     hits.Clear();
32.     polygon.Clear();
33.     observedObstructions.Clear();
34.     observerHistoryMap.Clear();
35.  

As the previous benchmark showed simply grouping these allocations performance is significantly improved.
But hey! I only see 5 allocations your benchmark says 7 did you get rid of 2?
Yes and no. This brings me to the next part of this post how I did it.

Originally I was using IJobNativeMultiHashMapVisitKeyValue<TKey, TValue> and this is where the problem basically stemmed from. I had no way of re-using containers between entities. So for this particular algorithm I had no real other way other than write a custom job.

Introducing
IJobNativeMultiHashMapVisitUniqueKey<TKey>

As you can see from the code above, this allowed me to re-use containers between all unique keys and that is how I got rid of the first 5 allocations, but what about the last 2?

These were actually caused by

NativeHashMap<TKey, TValue>.GetKeyArray(Allocator.Temp)
and
NativeHashMap<TKey, TValue>.GetKeyValue(Allocator.Temp)

My solution to this was a very simple iterator that'd iterate all keys/values and which I could grab instead of passing it to an array the iterating the array.

Code (CSharp):

1.  
2. var values = map.GetValueArray(Allocator.Temp);
3.  
4. for (var i = 0; i < values.Length; i++)
5. {
6.    var val = values[i];
7.  

was replaced with

Code (CSharp):

1. var iterator = map.GetIterator();
2.  
3. while (iterator.MoveNext())
4. {
5.     var val = iterator.Value;

Unfortunately none of what I just showed is doable without some type of hack as everything is internal which is extremely frustrating. Thankfully I already wrote imposters for Native(Multi)HashMaps months ago which basically give me full internal access and let me easily implement these without any reflection or modifications to the package.

If anyone is actually has a similar need and is interested in either the job or the iterator let me know and I'll clean it up a little and post it.

TLDR: group allocations per chunk/key/etc get big performance gains.

 

I've wanted a hash map iterator like that recently. It felt strange to allocate for an array of keys/values each time, even if it is using the faster Allocator.Temp type.

 

Here ya go. Not thoroughly tested (haven't got around to write unit tests for it yet) but appears to work as expected in project for last 24 hours.

Iterator

Code (CSharp):

1. // <copyright file="NativeHashMapIterator.cs" company="BovineLabs">
2. //     Copyright (c) BovineLabs. All rights reserved.
3. // </copyright>
4.  
5.  
6. namespace BovineLabs.Common.Collections
7. {
8.     using Unity.Collections;
9.     using Unity.Collections.LowLevel.Unsafe;
10.  
11.     /// <summary>
12.     /// An iterator for both <see cref="NativeHashMap{TKey,TValue}"/> and <see cref="NativeMultiHashMap{TKey, TValue}"/>.
13.     /// Used like this
14.     /// while (iterator.MoveNext())
15.     /// {
16.     ///     var key = iterator.Key;
17.     ///     var val = iterator.Value;
18.     /// }
19.     /// </summary>
20.     /// <typeparam name="TKey">The type of the hash map key.</typeparam>
21.     /// <typeparam name="TValue">The type of the hash map value.</typeparam>
22.     public unsafe struct NativeHashMapIterator<TKey, TValue>
23.         where TKey : struct
24.         where TValue : struct
25.     {
26.         private readonly NativeHashMapDataImposter* data;
27.         private readonly int* bucketArray;
28.         private readonly int* bucketNext;
29.  
30.         private int i;
31.         private int b;
32.  
33.         /// <summary>
34.         /// Initializes a new instance of the <see cref="NativeHashMapIterator{TKey, TValue}"/> struct.
35.         /// </summary>
36.         /// <param name="data">The HashMap data.</param>
37.         internal NativeHashMapIterator(NativeHashMapDataImposter* data)
38.         {
39.             this.data = data;
40.  
41.             this.bucketArray = (int*)data->Buckets;
42.             this.bucketNext = (int*)data->Next;
43.  
44.             this.i = 0;
45.             this.b = -1;
46.         }
47.  
48.         /// <summary>
49.         /// Gets the key at the current position. Make sure MoveNext returned true before calling this.
50.         /// </summary>
51.         public TKey Key => UnsafeUtility.ReadArrayElement<TKey>(this.data->Keys, this.b);
52.  
53.         /// <summary>
54.         /// Gets the value at the current position. Make sure MoveNext returned true before calling this.
55.         /// </summary>
56.         public TValue Value => UnsafeUtility.ReadArrayElement<TValue>(this.data->Values, this.b);
57.  
58.         /// <summary>
59.         /// Moves to the next element.
60.         /// </summary>
61.         /// <returns>Returns true if element exists, otherwise false.</returns>
62.         public bool MoveNext()
63.         {
64.             // This is a bit ugly to say the least.
65.             if (this.b == -1)
66.             {
67.                 ++this.i;
68.  
69.                 if (this.i >= this.data->BucketCapacityMask)
70.                 {
71.                     return false;
72.                 }
73.  
74.                 this.b = this.bucketArray[this.i];
75.                 return this.b != -1 || this.MoveNext();
76.             }
77.  
78.             this.b = this.bucketNext[this.b];
79.             return this.b != -1 || this.MoveNext();
80.         }
81.  
82.         /// <summary>
83.         /// Resets the iterator to start again.
84.         /// </summary>
85.         public void Reset()
86.         {
87.             this.i = 0;
88.             this.b = -1;
89.         }
90.     }
91. }

Extension methods

Code (CSharp):

1.         public static unsafe NativeHashMapIterator<TKey, TValue> GetIterator<TKey, TValue>(this NativeMultiHashMap<TKey, TValue> hashMap)
2.             where TKey : struct, IEquatable<TKey>
3.             where TValue : struct
4.         {
5.             var imposter = (NativeMultiHashMapImposter<TKey, TValue>)hashMap;
6.  
7.             NativeHashMapDataImposter* data = imposter.Buffer;
8.  
9.             return new NativeHashMapIterator<TKey, TValue>(data);
10.         }
11.  
12.         public static unsafe NativeHashMapIterator<TKey, TValue> GetIterator<TKey, TValue>(this NativeHashMap<TKey, TValue> hashMap)
13.             where TKey : struct, IEquatable<TKey>
14.             where TValue : struct
15.         {
16.             var imposter = (NativeHashMapImposter<TKey, TValue>)hashMap;
17.  
18.             NativeHashMapDataImposter* data = imposter.Buffer;
19.  
20.             return new NativeHashMapIterator<TKey, TValue>(data);
21.         }

My imposters

Code (CSharp):

1.     [StructLayout(LayoutKind.Sequential)]
2.     internal unsafe struct NativeHashMapImposter<TKey, TValue>
3.         where TKey : struct, IEquatable<TKey>
4.         where TValue : struct
5.     {
6.         [NativeDisableUnsafePtrRestriction]
7.         public NativeHashMapDataImposter* Buffer;
8.  
9. #if ENABLE_UNITY_COLLECTIONS_CHECKS
10.         public AtomicSafetyHandle Safety;
11.  
12.         [NativeSetClassTypeToNullOnSchedule]
13.         public DisposeSentinel DisposeSentinel;
14. #endif
15.  
16.         public Allocator AllocatorLabel;
17.  
18.         public static implicit operator NativeHashMapImposter<TKey, TValue>(NativeHashMap<TKey, TValue> hashMap)
19.         {
20.             var ptr = UnsafeUtility.AddressOf(ref hashMap);
21.             UnsafeUtility.CopyPtrToStructure(ptr, out NativeHashMapImposter<TKey, TValue> imposter);
22.             return imposter;
23.         }
24.     }
25.  
26.     [StructLayout(LayoutKind.Sequential)]
27.     internal unsafe struct NativeMultiHashMapImposter<TKey, TValue>
28.         where TKey : struct, IEquatable<TKey>
29.         where TValue : struct
30.     {
31.         [NativeDisableUnsafePtrRestriction]
32.         internal NativeHashMapDataImposter* Buffer;
33.  
34. #if ENABLE_UNITY_COLLECTIONS_CHECKS
35.         private AtomicSafetyHandle Safety;
36.  
37.         [NativeSetClassTypeToNullOnSchedule]
38.         private DisposeSentinel DisposeSentinel;
39. #endif
40.  
41.         private Allocator AllocatorLabel;
42.  
43.         public static implicit operator NativeMultiHashMapImposter<TKey, TValue>(NativeMultiHashMap<TKey, TValue> hashMap)
44.         {
45.             var ptr = UnsafeUtility.AddressOf(ref hashMap);
46.             UnsafeUtility.CopyPtrToStructure(ptr, out NativeMultiHashMapImposter<TKey, TValue> imposter);
47.             return imposter;
48.         }
49.     }
50.  
51.    
52. [StructLayout(LayoutKind.Explicit)]
53. internal unsafe struct NativeHashMapDataImposter
54. {
55.     [FieldOffset(0)]
56.     public byte* Values;c
57.  
58.     [FieldOffset(8)]
59.     public byte* Keys;
60.  
61.     [FieldOffset(16)]
62.     public byte* Next;
63.  
64.     [FieldOffset(24)]
65.     public byte* Buckets;
66.  
67.     [FieldOffset(32)]
68.     public int Capacity;
69.  
70.     [FieldOffset(36)]
71.     public int BucketCapacityMask; // = bucket capacity - 1
72.  
73.     [FieldOffset(40)]
74.     public int AllocatedIndexLength;
75.  
76.     [FieldOffset(JobsUtility.CacheLineSize < 64 ? 64 : JobsUtility.CacheLineSize)]
77.     public fixed int firstFreeTLS[JobsUtility.MaxJobThreadCount * IntsPerCacheLine];
78.  
79.     // 64 is the cache line size on x86, arm usually has 32 - so it is possible to save some memory there
80.     public const int IntsPerCacheLine = JobsUtility.CacheLineSize / sizeof(int);
81. }
82.