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

Unity Engine
,
1

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

GetUniqueKeyArray(). It’s an extension method.

3

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

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

What was stopping you bursting it? (parallel is bit more of an issue)

6

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

Not sure, but it definitely should work fine now if you use Temp Allocator

8

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 )

//[BurstCompile]
    public struct GetUniqueHashMapKeyArrayJob<TKey, TValue, U> : IJob
        where TKey : struct, IEquatable<TKey>
        where TValue : struct
        where U : struct, IComparer<TKey>
    {
        [ReadOnly] public NativeMultiHashMap<TKey, TValue> mmap;
        [WriteOnly] public NativeList<TKey> keyList;
        [ReadOnly] public U cmp;

        public void Execute()
        {
            var arr_key = mmap.GetKeyArray(Allocator.Temp);

            arr_key.Sort( cmp );
            TKey prev = default(TKey);
            for(int i=0; i<arr_key.Length; ++i)
            {
                var elem = arr_key[i];
                if (!elem.Equals(prev))
                {
                    keyList.Add(elem);
                    prev = elem;
                }
            }

            arr_key.Dispose();
        }
    }
9

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?

arr_key.Dispose();

you don’t need to (and shouldn’t) dispose Allocator.Temp in jobs, it’s handled automatically

10

Unity 2019.1.7f1 + Burst 1.0.4

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