Search Unity

What's the best way to get the NativeMultiHashMap's unique key array for jobs?

Discussion in 'Data Oriented Technology Stack' started by TMPxyz, Jul 16, 2019.

  1. TMPxyz

    TMPxyz

    Joined:
    Jul 20, 2012
    Posts:
    765
    Hi, is there some simple method to access the NativeMultiHashMap(NMHM)'s unique key array for job code?

    I'm working on a graph algorithm, the job will process the edges and generate a lot of <node, node_modification> pairs, the node key could appear multiple times as a node could be pointed to by multiple incoming edges.

    Now a part of the algorithm needs to loop on the nodes in the hashmap for once each.

    I've tried several methods to approach that:

    * I used a NativeHashMap in the same job of generating the NMHM, to get a unique node set. But there's not a job type to loop on NativeHashMap;
    * I tried with an IJob running on NMHM and get the key-array, sort it, and acquire an unique array. It works, but it cannot use burst-compile or parallel, and the performance is extremely terrible.

    Is there some simple way to make that? It would be great to have a job type can run on NativeHashMap or NativeQueue.
     
  2. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,366
    GetUniqueKeyArray(). It's an extension method.
     
  3. TMPxyz

    TMPxyz

    Joined:
    Jul 20, 2012
    Posts:
    765
    Well, that's basically what I did in the second solution with IJob.
    I copied the code out of GetUniqueKeyArray() and made a little change to make it work on Entity keys.

    The only drawback is that It cannot parallel or burst, and takes a huge amount time.
     
  4. TMPxyz

    TMPxyz

    Joined:
    Jul 20, 2012
    Posts:
    765
    Okay,

    I've figured out a method that can do it with parallel job + burst.

    It's kinda dumb and takes 3x memory, but it does work.

    The point is to add two more containers:
    * NativeHashMap<K, bool>: it works as a Set, and use TryAdd() to test if a K has already appeared before;
    * NativeMultiHashMap<K, bool>: this works as the container of unique keys, and will be passed down to next job, and only insert when the NativeHashMap.TryAdd() test passes;
     
  5. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,663
    What was stopping you bursting it? (parallel is bit more of an issue)
     
  6. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,366
    GetKeyArray working in burst is I think fairly new, I actually hit where it didn't work for me just a couple of weeks back, on burst 1.0.4 and 2019.1. Although I can't remember if it was NativeHashMap or NativeMultiHashMap. It complained about the allocator if I remember correctly.
     
  7. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,663
    Not sure, but it definitely should work fine now if you use Temp Allocator
     
  8. TMPxyz

    TMPxyz

    Joined:
    Jul 20, 2012
    Posts:
    765
    To clarify, I didn't use NMHM's GetUniqueKeyArray() directly, as it asks for the key to be IComparable but I'm using Entity as key,

    Here's the code I used. The burst compiler complains there's a allocation ( GetKeyArray )

    Code (CSharp):
    1. //[BurstCompile]
    2.     public struct GetUniqueHashMapKeyArrayJob<TKey, TValue, U> : IJob
    3.         where TKey : struct, IEquatable<TKey>
    4.         where TValue : struct
    5.         where U : struct, IComparer<TKey>
    6.     {
    7.         [ReadOnly] public NativeMultiHashMap<TKey, TValue> mmap;
    8.         [WriteOnly] public NativeList<TKey> keyList;
    9.         [ReadOnly] public U cmp;
    10.  
    11.         public void Execute()
    12.         {
    13.             var arr_key = mmap.GetKeyArray(Allocator.Temp);
    14.  
    15.             arr_key.Sort( cmp );
    16.             TKey prev = default(TKey);
    17.             for(int i=0; i<arr_key.Length; ++i)
    18.             {
    19.                 var elem = arr_key[i];
    20.                 if (!elem.Equals(prev))
    21.                 {
    22.                     keyList.Add(elem);
    23.                     prev = elem;
    24.                 }
    25.             }
    26.  
    27.             arr_key.Dispose();
    28.         }
    29.     }
     
  9. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,663
    GetKeyArray works fine for me in a job, literally just wrote a system 2 hours ago using it. what version of unity / burst are you using?

    Code (CSharp):
    1. arr_key.Dispose();
    you don't need to (and shouldn't) dispose Allocator.Temp in jobs, it's handled automatically
     
  10. TMPxyz

    TMPxyz

    Joined:
    Jul 20, 2012
    Posts:
    765
    Unity 2019.1.7f1 + Burst 1.0.4

    Isn't that allocating native containers in job bad for performance?