CHashMap::shrink_to_fit and CHashMap::with_capacity reserving ~3.4x buckets needed by ::insert
Hi, I have a CHashMap where I know I will insert N elements, N is large, and each element is quite small, so CHashMaps own memory usage is significant.
Unfortunately if I ::insert then ::shrink_to_fit or if I pre-allocate with_capacity(N) CHashMap reserves 4x N buckets rather than the expected N*loadfactor_denom/loadfactor_num that ::insert/::expand would check for.
This can result in maps growing significantly when ::shrink_to_fit is called, and means that one has to fudge the number passed to ::with_capacity to avoid over allocation of buckets in the "size known" usecase.
Two underling issues/questions:
- Is there a reason LENGTH_MULTIPLIER is 4 rather than 2? I think 2 is all that is needed to amortize the reallocation on growth when an insert/expand needs to expand.
- In known-length use cases CHashMap::shrink_to_fit and CHashMap::with_capacity is it an oversight that LENGTH_MULTIPLIER rather than MAX_LOAD_FACTOR_DENOM/MAX_LOAD_FACTOR_NUM is being applied to the length? Applying load factor would be considerably more space efficient, and more consistent with the bounds checked by insert/expand.
Happy to contribute changes if that helps.