Measure the memory usage of HashMap better

[jdm]

Currently we estimate it at capacity() * (size_of::<K>() + size_of::<V>()). I briefly looked into duplicating the internals in mem.rs, but it was looked really complicated.

[SimonSapin]

Should we file an issue on Rust to add some API?

[Gankra]

As of today (and for the last ~year) it's basically (cap() * 11 / 10) * (size(K) + size(V) + size(u64)), but there's some minor loss due to alignment and integer arith.

Basically a HashMap is [hash, hash, hash, ..., key, key, key, ... value, value, value...] allocated as a single buffer via jemalloc.

But the reported capacity is real_cap * 10 / 11 because we don't let the table get totally full (~91% max load factor). The internal capacity is always a power of two, so some careful math can let you figure out the "true" inner capacity from the reported capacity if you really care (round to the nearest power of two should be sufficient).

In practice I wouldn't expect any meaningful wasteage from alignment/padding. At most it would basically be the wasteage in a (u64, K, V) tuple, I think.

[Gankra]

As an aside, @pczarn had a PR to change this to [hash, hash, hash,... (K,V), (K,V), (K,V), ...] which shuffled around some perf characteristics, but we didn't go forward with it.

[pczarn]

Exactly as above, and (capacity() * 11 / 10).next_power_of_two() * (...) will correct off-by-one loss.

[nnethercote]

This issue is now blocking https://bugzilla.mozilla.org/show_bug.cgi?id=1387958. Stylo has some significant HashMaps which I want to measure the size of. I can estimate the size, but (a) it might be inaccurate (i.e. it won't measure slop), and (b) DMD doesn't get told that the block has been reported.

It would be nice if HashMap had a function exposing the pointer to the storage. (That's assuming there is a single pointer; it's conceivable that the internal representation could use 2 or 3 separate chunks of storage.)

What I'll probably end up doing is cloning HashMap for Stylo. Stylo already has its own copy of Arc, and we've been considering cloning Vec and HashMap anyway to add fallible growth methods.

[nnethercote]

Cloning (forking) HashMap turns out to be difficult, because it uses various unstable Rust features and we are using stable Rust only for Firefox.

[SimonSapin]

We could consider an alternative hash map like https://crates.io/crates/ordermap. Adding memory tracking might be easier there.

[dralley]

Still applicable after HashBrown-based HashMaps?

[nnethercote]

The change to HashBrown doesn't affect this.

[str4d]

I've started assembling a traits crate aiming to make it easier to expose these kinds of measurements (by standardising how type implementors can expose this information, and providing obvious compositions): https://github.com/str4d/memuse

[SimonSapin]

@str4d How does this differ from https://searchfox.org/mozilla-central/source/servo/components/malloc_size_of/lib.rs (if it were on crates.io) or https://crates.io/crates/heapsize ?

---

My point above about an alternative map is that the maintainers of hashbrown may be willing to add a Cargo feature flag and an optional dependency on a crate that does kind of memory tracking. Or maybe an ad-hoc method that exposes the relevant information.

In comparison, the bar for adding this functionality to standard library types is higher.

[str4d]

Thanks for the links!

I'd hunted for an existing crate I could use before writing my own, and yet somehow never stumbled upon heapsize, which takes the same approach as I have. It's got some impls I should also add! Looks like the main differences are:

• heapsize has been unmaintained for three years (so it wouldn't have done me any good to use it or attempt to build on it).
• memuse includes more precise calculations for types like HashMap (taking account of how hashbrown is implemented, rather than undercounting by estimating directly from HashMap::capacity).
  • This approach is obviously not long-term stable in the face of improvements to these types, but for the regular crate ecosystem the intent is that implementing the trait themselves ensures accuracy, and the Rust stdlib is a smaller target for memuse to keep pace with.
• memuse::DynamicUsage::dynamic_usage is documented as returning a "best estimate", and the trait also provides access to precise lower and upper bounds for use when externally wrapping a complex type we can't safely introspect (like HashMap or BTreeMap).

I had no idea that malloc_size_of existed (though I would have found it had I found heapsize), but I see now it's the code this issue was indirectly referring to. It looks like it enables more precision than my crate (as it can return the allocated rather than requested memory), but at the cost of having to pass around the allocator, and then for more complex types, when the allocator can't support the necessary functionality it falls back to the same undercounting estimate as heapsize (which is the topic of this issue).

I think the approach taken in malloc_size_of is interesting, and I'm going to look more closely at it and see if there are aspects I could incorporate, but obviously something that is explicitly documented as "not intended to be published on crates.io" isn't useful to me or the ecosystem as a whole. That being said, I now see that my original comment was misplaced, as the Servo devs have already tried and abandoned the approach I'm taking.

I think the best way to make progress on this issue would be to take the HashMap calculation logic that I extracted from hashbrown into memuse, and duplicate it in malloc_size_of (i.e. what the OP said they'd tried doing, and I have now done). That would greatly improve the lower bound that it is reporting when malloc_enclosing_size_of is unavailable.

[typesanitizer]

Looks like hashbrown exposes an API for memory usage information when using the (experimental) raw feature: https://docs.rs/hashbrown/latest/hashbrown/raw/struct.RawTable.html#method.allocation_info