Rfcs: HashMap: use similar implementation as Python's "modern dictionaries"

[jhpratt]

This was proposed in 2012 by Raymond Hettinger. The original proposal can be seen here.

Basically, instead of storing the full table, the indices can be stored in a separate vector, saving memory that would otherwise be unused. As a bonus, this makes it trivial to recover objects in insertion order,

One thing the Python proposal notes is to use None for marking an empty index. Of course, Rust doesn't have null, so I'd recommend using -1 instead, as that can never be a valid index.

This implementation claims to shrink memory usage by ~30% in addition to making iteration and enumeration faster (since you never have to view empty indices).

Both Python and JavaScript use this; I'm unaware of any other languages that do.

[Bobo1239]

@jhpratt Do you mean something like this? https://github.com/bluss/ordermap

[jhpratt]

Basically, yes. Upon quick overview of the README it's missing some features, but it certainly appears to be an implementation of Python's "modern dictionaries".

[Diggsey]

@jhpratt You can't expect to get the same space savings as observed in the original proposal because rust uses robin-hood hashing, which supports much higher loads (90% or more) without much reduction in performance, compared to alternative schemes which max out around 60%.

Tracking the indices separately may well consume more memory, particularly for small values, and there's also the cost of performing two allocations instead of one each time the hash table is resized. Finally there's the performance impact of the indirect lookup each time an entry is accessed, which may be quite a bit higher than you expect.

Maybe the hashmap could switch implementations based on the size of the value? I imagine this could be an improvement if particularly large structures are being stored as values or keys.

[Centril]

I think you only actually need an RFC if as a result of a change you have to make API surface changes (and if you introduce breaking changes with such an RFC may be a nonstarter to begin with) or introduce a new API (as in introducing ordermap into libstd). Otherwise, if the changes are transparent and you can show consistent improvements in benchmarks across use cases I think you can just create a PR against rust-lang/rust and have it discussed there.

[Benjamin-L]

I would definitely be uncomfortable with having the standard library hash map change implementation silently. If both impelemntations are going to be used, the programmers using the hash map should be able to make the decision and be aware of performance implications.

[burdges]

We cannot do this in HashMap because HashMap<K,V> becomes less efficient if either size_of::<V>() <= 8, or else if V itself is a simple allocation, ala HashMap<K,Box<..>>. I'd expect this wastes CPU cache for complex allocations too, like HashMap<K,String>, HashMap<K,Vec<..>>, HashMap<K,HashMap<..>>, etc. and maybe atomic types, like HashMap<K,Arc<..>> or HashMap<K,Mutex<..>>.

Instead, I think OrderMap should simply document under what condition it may provide some performance improvement and/or memory savings over HashMap. Anyone who cares but falls into unclear cases can do their own benchmarks.

[Centril]

Triage: @jhpratt What is the status of this issue?