Search Unity

  1. Unity 2018.3 is now released.
    Dismiss Notice
  2. The Unity Pro & Visual Studio Professional Bundle gives you the tools you need to develop faster & collaborate more efficiently. Learn more.
    Dismiss Notice
  3. We've updated our Terms of Service. Please read our blog post from Unity CTO and Co-Founder Joachim Ante here
    Dismiss Notice
  4. Want to provide direct feedback to the Unity team? Join the Unity Advisory Panel.
    Dismiss Notice
  5. Improve your Unity skills with a certified instructor in a private, interactive classroom. Watch the overview now.
    Dismiss Notice

Iterating NativeMultiHashMap

Discussion in 'Entity Component System and C# Job system' started by tertle, Jan 11, 2019.

  1. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    910
    -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!
     
    Last edited: Jan 13, 2019
  2. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    910
    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.
     
    Last edited: Jan 12, 2019
    Abbrew likes this.
  3. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    655
    @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?
     
  4. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    910
    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.
     
    Abbrew likes this.
  5. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    655
    @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?
     
  6. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    910
    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.
     
    Mr-Mechanical and sngdan like this.
  7. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    655
    @tertle if you ever get to it, the same extension for NativeHashMap would be great as well...
     
  8. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    910
    Yeah I intend to I'm just in the process of moving for the next week.
     
    sngdan likes this.
  9. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    910
  10. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    910
    Guess this is a bit dated now