Search Unity

Is there no NativeHashSet or am I blind?

Discussion in 'Data Oriented Technology Stack' started by AurelWu, May 5, 2019.

  1. AurelWu

    AurelWu

    Joined:
    Oct 11, 2013
    Posts:
    26
    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?)
     
  2. Shinyclef

    Shinyclef

    Joined:
    Nov 20, 2013
    Posts:
    364
    I was wondering the same thing yesterday.
     
  3. Abbrew

    Abbrew

    Joined:
    Jan 1, 2018
    Posts:
    145
    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.
     
  4. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    102
    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.  
     
    Last edited: Jun 15, 2019
  5. GilCat

    GilCat

    Joined:
    Sep 21, 2013
    Posts:
    417
    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.     }
     
  6. capyvara

    capyvara

    Joined:
    Mar 11, 2010
    Posts:
    70
    struct Empty {}
    NativeHashMap<T, Empty>

    I believe this works.
     
    Razmot likes this.
  7. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    102
    Fixed for posterity.
     
    GilCat likes this.
  8. AurelWu

    AurelWu

    Joined:
    Oct 11, 2013
    Posts:
    26
    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.
     
    Last edited: May 15, 2019
  9. GilCat

    GilCat

    Joined:
    Sep 21, 2013
    Posts:
    417
    Did you enabled Allow 'unsafe' code in you unity player settings?
     
  10. AurelWu

    AurelWu

    Joined:
    Oct 11, 2013
    Posts:
    26
    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.
     
  11. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    102
    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.
     
    Last edited: May 18, 2019
  12. GilCat

    GilCat

    Joined:
    Sep 21, 2013
    Posts:
    417
    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.   }
     
    Razmot likes this.
  13. alexzzzz

    alexzzzz

    Joined:
    Nov 20, 2010
    Posts:
    1,404
    @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.
     

    Attached Files:

    Last edited: May 24, 2019
  14. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    102
    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.
     
  15. alexzzzz

    alexzzzz

    Joined:
    Nov 20, 2010
    Posts:
    1,404
    I mean, sizeof(int) is not the same as sizeof(T) when T is not int.
     
  16. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    102
    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.
     
    Last edited: May 30, 2019
  17. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    102
    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.
     
    Last edited: Jun 5, 2019
    alexzzzz likes this.
  18. sollniss

    sollniss

    Joined:
    Aug 23, 2017
    Posts:
    8
    @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.        }
     
  19. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    102
    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?
     
    Last edited: Aug 12, 2019
  20. sollniss

    sollniss

    Joined:
    Aug 23, 2017
    Posts:
    8
    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.
     
  21. RecursiveEclipse

    RecursiveEclipse

    Joined:
    Sep 6, 2018
    Posts:
    102
    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?
     
  22. sollniss

    sollniss

    Joined:
    Aug 23, 2017
    Posts:
    8
    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.
     
  23. eizenhorn

    eizenhorn

    Joined:
    Oct 17, 2016
    Posts:
    1,431
    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.