automatic shrinking of hash table capacity is very expensive

[thestinger]

This interacts poorly with with_capacity since it will just end up shrinking the allocation immediately. It's very widely used since FromIter uses it with the iterator size hint. Even in code that's not pre-allocating capacity, the resize strategy results in many reallocations as the hash table shrinks and then grows again. Allocator improvements are possible but this is always going to be extremely expensive for huge collections on most platforms.

[Gankra]

If you ask for a hashmap with_capacity, it will record that number as a minimum and never shrink the map below that.

[thestinger]

I think it's trying to be too clever. It will always have problems reminiscent of the segmented stack thrashing issues. It would be better to just have the caller use shrink_to_fit as is done for vectors. There's a lot of value in having simple and predictable performance characteristics. Implementing jemalloc/jemalloc#134 would reduce the problem smaller for huge hash tables but I think it's still too aggressive as a default.

[Gankra]

cc @pczarn

[jfager]

Automatic shrinking is pretty surprising behavior, and only seems to be hinted at in the rustdoc via the reserve method. +1 to stop doing it.

[mitsuhiko]

+1 on explicit calls for more predictable performance. I was quite surprised to learn that this is what it does currently.

[arthurprs]

+1 same as @mitsuhiko

[pczarn]

I don't mind explicit calls. This is a simple approach. ResizePolicy would allow opt-in automatic shrinking in the future.

Just keep in mind that the capacity of a hash table affects the performance of accesses, even though it's more predicable. (Is it?)

[pczarn]

Fixed by #18770.

[Gankra]

🎊