Is there no NativeHashSet or am I blind?

While there is NativeHashmap there does not seem to be a NativeHashSet? Is there going to be one eventually or would I need to implement it myself (or am I missing some aspect why it is not needed?)

 

I was wondering the same thing yesterday.

 

You could use a NativeHashMap as a NativeHashSet. Have <T,byte> or <T,bool> as your type arguments. When adding an element T t do either hash.TryAdd(t,0) or hash.TryAdd(t,true). The second type argument should be something small to minimize wasted space.

 

I made a NativeHashSet a while ago with some improvements with clearing compared to NativeHashMap, I'm not sure if it still works without errors as it was made months ago and haven't retested it with the latest APIs. This was the lastest git node I had with it:

NativeHashSet.cs

Code (CSharp):

1. using System;
2. using System.Runtime.InteropServices;
3. using Unity.Collections;
4. using Unity.Collections.LowLevel.Unsafe;
5.  
6. namespace NativeContainers {
7.     [StructLayout(LayoutKind.Sequential)]
8.     [NativeContainer]
9.     public unsafe struct NativeHashSet<T> : IDisposable where T : struct, IEquatable<T> {
10.         [NativeDisableUnsafePtrRestriction] NativeHashSetData* buffer;
11.         Allocator allocator;
12. #if ENABLE_UNITY_COLLECTIONS_CHECKS
13.         AtomicSafetyHandle m_Safety;
14.         [NativeSetClassTypeToNullOnSchedule] DisposeSentinel m_DisposeSentinel;
15. #endif
16.  
17.         public NativeHashSet(int capacity, Allocator allocator) {
18.             NativeHashSetData.AllocateHashSet<T>(capacity, allocator, out buffer);
19.             this.allocator = allocator;
20. #if ENABLE_UNITY_COLLECTIONS_CHECKS
21.             DisposeSentinel.Create(
22.                 out m_Safety, out m_DisposeSentinel, callSiteStackDepth:8, allocator:allocator);
23. #endif
24.             Clear();
25.         }
26.  
27.         [NativeContainer]
28.         [NativeContainerIsAtomicWriteOnly]
29.         public struct Concurrent {
30.             [NativeDisableUnsafePtrRestriction] public NativeHashSetData* buffer;
31.             [NativeSetThreadIndex] public int threadIndex;
32. #if ENABLE_UNITY_COLLECTIONS_CHECKS
33.             public AtomicSafetyHandle m_Safety;
34. #endif
35.  
36.             public int Capacity {
37.                 get {
38. #if ENABLE_UNITY_COLLECTIONS_CHECKS
39.                     AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
40. #endif
41.                     return buffer->Capacity;
42.                 }
43.             }
44.  
45.             public bool TryAdd(T value) {
46. #if ENABLE_UNITY_COLLECTIONS_CHECKS
47.                 AtomicSafetyHandle.CheckWriteAndThrow(m_Safety);
48. #endif
49.                 return buffer->TryAddThreaded(ref value, threadIndex);
50.             }
51.         }
52.  
53.         public int Capacity {
54.             get {
55. #if ENABLE_UNITY_COLLECTIONS_CHECKS
56.                 AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
57. #endif
58.                 return buffer->Capacity;
59.             }
60.         }
61.  
62.         public int Length {
63.             get {
64. #if ENABLE_UNITY_COLLECTIONS_CHECKS
65.                 AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
66. #endif
67.                 return buffer->Length;
68.             }
69.         }
70.  
71.         public bool IsCreated => buffer != null;
72.  
73.         public void Dispose() {
74. #if ENABLE_UNITY_COLLECTIONS_CHECKS
75.             AtomicSafetyHandle.CheckDeallocateAndThrow(m_Safety);
76.             DisposeSentinel.Dispose(ref m_Safety, ref m_DisposeSentinel);
77. #endif
78.             NativeHashSetData.DeallocateHashSet(buffer, allocator);
79.             buffer = null;
80.         }
81.  
82.         public void Clear() {
83. #if ENABLE_UNITY_COLLECTIONS_CHECKS
84.             AtomicSafetyHandle.CheckWriteAndThrow(m_Safety);
85. #endif
86.             buffer->Clear<T>();
87.         }
88.  
89.         public Concurrent ToConcurrent() {
90.             Concurrent concurrent;
91.             concurrent.threadIndex = 0;
92.             concurrent.buffer = buffer;
93. #if ENABLE_UNITY_COLLECTIONS_CHECKS
94.             concurrent.m_Safety = m_Safety;
95. #endif
96.             return concurrent;
97.         }
98.  
99.         public bool TryAdd(T value) {
100. #if ENABLE_UNITY_COLLECTIONS_CHECKS
101.             AtomicSafetyHandle.CheckWriteAndThrow(m_Safety);
102. #endif
103.             return buffer->TryAdd(ref value, allocator);
104.         }
105.  
106.         public bool TryRemove(T value) {
107. #if ENABLE_UNITY_COLLECTIONS_CHECKS
108.             AtomicSafetyHandle.CheckWriteAndThrow(m_Safety);
109. #endif
110.             return buffer->TryRemove(value);
111.         }
112.  
113.         public bool Contains(T value) {
114. #if ENABLE_UNITY_COLLECTIONS_CHECKS
115.             AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
116. #endif
117.             return buffer->Contains(ref value);
118.         }
119.  
120.         public NativeArray<T> GetValueArray(Allocator allocator) {
121. #if ENABLE_UNITY_COLLECTIONS_CHECKS
122.             AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
123. #endif
124.             var result = new NativeArray<T>(Length, allocator, NativeArrayOptions.UninitializedMemory);
125.             buffer->GetValueArray(result);
126.             return result;
127.         }
128.     }
129. }
130.  

NativeHashSetData.cs:

Code (CSharp):

1.  
2. using System;
3. using System.Runtime.InteropServices;
4. using System.Threading;
5. using Unity.Collections;
6. using Unity.Collections.LowLevel.Unsafe;
7. using Unity.Jobs.LowLevel.Unsafe;
8. using Unity.Mathematics;
9. using UnityEngine.Assertions;
10.  
11. namespace NativeContainers {
12.    [StructLayout(LayoutKind.Sequential)]
13.    public unsafe struct NativeHashSetData {
14.        byte* values;
15.        byte* next;
16.        byte* buckets;
17.        int valueCapacity;
18.        int bucketCapacityMask;
19.  
20.        // Adding padding to ensure remaining fields are on separate cache-lines
21.        fixed byte padding[60];
22.        fixed int firstFreeTLS[JobsUtility.MaxJobThreadCount * IntsPerCacheLine];
23.        int allocatedIndexLength;
24.        const int IntsPerCacheLine = JobsUtility.CacheLineSize / sizeof(int);
25.  
26.        public int Capacity => valueCapacity;
27.  
28.        public int Length {
29.            get {
30.                int* nextPtrs = (int*)next;
31.                int freeListSize = 0;
32.                for(int tls = 0; tls < JobsUtility.MaxJobThreadCount; ++tls) {
33.                    int freeIdx = firstFreeTLS[tls * IntsPerCacheLine] - 1;
34.                    for(; freeIdx >= 0; freeListSize++, freeIdx = nextPtrs[freeIdx] - 1) {}
35.                }
36.                return math.min(valueCapacity, allocatedIndexLength) - freeListSize;
37.            }
38.        }
39.  
40.        static int DoubleCapacity(int capacity) => capacity == 0 ? 1 : capacity * 2;
41.  
42.        public static void AllocateHashSet<T>(
43.        int capacity, Allocator label, out NativeHashSetData* buffer) where T : struct {
44. #if ENABLE_UNITY_COLLECTIONS_CHECKS
45.            if(!UnsafeUtility.IsBlittable<T>())
46.                throw new ArgumentException($"{typeof(T)} used in NativeHashSet<{typeof(T)}> must be blittable");
47. #endif
48.            var data = (NativeHashSetData*)UnsafeUtility.Malloc(
49.                sizeof(NativeHashSetData), UnsafeUtility.AlignOf<NativeHashSetData>(), label);
50.  
51.            int bucketCapacity = math.ceilpow2(capacity * 2);
52.            data->valueCapacity = capacity;
53.            data->bucketCapacityMask = bucketCapacity - 1;
54.    
55.            int nextOffset, bucketOffset;
56.            int totalSize = CalculateDataSize<T>(capacity, bucketCapacity, out nextOffset, out bucketOffset);
57.    
58.            data->values = (byte*)UnsafeUtility.Malloc(totalSize, JobsUtility.CacheLineSize, label);
59.            data->next = data->values + nextOffset;
60.            data->buckets = data->values + bucketOffset;
61.            buffer = data;
62.        }
63.  
64.        public static void DeallocateHashSet(NativeHashSetData* data, Allocator allocator) {
65.            UnsafeUtility.Free(data->values, allocator);
66.            data->values = null;
67.            data->buckets = null;
68.            data->next = null;
69.            UnsafeUtility.Free(data, allocator);
70.        }
71.  
72.        public void Clear() {
73.            UnsafeUtility.MemClear((int*)buckets, sizeof(int) * (bucketCapacityMask + 1));
74.            UnsafeUtility.MemClear((int*)next, sizeof(int) * valueCapacity);
75.            fixed(int* firstFreeTLS = this.firstFreeTLS) {
76.                UnsafeUtility.MemClear(
77.                    firstFreeTLS, sizeof(int) * (JobsUtility.MaxJobThreadCount * IntsPerCacheLine));
78.            }
79.            allocatedIndexLength = 0;
80.        }
81.  
82.        public void GetValueArray<T>(NativeArray<T> result) where T : struct {
83.            var buckets = (int*)this.buckets;
84.            var nextPtrs = (int*)next;
85.            int outputIndex = 0;
86.            for(int bucketIndex = 0; bucketIndex <= bucketCapacityMask; ++bucketIndex) {
87.                int valuesIndex = buckets[bucketIndex];
88.                while(valuesIndex > 0) {
89.                    result[outputIndex] = UnsafeUtility.ReadArrayElement<T>(values, valuesIndex - 1);
90.                    outputIndex++;
91.                    valuesIndex = nextPtrs[valuesIndex - 1];
92.                }
93.            }
94.            Assert.AreEqual(result.Length, outputIndex);
95.        }
96.  
97.        public bool TryAdd<T>(ref T value, Allocator allocator) where T : struct, IEquatable<T> {
98.            if(Contains(ref value)) {
99.                return false;
100.            }
101.  
102.            int valuesIdx = FindFirstFreeIndex<T>(allocator);
103.            UnsafeUtility.WriteArrayElement(values, valuesIdx, value);
104.            // Add the index to the hashset
105.            int* buckets = (int*)this.buckets;
106.            int* nextPtrs = (int*)next;
107.            int bucketIndex = value.GetHashCode() & bucketCapacityMask;
108.            nextPtrs[valuesIdx] = buckets[bucketIndex];
109.            buckets[bucketIndex] = valuesIdx + 1;
110.            return true;
111.        }
112.  
113.        public bool TryAddThreaded<T>(ref T value, int threadIndex) where T : IEquatable<T> {
114.            if(Contains(ref value)) {
115.                return false;
116.            }
117.            // Allocate an entry from the free list
118.            int idx = FindFreeIndexFromTLS(threadIndex);
119.            UnsafeUtility.WriteArrayElement(values, idx, value);
120.  
121.            // Add the index to the hashset
122.            int* buckets = (int*)this.buckets;
123.            int bucket = value.GetHashCode() & bucketCapacityMask;
124.            int* nextPtrs = (int*)next;
125.            if(Interlocked.CompareExchange(ref buckets[bucket], idx + 1, 0) != 0) {
126.                do {
127.                    nextPtrs[idx] = buckets[bucket];
128.                    if(Contains(ref value)) {
129.                        // Put back the entry in the free list if someone else added it while trying to add
130.                        do {
131.                            nextPtrs[idx] = firstFreeTLS[threadIndex * IntsPerCacheLine];
132.                        } while(Interlocked.CompareExchange(
133.                                    ref firstFreeTLS[threadIndex * IntsPerCacheLine], idx + 1,
134.                                    nextPtrs[idx]) != nextPtrs[idx]);
135.                        return false;
136.                    }
137.                } while(Interlocked.CompareExchange(ref buckets[bucket], idx + 1, nextPtrs[idx]) != nextPtrs[idx]);
138.            }
139.            return true;
140.        }
141.  
142.        public bool Contains<T>(ref T value) where T : IEquatable<T> {
143.            if(allocatedIndexLength <= 0) {
144.                return false;
145.            }
146.            int* buckets = (int*)this.buckets;
147.            int* nextPtrs = (int*)next;
148.            int bucket = value.GetHashCode() & bucketCapacityMask;
149.            int valuesIdx = buckets[bucket] - 1;
150.            while(valuesIdx >= 0 && valuesIdx < valueCapacity) {
151.                if(UnsafeUtility.ReadArrayElement<T>(values, valuesIdx).Equals(value)) {
152.                    return true;
153.                }
154.                valuesIdx = nextPtrs[valuesIdx] - 1;
155.            }
156.            return false;
157.        }
158.  
159.        public bool TryRemove<T>(T key) where T : struct, IEquatable<T> {
160.            int* buckets = (int*)this.buckets;
161.            int* nextPtrs = (int*)next;
162.            int bucketIdx = key.GetHashCode() & bucketCapacityMask;
163.            int valuesIdx = buckets[bucketIdx] - 1;
164.            int prevValuesIdx = -1;
165.  
166.            while(valuesIdx >= 0 && valuesIdx < valueCapacity) {
167.                if(UnsafeUtility.ReadArrayElement<T>(values, valuesIdx).Equals(key)) {
168.                    if(prevValuesIdx == -1) {
169.                        // Sets head->next to head->next->next(or -1)
170.                        buckets[bucketIdx] = nextPtrs[valuesIdx];
171.                    }
172.                    else {
173.                        // Sets prev->next to prev->next(current valuesIdx)->next
174.                        nextPtrs[prevValuesIdx] = nextPtrs[valuesIdx];
175.                    }
176.                    // Mark the index as free
177.                    nextPtrs[valuesIdx] = firstFreeTLS[0];
178.                    firstFreeTLS[0] = valuesIdx + 1;
179.                    return true;
180.                }
181.                prevValuesIdx = valuesIdx;
182.                valuesIdx = nextPtrs[valuesIdx] - 1;
183.            }
184.            return false;
185.        }
186.  
187.        static int CalculateDataSize<T>(
188.        int capacity, int bucketCapacity, out int nextOffset, out int bucketOffset) where T : struct {
189.            nextOffset = (UnsafeUtility.SizeOf<T>() * capacity) + JobsUtility.CacheLineSize - 1;
190.            nextOffset -= nextOffset % JobsUtility.CacheLineSize;
191.  
192.            bucketOffset = nextOffset + (sizeof(int) * capacity) + JobsUtility.CacheLineSize - 1;
193.            bucketOffset -= bucketOffset % JobsUtility.CacheLineSize;
194.            return bucketOffset + (sizeof(int) * bucketCapacity);
195.        }
196.  
197.        int FindFirstFreeIndex<T>(Allocator allocator) where T : struct {
198.            int valuesIdx;
199.            int* nextPtrs = (int*)next;
200.  
201.            // Try to find an index in another TLS.
202.            if(allocatedIndexLength >= valueCapacity && firstFreeTLS[0] == 0) {
203.                for(int tls = 1; tls < JobsUtility.MaxJobThreadCount; ++tls) {
204.                    int tlsIndex = tls * IntsPerCacheLine;
205.                    if(firstFreeTLS[tlsIndex] > 0) {
206.                        valuesIdx = firstFreeTLS[tlsIndex] - 1;
207.                        firstFreeTLS[tlsIndex] = nextPtrs[valuesIdx];
208.                        nextPtrs[valuesIdx] = 0;
209.                        firstFreeTLS[0] = valuesIdx + 1;
210.                        break;
211.                    }
212.                }
213.                // No indexes found.
214.                if(firstFreeTLS[0] == 0) {
215.                    GrowHashSet<T>(DoubleCapacity(valueCapacity), allocator);
216.                }
217.            }
218.            if(firstFreeTLS[0] == 0) {
219.                valuesIdx = allocatedIndexLength;
220.                allocatedIndexLength++;
221.            }
222.            else {
223.                valuesIdx = firstFreeTLS[0] - 1;
224.                firstFreeTLS[0] = nextPtrs[valuesIdx];
225.            }
226.            if(!(valuesIdx >= 0 && valuesIdx < valueCapacity)) {
227.                throw new InvalidOperationException(
228.                    $"Internal HashSet error, values index: {valuesIdx} not in range of 0 and {valueCapacity}");
229.            }
230.            return valuesIdx;
231.        }
232.  
233.        int FindFreeIndexFromTLS(int threadIndex) {
234.            int idx;
235.            int* nextPtrs = (int*)next;
236.            int thisTLSIndex = threadIndex * IntsPerCacheLine;
237.            do {
238.                idx = firstFreeTLS[thisTLSIndex] - 1;
239.                if(idx < 0) {
240.                    // Mark this TLS index as locked
241.                    Interlocked.Exchange(ref firstFreeTLS[thisTLSIndex], -1);
242.                    // Try to allocate more indexes with this TLS
243.                    if(allocatedIndexLength < valueCapacity) {
244.                        idx = Interlocked.Add(ref allocatedIndexLength, 16) - 16;
245.                        if(idx < valueCapacity - 1) {
246.                            int count = math.min(16, valueCapacity - idx) - 1;
247.                            for(int i = 1; i < count; ++i) {
248.                                nextPtrs[idx + i] = (idx + 1) + i + 1;
249.                            }
250.                            nextPtrs[idx + count] = 0;
251.                            nextPtrs[idx] = 0;
252.                            Interlocked.Exchange(ref firstFreeTLS[thisTLSIndex], (idx + 1) + 1);
253.                            return idx;
254.                        }
255.  
256.                        if(idx == valueCapacity - 1) {
257.                            Interlocked.Exchange(ref firstFreeTLS[thisTLSIndex], 0);
258.                            return idx;
259.                        }
260.                    }
261.  
262.                    Interlocked.Exchange(ref firstFreeTLS[thisTLSIndex], 0);
263.                    // Could not find an index, try to steal one from another TLS
264.                    for(bool iterateAgain = true; iterateAgain;) {
265.                        iterateAgain = false;
266.                        for(int i = 1; i < JobsUtility.MaxJobThreadCount; i++) {
267.                            int nextTLSIndex = ((threadIndex + i) % JobsUtility.MaxJobThreadCount) * IntsPerCacheLine;
268.                            do {
269.                                idx = firstFreeTLS[nextTLSIndex] - 1;
270.                            } while(idx >= 0 && Interlocked.CompareExchange(
271.                                        ref firstFreeTLS[nextTLSIndex], nextPtrs[idx], idx + 1) != idx + 1);
272.                            if(idx == -1) {
273.                                iterateAgain = true;
274.                            }
275.                            else if(idx >= 0) {
276.                                nextPtrs[idx] = 0;
277.                                return idx;
278.                            }
279.                        }
280.                    }
281.                    throw new InvalidOperationException("HashSet has reached capacity, cannot add more.");
282.                }
283.                if(idx > valueCapacity) {
284.                    throw new InvalidOperationException($"nextPtr idx {idx} beyond capacity {valueCapacity}");
285.                }
286.                // Another thread is using this TLS, try again.
287.            } while(Interlocked.CompareExchange(
288.                        ref firstFreeTLS[threadIndex * IntsPerCacheLine], nextPtrs[idx], idx + 1) != idx + 1);
289.            nextPtrs[idx] = 0;
290.            return idx;
291.        }
292.  
293.        
294.        void GrowHashSet<T>(int newCapacity, Allocator allocator) where T : struct {
295.            int newBucketCapacity = math.ceilpow2(newCapacity * 2);
296.            if(newCapacity == valueCapacity && newBucketCapacity == (bucketCapacityMask + 1)) {
297.                return;
298.            }
299.            if(valueCapacity > newCapacity) {
300.                throw new ArgumentException("Shrinking a hashset is not supported");
301.            }
302.  
303.            int nextOffset, bucketOffset;
304.            int totalSize = CalculateDataSize<T>(newCapacity, newBucketCapacity, out nextOffset, out bucketOffset);
305.            byte* newValues = (byte*)UnsafeUtility.Malloc(totalSize, JobsUtility.CacheLineSize, allocator);
306.            byte* newNext = newValues + nextOffset;
307.            byte* newBuckets = newValues + bucketOffset;
308.  
309.            UnsafeUtility.MemClear(newNext, sizeof(int) * newCapacity);
310.            UnsafeUtility.MemCpy(newValues, values, UnsafeUtility.SizeOf<T>() * valueCapacity);
311.            UnsafeUtility.MemCpy(newNext, next, sizeof(int) * valueCapacity);
312.  
313.            // Re-hash the buckets, first clear the new buckets, then reinsert.
314.            UnsafeUtility.MemClear(newBuckets, sizeof(int) * newBucketCapacity);
315.            int* oldBuckets = (int*)buckets;
316.            int* newNextPtrs = (int*)newNext;
317.            for(int oldBucket = 0; oldBucket <= bucketCapacityMask; ++oldBucket) {
318.                int curValuesIdx = oldBuckets[oldBucket] - 1;
319.                while(curValuesIdx >= 0 && curValuesIdx < valueCapacity) {
320.                    var curValue = UnsafeUtility.ReadArrayElement<T>(values, curValuesIdx);
321.                    int newBucket = curValue.GetHashCode() & newBucketCapacity - 1;
322.                    oldBuckets[oldBucket] = newNextPtrs[curValuesIdx];
323.                    newNextPtrs[curValuesIdx] = ((int*)newBuckets)[newBucket];
324.                    ((int*)newBuckets)[newBucket] = curValuesIdx + 1;
325.                    curValuesIdx = oldBuckets[oldBucket] - 1;
326.                }
327.            }
328.  
329.            UnsafeUtility.Free(values, allocator);
330.            if(allocatedIndexLength > valueCapacity) {
331.                allocatedIndexLength = valueCapacity;
332.            }
333.            values = newValues;
334.            next = newNext;
335.            buckets = newBuckets;
336.            valueCapacity = newCapacity;
337.            bucketCapacityMask = newBucketCapacity - 1;
338.        }
339.    }
340. }
341.  

NativeHashSetTests.cs:

Code (CSharp):

1. using System.Collections.Generic;
2. using NativeContainers;
3. using NUnit.Framework;
4. using Unity.Collections;
5. using Unity.Jobs;
6. using UnityEngine;
7.  
8. namespace NativeContainerTests {
9.     public class NativeHashSetBasicTests {
10.         const int HashSetInitialCapacity = 4;
11.         NativeHashSet<int> testHashSet;
12.  
13.         [OneTimeSetUp]
14.         public void Setup() {
15.             testHashSet = new NativeHashSet<int>(HashSetInitialCapacity, Allocator.Persistent);
16.         }
17.  
18.         [OneTimeTearDown]
19.         public void TearDown() {
20.             testHashSet.Dispose();
21.         }
22.  
23.         [Test, Order(0)]
24.         public void Capacity_ShouldBeInitalValue() {
25.             Assert.AreEqual(HashSetInitialCapacity, testHashSet.Capacity);
26.         }
27.  
28.         [Test, Order(1)]
29.         public void Add_ShouldAdd1() {
30.             testHashSet.TryAdd(1);
31.             Assert.AreEqual(1, testHashSet.Length);
32.         }
33.  
34.         [Test, Order(2)]
35.         public void Remove_ShouldRemove1() {
36.             testHashSet.TryRemove(1);
37.             Assert.AreEqual(0, testHashSet.Length);
38.         }
39.  
40.         [Test, Order(3)]
41.         public void Add_ShouldReturnTrueOnUnique() {
42.             Assert.IsTrue(testHashSet.TryAdd(1));
43.         }
44.  
45.         [Test, Order(4)]
46.         public void Add_ShouldReturnFalseOnDuplicate() {
47.             Assert.IsFalse(testHashSet.TryAdd(1));
48.         }
49.  
50.         [Test, Order(5)]
51.         public void Remove_ShouldReturnTrueIfExists() {
52.             Assert.IsTrue(testHashSet.TryRemove(1));
53.         }
54.  
55.         [Test, Order(6)]
56.         public void Remove_ShouldReturnFalseIfNotExists() {
57.             Assert.IsFalse(testHashSet.TryRemove(99));
58.         }
59.  
60.         [Test, Order(7)]
61.         public void Clear_LengthShouldEqual0() {
62.             testHashSet.TryAdd(1);
63.             Assert.AreEqual(1, testHashSet.Length);
64.             testHashSet.Clear();
65.             Assert.AreEqual(0, testHashSet.Length);
66.         }
67.  
68.         [Test, Order(8)]
69.         public void Contains_ShouldNotContainIfNotAdded() {
70.             Assert.IsFalse(testHashSet.Contains(99));
71.         }
72.     }
73.  
74.     public class NativeHashSetExtendedRandomTests {
75.         const int RandomNumbersMinLength = 100;
76.         const int RandomNumbersMaxLength = 200;
77.         const int RandomNumberMaxValue = 1000000;
78.         NativeHashSet<int> testHashSet;
79.         NativeList<int> uniqueRandomNumbers;
80.  
81.         [OneTimeSetUp]
82.         public void Setup() {
83.             uniqueRandomNumbers = new NativeList<int>(Allocator.Persistent);
84.             var managedSet = new HashSet<int>();
85.             var randomNumbersLength = Random.Range(RandomNumbersMinLength, RandomNumbersMaxLength);
86.             for(int i = 0; i < randomNumbersLength; i++) {
87.                 managedSet.Add(Random.Range(0, RandomNumberMaxValue));
88.             }
89.             foreach(var num in managedSet) {
90.                 uniqueRandomNumbers.Add(num);
91.             }
92.         }
93.  
94.         [OneTimeTearDown]
95.         public void TearDown() {
96.             uniqueRandomNumbers.Dispose();
97.         }
98.  
99.         [SetUp]
100.         public void TestSetUp() {
101.             testHashSet = new NativeHashSet<int>(uniqueRandomNumbers.Length, Allocator.Temp);
102.         }
103.  
104.         [TearDown]
105.         public void TestTearDown() {
106.             testHashSet.Dispose();
107.         }
108.  
109.         [Test]
110.         public void Length_ShouldEqualRandomLength() {
111.             for(int i = 0; i < uniqueRandomNumbers.Length; i++) {
112.                 testHashSet.TryAdd(uniqueRandomNumbers[i]);
113.             }
114.             Assert.AreEqual(uniqueRandomNumbers.Length, testHashSet.Length);
115.         }
116.  
117.         [Test]
118.         public void Remove_ShouldRemoveRange() {
119.             for(int i = 0; i < uniqueRandomNumbers.Length; i++) {
120.                 testHashSet.TryAdd(uniqueRandomNumbers[i]);
121.                 Assert.IsTrue(testHashSet.TryRemove(uniqueRandomNumbers[i]));
122.             }
123.             Assert.AreEqual(0, testHashSet.Length);
124.         }
125.  
126.         [Test]
127.         public void Contains_ShouldContainRandomNumber() {
128.             var randomNum = uniqueRandomNumbers[Random.Range(0, uniqueRandomNumbers.Length)];
129.             testHashSet.TryAdd(randomNum);
130.             Assert.IsTrue(testHashSet.Contains(randomNum));
131.         }
132.  
133.         [Test]
134.         public void Contains_ShouldContainRandomRange() {
135.             for(int i = 0; i < uniqueRandomNumbers.Length; i++) {
136.                 testHashSet.TryAdd(uniqueRandomNumbers[i]);
137.                 Assert.IsTrue(testHashSet.Contains(uniqueRandomNumbers[i]));
138.             }
139.         }
140.  
141.         [Test]
142.         public void GetValueArray_ShouldReturnCorrectRandomLength() {
143.             for(int i = 0; i < uniqueRandomNumbers.Length; i++) {
144.                 testHashSet.TryAdd(uniqueRandomNumbers[i]);
145.             }
146.             var values = testHashSet.GetValueArray(Allocator.Temp);
147.             Assert.AreEqual(uniqueRandomNumbers.Length, values.Length);
148.         }
149.  
150.         [Test]
151.         public void GetValueArray_ShouldReturnAllValues() {
152.             var managedSet = new HashSet<int>();
153.             for(int i = 0; i < uniqueRandomNumbers.Length; i++) {
154.                 managedSet.Add(uniqueRandomNumbers[i]);
155.                 testHashSet.TryAdd(uniqueRandomNumbers[i]);
156.             }
157.             var values = testHashSet.GetValueArray(Allocator.Temp);
158.             Assert.AreEqual(managedSet.Count, values.Length);
159.             for(int i = 0; i < values.Length; i++) {
160.                 Assert.IsTrue(managedSet.Contains(values[i]));
161.             }
162.         }
163.     }
164.  
165.     public class NativeHashSetJobRandomTests {
166.         const int RandomNumbersMinLength = 500;
167.         const int RandomNumbersMaxLength = 2000;
168.         const int RandomNumberMaxValue = 1000000;
169.         NativeHashSet<int> testHashSet;
170.         NativeList<int> uniqueRandomNumbers;
171.  
172.         struct AddJob : IJobParallelFor {
173.             public NativeHashSet<int>.Concurrent HashSet;
174.             [ReadOnly] public NativeArray<int> ToAdd;
175.  
176.             public void Execute(int index) {
177.                 HashSet.TryAdd(ToAdd[index]);
178.             }
179.         }
180.  
181.         [OneTimeSetUp]
182.         public void Setup() {
183.             var randomNumbersLength = Random.Range(RandomNumbersMinLength, RandomNumbersMaxLength);
184.             uniqueRandomNumbers = new NativeList<int>(randomNumbersLength, Allocator.Persistent);
185.             var managedSet = new HashSet<int>();
186.             for(int i = 0; i < randomNumbersLength; i++) {
187.                 managedSet.Add(Random.Range(0, RandomNumberMaxValue));
188.             }
189.             foreach(var num in managedSet) {
190.                 uniqueRandomNumbers.Add(num);
191.             }
192.         }
193.  
194.         [OneTimeTearDown]
195.         public void TearDown() {
196.             uniqueRandomNumbers.Dispose();
197.         }
198.  
199.         [SetUp]
200.         public void SetUpHashSet() {
201.             if(testHashSet.IsCreated) {
202.                 testHashSet.Dispose();
203.             }
204.             testHashSet = new NativeHashSet<int>(uniqueRandomNumbers.Length, Allocator.TempJob);
205.             var addJob = new AddJob {
206.                 HashSet = testHashSet.ToConcurrent(),
207.                 ToAdd = uniqueRandomNumbers.AsArray()
208.             }.Schedule(uniqueRandomNumbers.Length, 1);
209.             addJob.Complete();
210.         }
211.  
212.         [Test]
213.         public void Add_ShouldAddRange() {
214.             Assert.AreEqual(uniqueRandomNumbers.Length, testHashSet.Length);
215.         }
216.  
217.         [Test]
218.         public void Contains_ShouldContainRandomRange() {
219.             for(int i = 0; i < uniqueRandomNumbers.Length; i++) {
220.                 Assert.IsTrue(testHashSet.Contains(uniqueRandomNumbers[i]));
221.             }
222.         }
223.  
224.         [Test]
225.         public void Contains_ShouldContainRandomRangeAfterRemovingSome() {
226.             var numberToRemove = Random.Range(0, uniqueRandomNumbers.Length + 1);
227.             for(int i = 0; i < numberToRemove; i++) {
228.                 testHashSet.TryRemove(uniqueRandomNumbers[i]);
229.             }
230.             Assert.AreEqual(uniqueRandomNumbers.Length - numberToRemove, testHashSet.Length);
231.             for(int i = numberToRemove; i < uniqueRandomNumbers.Length; i++) {
232.                 Assert.IsTrue(testHashSet.Contains(uniqueRandomNumbers[i]));
233.             }
234.         }
235.  
236.         [Test]
237.         public void Clear_ShouldClearAdditions() {
238.             Assert.AreEqual(uniqueRandomNumbers.Length, testHashSet.Length);
239.             testHashSet.Clear();
240.             Assert.AreEqual(0, testHashSet.Length);
241.         }
242.     }
243. }
244.  

 

As far as i could tell only Dispose is missing setting buffer to null

Code (CSharp):

1.     public void Dispose() {
2. #if ENABLE_UNITY_COLLECTIONS_CHECKS
3.       AtomicSafetyHandle.CheckDeallocateAndThrow(m_Safety);
4.       DisposeSentinel.Dispose(ref m_Safety, ref m_DisposeSentinel);
5. #endif
6.       NativeHashSetData.DeallocateHashSet(buffer, allocator);
7.       buffer = null;
8.     }

 

struct Empty {}
NativeHashMap<T, Empty>

I believe this works.

 

Fixed for posterity.

 

Appreciate you sharing your code here

In the NativeHashSetData.cs on line 196 "while (values)" I get Error CS0029: Type byte* can't be implicitly converted to bool.
Should that be "while (values != null)" ? I have never written "unsafe" code in C# so I am just guessing.
Edit: That whole TryRemoveThreaded<T> methode seems to be faulty, amongst other things it also does not return a bool as it should at all.

 

Did you enabled Allow 'unsafe' code in you unity player settings?

 

yah I did, that was another issue I had but resolved. This is the method in NativeHashSetData which is causing the problems:

Code (CSharp):

1. public bool TryRemoveThreaded<T>(T value, int threadIndex) where T : IEquatable<T> {
2.             int* buckets = (int*)this.buckets;
3.             int* nextPtrs = (int*)this.next;
4.             int bucketIdx = value.GetHashCode() & bucketCapacityMask;
5.             int valuesIdx = buckets[bucketIdx];
6.             int prevValuesIdx;
7.             do {
8.                 valuesIdx = buckets[bucketIdx];
9.                 while(values)
10.             } while(valuesIdx != 0)
11.             while(valuesIdx != 0) {
12.                 if(valuesIdx < 0) {
13.                     valuesIdx = buckets[bucketIdx];
14.                 }
15.             }
16.         }

now the first error is that it has bool as return value, additionally values is a byte* and so "while(values)" causes the mentioned error.

 

TryRemoveThreaded() should not have existed in the code I gave, it was something I was experimenting with and was incomplete in my commits. NativeHashMap(which this is based on) doesn't support a jobified Remove() but should technically be possible. Of course if you remove and add in the same job, you get no guarantees as to what the result is. It sort of passed my tests but edge cases were buggy and I got bored, I'll remove that in my post. Idk how you accessed it though, unless you added the wrapper or called it directly.

It should be noted that Clear() in my version has a 10x performance improvement, depending on what you're doing, that may be an option, and you can re add what you need:
[See proposed memclear solution] Clear() on large NativeMultiHashMaps is causing performance issues.

 

I do all my native container clears on IJobs and it can have a big impact depending on what you are doing.
Here are a few generic jobs for that:

Code (CSharp):

1.  [BurstCompile]
2.   struct ClearNativeList<T> : IJob where T : struct {
3.     public NativeList<T> Source;
4.     public void Execute() {
5.       Source.Clear();
6.     }
7.   }
8.  
9.   [BurstCompile]
10.   struct ClearNativeQueue<T> : IJob where T : struct {
11.     public NativeQueue<T> Source;
12.     public void Execute() {
13.       Source.Clear();
14.     }
15.   }
16.  
17.   [BurstCompile]
18.   struct ClearNativeHashMap<T1, T2> : IJob where T1 : struct, IEquatable<T1> where T2 : struct {
19.     public NativeHashMap<T1, T2> Source;
20.     public void Execute() {
21.       Source.Clear();
22.     }
23.   }
24.  
25.   [BurstCompile]
26.   struct ClearNativeMultiHashMap<T1, T2> : IJob where T1 : struct, IEquatable<T1> where T2 : struct {
27.     public NativeMultiHashMap<T1, T2> Source;
28.     public void Execute() {
29.       Source.Clear();
30.     }
31.   }

 

@RecursiveEclipse
There must be a bug somewhere in the constructor.

Code (CSharp):

1. var set = new NativeHashSet<int4>(1000, Allocator.Persistent);

This makes Unity crash. The problem is <int4>, simple <int> seems to work fine.

I've attached the repro project for 2019.1.3f1.

PS
Line 191 in NativeHashSetData.cs looks suspicious:

Code (CSharp):

1. bucketOffset = nextOffset + (sizeof(int) * capacity) + JobsUtility.CacheLineSize - 1;

I changed sizeof(int) to UnsafeUtility.SizeOf<T>() and Unity stopped crashing. I'm not sure if it's a correct fix and also if it's the only place.

 

I'm unsure why that is, UnsafeUtility.SizeOf should just be a call to sizeof, but I still get crashes with your project even after changing everything.

 

I mean, sizeof(int) is not the same as sizeof(T) when T is not int.

 

Oh, yeah that'll do it. Bad day I guess, fixed.

EDIT: Maybe double oopsie, the original code should be correct, or close. I'll have to investigate.

 

Okay, now fixed for real. Was caused by bad MemClear length. The original was correct because next/buckets are just indexes(ints)/pointers to the values array.

 

@RecursiveEclipse is there any reason for the Assert.AreEqual in GetValueArray (line 94 in NativeHashSetData.cs)?

Also would something like this be fine for converting to managed C#?

Code (CSharp):

1.        public List<T> ToList<T>() {
2.            List<T> result = new List<T>();
3.            var buckets = (int*)this.buckets;
4.            var nextPtrs = (int*)next;
5.            for(int bucketIndex = 0; bucketIndex <= bucketCapacityMask; ++bucketIndex) {
6.                int valuesIndex = buckets[bucketIndex];
7.                while(valuesIndex > 0) {
8.                    result.Add(UnsafeUtility.ReadArrayElement<T>(values, valuesIndex - 1));
9.                    valuesIndex = nextPtrs[valuesIndex - 1];
10.                }
11.            }
12.            return result;
13.        }

 

Most likely because it's there in the NativeHashMap implementation when I ported it over. And I don't see why ToList couldn't be added, can't say how it functions in a job environment though. Why do you need managed list though?

 

A managed Dictionary is almost twice as fast as an unmanaged NativeHashMap:

https://imgur.com/de0ULTj

https://imgur.com/3yE3X8l

This is mainly because a NativeHashMap can't modify values so you have to Remove() and TryAdd() for every modification. But in the screenshots you also see that Dictionary.TryGetValue is faster than NativeHashMap.TryGetValue.

//edit I just realized I could add the NativeArray to the Dictionary.

 

What I mean is I'm not sure what your use case is. As I understand it you want a dictionary with some key and unique values(or am I mistaken?), but for what reason do you need IndexOf?(mentioned in the other thread of yours) Do you need to iterate or just know something exists and remove/add it?

 

I want to avoid duplicates so I'm checking if the element is in the collection already before adding it.

But right now I'm at a point where I have other optimizations for what I'm doing that only work in managed code. So I'll probably wont use Jobs after all.

 

It can. Previously on forum, months ago, I posted solution for Replace(key, value) and replacement by indexer [key]=value for NHM. But now it’s replaced and in latest collections package Unity implemented replace logic.