Bug "Hashmap is Full" Error before hashmap is full.

I think I may have encountered a new bug with NativeMultiHashMap. It's difficult to explain, but here goes:

1. If I set the capacity of the NativeMultiHashMap to 100...
2. ...And then I try to add 100 elements to the NativeMultiHashMap...
3. ...I will hit a "Hashmap is Full" error when I try to add the 100th element. All previous elements add without error.

No matter what the hashmap's capacity is, I always get this error when I try to add (what should be) the last possible element. I hope that makes sense.

I'm specifically hitting the error at UnsafeHashMap.cs, line #528.

I'm creating a test project to confirm this, and I'll file a bug if it's a reliable repro.

But in the meantime: Am I missing something about how NativeMultiHashMaps should work? If I have a hashmap with a capacity of 100, I should be able to add 100 elements to it, right?

Many thanks!

 

Ah, nevermind. I just ran into a case in which I got the same error on the 99th time I tried to add to the hashmap.

Man, I wish I knew what this issue was.

 

After more tests, I'm hitting this error when the hashmap is far from full.

For example, on my 51st add to a NativeMultiHashMap with a 157 capacity.

 

That sounds like a bug. However, in general, hash maps are best when 50-70% full (when using robin hood hashing (which Unity should be but isn't), you can go up to ~90% if the hashes are reasonably well-distributed, but this can still break if your hashes are badly distributed (which can happen if your hash function sucks, your data happens to fall into a poor pattern, or an attacker deliberately is trying to break your system)). This is because of collisions. When more than 1 key hashes to the same bucket, then you get a collision, which is expensive to resolve. The more full the hash table is, the more chance of collision.

tl;dr: 51 elements with a 157 capacity is definitely a bug. But try to allocate hash maps with about 150% the capacity you need.

 

Thank you for that response, sincerely.

Is this really true? Have you all been over sizing your hashmap capacities to 150-200% of what you’ll need?

 

This issue has stopped me in my tracks this week.

It's a tough problem to diagnose, and even tougher to simplify into a test project I can legally submit in a bug report.

It would help to know if anyone else has run into anything remotely like this. Thank you for any input.

This is the third, show-stopping bug in a DOTS package I've run into in the last few moths, which has ground development to a halt for a week or more. It's been one after the other - as soon as I think I'm in the clear, there's a new issue in Entities or Burst which can only fixed in a new package update.

 

Seem like the bug may be related to NativeMultiHashMap.ParallelWriter. I can't get a repro when I'm adding to the NativeMultiHashMap directly.

 

The non-parallel writers allow the hashmap to grow. However, the parallel writers do not.

 

I’m hitting the error well before the hashmap has reached it’s capacity. For example, on the 4th Add out of a capacity of 200.

 

I'm aware of that, and I don't have an explanation for why that is. I avoid NativeMultiHashMap.ParallelWriter for many reasons. I was simply clarifying why you weren't seeing that issue when not using ParallelWriter.

 

Oh, right! Man I’m frazzled today. Thank you.

 

Can we see the code?

 

Thanks for asking. I can’t show the code as is, for annoying reasons.

I’m working on a repro project now, and I will post the asap.

 

There's a lot of things to consider if you feel like geeking out over data structures. This is a good overview: https://medium.com/@leventov/hash-table-tradeoffs-cpu-memory-and-variability-22dc944e6b9a . The article I liked earlier talks about a specific, very very fast, implementation of a hash map: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/

As for the "right" load factor, it depends on how collisions are resolved, and how much memory you're willing to sacrifice for speed. Java uses 0.75 as the load factor (when it's 75% full, it resizes, so will be in the range of like 40-75% full at most times). .NET

Dictionary<,>

uses 1 as its maximum (so will be in the range of 50%-100% full at most times). Python uses 2/3 (so 30-66% or so). Generally, the lower the load factor, the fewer collisions (so, faster lookup and insert), but more memory use.

Anyway, it's not a huge deal unless you're trying to squeeze out every last bit of performance, or you need predicatable lookup times (with a high load factor, some lookups can be instant and some can be slow).

 

What's your key/value pair at least. I've had issues with nhm before, for example https://forum.unity.com/threads/nat...r-tryadd-is-not-thread-safe-with-repo.886318/

So it's useful to know what to avoid!

I never actually tested if this was fixed, though they said it was, but I should probably check.

Side note, if you set capacity to capacity + 1, does issue still exist? (specifically for the cases where you're running out really early)

 

Ah, I remember your post from back then. When you made it, it prompted me to go through and make sure I wasn’t relying on any NativeHashMaps for more than membership checks. Thanks again.

Code still coming asap. To answer your questions:

1. The map I’m getting the error for is a NativeMultiHashMap<Entity, Entity>.

2. Yes, even if my map is always twice the capacity of what I’m adding to it, I still get this error.

And it’s not always on the same add: If my map has a capacity of 200, I might get the error on the 4th time I call Add(), or on the 40th.

 

I met this question before, and I add a `Debug.Log` before the `TryAdd` method, then 'hashmap is full' message disappeared.

SO WRIED! WHY?

 

Is NativeMultiHashMap.ParallelWriter still not stable?