Worse memory usage than old stdlib hashmap due to growth factor differences.

[emilio]

Hi,

So, in https://bugzilla.mozilla.org/show_bug.cgi?id=1747037, I'm investigating a memory usage regression that happened when removing our old fork of the stdlib hashmap (which we needed for various reasons, mostly fallible allocations) in favor of the new stdlib hashmap.

During the investigation, I found the underlying cause is just the growth factor choices. If I'm reading the code correctly, to allocate a enough capacity for a new capacity:

• Hashbrown seems to effectively double the capacity: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=5525f5bf5e1dfa77b4f4d46495d5d6ea
• Old hashmap grew more slowly, see https://bugzilla.mozilla.org/show_bug.cgi?id=1747037#c7.

I understand there are various trade-offs involved and this might just be by design, but it's not obvious to me from reading the code this is the intended behavior, so filing just in case.

[Amanieu]

Both hashbrown and the old pre-1.36 HashMap use power-of-2 sized tables, which means that any capacity growth requires doubling the table size by design. In both implementations this is done by taking the requested capacity (in terms of number of items that can actually be added), adding some buffer space (10% for the old HashMap, 14% for hashbrown) and then rounding that up to the next power of 2.

In fact when Rust upgraded the default HashMap to hashbrown we saw an overall reduction in memory usage because hashbrown uses a u8 for auxillary data per bucket instead of usize in the old HashMap.

The specific behavior that you are seeing is most likely due to the way hashbrown lazily clears out deleted items from the hash table. Buckets are marked as deleted (the actual key/value are still dropped eagerly), which avoids the need to shuffle items around every time a deletion occurs, but these DELETED entries still count as in-use for the purposes of capacity calculation.

When the capacity is exceeded, this code is executed which will either do a pass through the table to clear out DELETED entries to make space or allocate a new table with double the capacity.

[emilio]

Hmm, those tables are mostly insert-only though (well with some clear()s in between), so I'm not sure that theory makes sense... Unless for some reason clear() doesn't remove the deleted entries altogether perhaps?

I'll try to do some more digging though. Maybe that 10 vs. 14% just makes it go over the right amount for our hash tables. Though the differences in capacity I see are significant...

[Amanieu]

From the capacity numbers in the bugzilla issue, it seems to be due to the 10% vs 14% difference:

>>> 57 * 11 / 10
62.7
>>> 451 * 11 / 10
496.1
>>> 57 * 8 / 7
65.14285714285714
>>> 451 * 8 / 7
515.4285714285714

Notice how the numbers are very close to the power-of-2 boundary (64, 512), which is rounded up to the next power 2 to calculate the table capacity.

[emilio]

Yep, indeed, so this is all working as expected I guess. Thanks and sorry for the alarm!