Rust has HashMap with random order and BTreeMap which is ordered by the key. Additionally one can use IndexMap crate if wanting to keep the order of insertion in the map. The issue with the latter is how much memory it can waste in the worst cases. A good example is the serde_json library, if enabling the ordering of the maps. If you deserialize JSON into its dynamic Value enum, the resulting object can be many times bigger than the original string.
For immutable data that can fit to the CPU cache, utilizing a sorted vector can be many times faster and uses less memory compared to the maps.
> A good example is the serde_json library, if enabling the ordering of the maps. If you deserialize JSON into its dynamic Value enum, the resulting object can be many times bigger than the original string.
Deserialized non-trivial objects are generally larger than the original serialised value.
IndexMap should not generally be significantly larger than a HashMap though, unless the key and value are very small (sub-word).
We did measure significantly bigger memory usage with IndexMap and needed to revert back to HashMap eventually.
Deserializing into a defined struct does not waste as much memory as Value does. Especially due to the recursive nature of the Map variant, which can hold another Map.
> We did measure significantly bigger memory usage with IndexMap and needed to revert back to HashMap eventually.
That is strange and I’d assume the maintainers would be interested in the information.
By my reckoning HashMap would be consuming about capacity * 10/9 * (8 + sizeof key + sizeof value) while indexmap should be consuming capacity * 10/9 * 8 + capacity * (8 + sizeof key + sizeof value).
Unless indexmap reuses hashbrown directly in which case you’d get something like capacity * 10/9 (16 + sizeof key) + capacity * sizeof value.
Now, if you have an enum such as `serde_json::Value` which is kind of recursive with its `Map` variant, and you have a ton of dynamic JSON parsing in your code, these numbers really add up. And serde_json uses `BTreeMap` (I was wrong in my previous message) by default which is even smaller than `HashMap`.
The learning here is to avoid dynamic JSON parsing if you can. And if needing it, but not caring the insertion order, avoid the `preserve_order` feature flag.
The other learning here is that there is no map structure that fits to all purposes. They all have their pros and cons and you should choose the right one for the problem.
Indexmap does reuse hashbrown. It consists of a hashtable containing `usize` indexes into a `Vec` which in turn contains the actual entries (keys and values), along with a cached hash for the key. In the end the overhead should only be that index and the hash.
For immutable data that can fit to the CPU cache, utilizing a sorted vector can be many times faster and uses less memory compared to the maps.