Iterating NativeMultiHashMap

-edit-
I've renamed the title to better reflect the different things in this thread now.

IJobProcessNativeMultiHashMap<TKey, TValue> is available here: https://forum.unity.com/threads/nativemultihashmap-iteration-and-job.611293/#post-4093213

NativeMultiHashMap.GetEnumerator() is available here: https://forum.unity.com/threads/nativemultihashmap-iteration-and-job.611293/#post-4096609

-original-

It's been an often requested feature, and I've come into the need on occasion to be able to iterate a NativeMutliHashMap in a job. At the moment, all we have is IJobNativeMultiHashMapMergedSharedKeyIndices which only works on NativeMutliHashMap<int, int> and does not pass key value.

I could not be bothered waiting any longer so I decided to write a new job to do this myself. The interface looks like so,

Code (CSharp):

1.     /// <summary>
2.     /// Iterates a NativeMultiHashMap.
3.     /// </summary>
4.     /// <typeparam name="TKey">The key.</typeparam>
5.     /// <typeparam name="TValue">The value.</typeparam>
6.     public interface IJobProcessNativeMultiHashMap<in TKey, in TValue>
7.         where TKey : struct, IEquatable<TKey>
8.         where TValue : struct
9.     {
10.         /// <summary>
11.         /// Called for every key, value pair of the <see cref="NativeMultiHashMap{TKey,TValue}"/>
12.         /// </summary>
13.         /// <param name="key">The value of the key.</param>
14.         /// <param name="value">The value of the pair.</param>
15.         void Execute(TKey key, TValue value);
16.     }

The schedule looks like so,

Code (CSharp):

1. public static unsafe JobHandle Schedule<TJob, TKey, TValue>(this TJob jobData, NativeMultiHashMap<TKey, TValue> hashMap, int minIndicesPerJobCount, JobHandle dependsOn = default)
2.     where TJob : struct, IJobProcessNativeMultiHashMap<TKey, TValue>
3.     where TKey : struct, IEquatable<TKey>
4.     where TValue : struct

Pretty much the same as IJobNativeMultiHashMapMergedSharedKeyIndices except takes any NativeMultiHashMap.

Here is a quickly thrown together unit test so you can see how you'd implement / use it.

Code (CSharp):

1. [Test]
2. public void JobProcessNativeMultiHashMap()
3. {
4.     const int keyCount = 10;
5.     const int valueCount = 10;
6.  
7.     var values = new NativeMultiHashMap<double, double>(keyCount * valueCount, Allocator.TempJob);
8.  
9.     var random = new Random(1234);
10.  
11.     for (var i = 0; i < keyCount; i++)
12.     {
13.         var key = random.NextDouble();
14.  
15.         for (var j = 0; j < valueCount; j++)
16.         {
17.             var value = random.NextDouble();
18.  
19.             values.Add(key, value);
20.         }
21.     }
22.  
23.     var results = new NativeMultiHashMap<double, double>(keyCount * valueCount, Allocator.TempJob);
24.  
25.     var job = new JobTest
26.     {
27.         Results = results.ToConcurrent(),
28.     };
29.  
30.     var handle = job.Schedule(values, 1);
31.  
32.     handle.Complete();
33.  
34.     Assert.AreEqual(values.Length, results.Length);
35.  
36.     values.Clear();
37.     results.Clear();
38. }
39.  
40. [BurstCompile]
41. private struct JobTest : IJobProcessNativeMultiHashMap<double, double>
42. {
43.     public NativeMultiHashMap<double, double>.Concurrent Results;
44.  
45.     /// <inheritdoc />
46.     public void Execute(double key, double value)
47.     {
48.         this.Results.Add(key, value);
49.     }
50. }

At this stage I'm not 100% sure how the threading on this works as I'm still not certain of the workings of NativeMultiHashMap and I can't tell if each key will operate on it's own thread (what i'm hoping for) or they will mix across threads. I need to do more testing and reading the source.

Now I'm not releasing it right this second, maybe later today/tomorrow if I can figure out how the work is split but I also wanted feedback on the interface. If you were to use this, is void Execute(TKey key, TValue value) what you'd want or is there an alternative? I can't really think of one with how the NativeMultiHashMap is setup.

-side note-

The biggest challenge of getting this to work was the fact that everything is internal for the NativeMutliHashMap. My solution if anyone was interested was taking advantage of the sequential memory layout so I wrote a couple of imposters

Code (CSharp):

1.         [StructLayout(LayoutKind.Sequential)]
2.         public unsafe struct NativeMultiHashMapImposter<TKey, TValue>
3.             where TKey : struct, IEquatable<TKey>
4.             where TValue : struct
5.         {
6.             [NativeDisableUnsafePtrRestriction] internal NativeHashMapDataImposter* m_Buffer;
7.  
8. #if ENABLE_UNITY_COLLECTIONS_CHECKS
9.             AtomicSafetyHandle m_Safety;
10.             [NativeSetClassTypeToNullOnSchedule] DisposeSentinel m_DisposeSentinel;
11. #endif
12.  
13.             Allocator m_AllocatorLabel;
14.         }
15.  
16.         [StructLayout(LayoutKind.Sequential)]
17.         public unsafe struct NativeHashMapDataImposter
18.         {
19.             public byte* values;
20.             public byte* keys;
21.             public byte* next;
22.             public byte* buckets;
23.             public int capacity;
24.  
25.             public int bucketCapacityMask; // = bucket capacity - 1
26.  
27.             // Add padding between fields to ensure they are on separate cache-lines
28.             private fixed byte padding1[60];
29.  
30.             public fixed int firstFreeTLS[JobsUtility.MaxJobThreadCount * IntsPerCacheLine];
31.             public int allocatedIndexLength;
32.  
33.             // 64 is the cache line size on x86, arm usually has 32 - so it is possible to save some memory there
34.             public const int IntsPerCacheLine = JobsUtility.CacheLineSize / sizeof(int);
35.         }

and remapped the hash map to them

Code (CSharp):

1.             public static implicit operator NativeMultiHashMapImposter<TKey, TValue>(NativeMultiHashMap<TKey, TValue> hashMap)
2.             {
3.                 var ptr = UnsafeUtility.AddressOf(ref hashMap);
4.                 UnsafeUtility.CopyPtrToStructure(ptr, out NativeMultiHashMapImposter<TKey, TValue> imposter);
5.                 return imposter;
6.             }

It seems to work fantastic, but if anyone can tell me why this is a very bad idea it would be great to know now!

 

Available here: https://github.com/tertle/com.bovin.../Runtime/Jobs/JobProcessNativeMultiHashMap.cs

From my testing I believe each Key should only exist on one thread (though that thread may have multiple keys) which is extremely useful.

Therefore if your key is an Entity, you should be able to safely manipulate it using ComponentDataFromEntity and BufferFromEntity

I might write something up tomorrow on the very convenient use case I want it for.

 

@tertle

Can we map the NativeMultiHashMap to native arrays / queues in memory?

I would like to process the results stored in the NativeMultiHashMap a native array per key. How would we get the length of each?

 

I'll have a think about how you could do it.

I have a much better understand how NativeMultiHashMap works now and there are a bunch of extensions I could potentially add to add more support for it.

 

@tertle

Thank you - that would be useful. I am using NativeHashMap and NativeMultiHashMap for the first time. Similar to my question above, is there a way to iterate through all Values of a NativeHashMap without a key?

 

You are not the only one who has asked this!
https://forum.unity.com/threads/iteration-over-values-in-nativehashmap-or-nativemultihashmap.582310/
https://forum.unity.com/threads/nativehashmap.529803/
etc etc

Well now you can!

Code (CSharp):

1. var map = new NativeMultiHashMap<int, int>(128, Allocator.TempJob);
2.  
3. using (var enumerator = map.GetEnumerator())
4. {
5.     while (enumerator.MoveNext())
6.     {
7.         KeyValuePair<int, int> kvp = enumerator.Current;
8.     }
9. }
10.  
11. map.Dispose();

Source code here: https://github.com/tertle/com.bovin...me/Extensions/NativeMultiHashMapExtensions.cs

I think this should work fine, but it's late at night and I only wrote a single quick unit test to confirm.
Currently only built it for NativeMultiHashMap, I'll create a similar versions for NativeHashMap at some point.

 

@tertle if you ever get to it, the same extension for NativeHashMap would be great as well...

 

Yeah I intend to I'm just in the process of moving for the next week.

 

Managed to find some time to throw together a GetEnumerator method for NativeHashMap

https://github.com/tertle/com.bovin...Runtime/Extensions/NativeHashMapExtensions.cs

Passes my simple unit test but not well tested yet.

 

Guess this is a bit dated now

 

https://forum.unity.com/threads/nativehashmap-concurrent-replace.532420/
is answer

 

I noticed NativeMultiHashMapExtensions.cs was removed from GitHub. Has unity provided a better/standard way of iterating over the NativeMultiHashMap?