40% faster NativeHashMap reallocations

[keen glade]

I was doing an optimization pass on my DynamicHashMap and was looking at a comparison with NativeHashMap when I noticed reallocating was doing a bunch of work it didn't need to, so I spent some time optimizing it.
Final Results: 40% faster reallocations
-edit- The middle case is the NativeHashMap optimized results
(Anyone may use code without Attribution)

Passes all Collection Tests

This is all about the ResizeExact method
First Observation. Doing a Find on every element

internal void ResizeExact(int newCapacity, int newBucketCapacity)
        {
            int keyOffset, nextOffset, bucketOffset;
            int totalSize = CalculateDataSize(newCapacity, newBucketCapacity, SizeOfTValue, out keyOffset, out nextOffset, out bucketOffset);

            var oldPtr = Ptr;
            var oldKeys = Keys;
            var oldNext = Next;
            var oldBuckets = Buckets;
            var oldBucketCapacity = BucketCapacity;

            Ptr = (byte*)Memory.Unmanaged.Allocate(totalSize, JobsUtility.CacheLineSize, Allocator);
            Keys = (TKey*)(Ptr + keyOffset);
            Next = (int*)(Ptr + nextOffset);
            Buckets = (int*)(Ptr + bucketOffset);
            Capacity = newCapacity;
            BucketCapacity = newBucketCapacity;

            Clear();

            for (int i = 0, num = oldBucketCapacity; i < num; ++i)
            {
                for (int idx = oldBuckets[i]; idx != -1; idx = oldNext[idx])
                {
                    var newIdx = TryAdd(oldKeys[idx]);
                    UnsafeUtility.MemCpy(Ptr + SizeOfTValue * newIdx, oldPtr + SizeOfTValue * idx, SizeOfTValue);
                }
            }

            Memory.Unmanaged.Free(oldPtr, Allocator);
        }```

To fill gaps when shrinking it does a TryAdd, but a TryAdd always does a Find first but when moving data from one hashmap to the next this isn't required as we know for certain the element won't exist
```cs
        internal int TryAdd(in TKey key)
        {
            if (-1 == Find(key))
            {```

Replacing this method with a dedicated method for resizing nets a decent speed up by itself of around 25% (I also removed the capacity check as it's not required as we know our capacity is fine)

        internal int AddForResize(in TKey key)
        {
            // Allocate an entry from the free list
            var idx = this.FirstFreeIdx;

            if (idx >= 0)
            {
                FirstFreeIdx = Next[idx];
            }
            else
            {
                idx = AllocatedIndex++;
            }

            CheckIndexOutOfBounds(idx);

            UnsafeUtility.WriteArrayElement(Keys, idx, key);
            var bucket = GetBucket(key);

            var next = this.Next;
            // Add the index to the hash-map
            next[idx] = Buckets[bucket];
            Buckets[bucket] = idx;
            Count++;

            return idx;
        }```

Second Observation was this is still slower than a reallocation in the 'slower' NativeParallelHashMap which just does memcpys and recalculates bucket array because it doesn't support Trim, however we can still utilize its faster path when increasing capacity leading us to the final version that uses separate paths when increasing vs shrinking capacity.
Netting us a 40% speed up when having to reallocate a hashmap.

[timid haven]

[foggy bridge]

Thanks for the changes! We'll take a look but a cursory glance looks promising 🙂

[keen glade]

random side note: this[key] does a similar thing when writing

        public TValue this[TKey key]
        {
            get
            {
                CheckRead();

                TValue result;
                if (!m_Data->TryGetValue(key, out result))
                {
                    ThrowKeyNotPresent(key);
                }

                return result;
            }

            set
            {
                CheckWrite();

                var idx = m_Data->Find(key);
                if (-1 == idx)
                {
                    TryAdd(key, value);
                    return;
                }

                UnsafeUtility.WriteArrayElement(m_Data->Ptr, idx, value);
            }
        }```
Does a find, if it doesn't Find does a TryAdd which then does another Find. This is a lot less costly though as it's only a single element