Hacker News Reader

Comment by mort96 | Hacker News Reader

JavaScript is probably the most notable example of that. It used to not have a guaranteed iteration order, but browsers implemented it in such a way that the iteration order was the insertion order, and then that eventually got standardized because websites started depending on it.

For general purpose hash maps in standard libraries, I think you ought to either randomize the iteration order so that it's different every time, or guarantee an iteration order. Leaving it unspecified but predictable in practice is a recipe to fall victim to Hyrum's Law (https://www.hyrumslaw.com/).

View on HN

Javascript is kinda weird as the numerical keys have their own special ordering.

Python is probably the better known one, as it went through "arbitrary but deterministic" (before 3.3) to "wilfully non-deterministic" (from 3.3 to 3.6) to "insertion ordered" from 3.6, the latter of which was initially an implementation detail of improving the hashmap but was then made into the language spec starting 3.7.

I remember that it actually broke a critical algorithm I was testing at the time. Fun times.

Perl also changed its behavior, but in the other direction: a random seed was used per interpreter start after 5.18.

https://www.perlmonks.org/?node_id=1005122

That's actually the first python transition I mentioned, per-process hash randomisation had the effect of making map iteration non-deterministic. I believe in both cases this was in response to the hashdos concern / attacks.

Ah, sorry I didn't read that closely.

One minor nit (which the Perl press releases also mess up): the randomisation is per-interpreter, not per-process.

That's not a pedantic distinction. I've seen a couple of bugs/bad behaviors caused by forking servers forgetting to call srand(3)/re-randomize the hash seed after fork(2) and then relying on more randomness than they actually have. Suddenly (for example) hashing rate limiters or bloom filters all operate in near-lockstep, which can cause significant issues at high volumes.

Forking has also caused randomness-related issues (though not necessarily specifically re: hashing) for Rust[1] and Ruby[2], and probably many other platforms. OpenSSL seems to sidestep[3] the issue by using the PID as part of its salt internally.

1: https://github.com/rust-lang/rust/issues/16799

2: https://bugs.ruby-lang.org/issues/4579

3: https://wiki.openssl.org/index.php/Random_fork-safety

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.

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.

It's pretty easy to try out: https://play.rust-lang.org/?version=stable&mode=debug&editio...

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.

PHP too.

Its arrays, which also behave like hash maps, respect insertion order.

https://www.php.net/manual/en/language.types.array.php

Python also, similar story.

Reply on news.ycombinator.com