4 ms·

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 it

by mort96 2y ago

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/ https://www.hyrumslaw.com/).

aranke 2y ago
Python also, similar story.
pimeys 2y ago
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.
- masklinn 2y ago
  > 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).
  - pimeys 2y ago
    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.
    - masklinn 2y ago
      > 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.
      - SkiFire13 2y ago
        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.
      - pimeys 2y ago
        It's pretty easy to try out: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=6bfcdc0a94fcbb45cc430ab139a962cb 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.
masklinn 2y ago
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.
- Yoric 2y ago
  I remember that it actually broke a critical algorithm I was testing at the time. Fun times.
- zbentley 2y ago
  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 https://www.perlmonks.org/?node_id=1005122
  - masklinn 2y ago
    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.
    - zbentley 2y ago
      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 https://github.com/rust-lang/rust/issues/16799 2: https://bugs.ruby-lang.org/issues/4579 https://bugs.ruby-lang.org/issues/4579 3: https://wiki.openssl.org/index.php/Random_fork-safety https://wiki.openssl.org/index.php/Random_fork-safety
tucnak 2y ago
[flagged]
- kortex 2y ago
  It probably started with Zipf's law in the 1930s and then Murphys law a few years later.
- mort96 2y ago
  Americans? This is using "law" to mean something akin to "scientific law", such as Newton's three laws of motion or Mendel's three laws of inheritance; it's a description of what will happen. People were using "law" in this way since before the USA even was a country lol
hu3 2y ago
PHP too. Its arrays, which also behave like hash maps, respect insertion order. https://www.php.net/manual/en/language.types.array.php https://www.php.net/manual/en/language.types.array.php

by mort96 2y ago

aranke 2y ago

Python also, similar story.

pimeys 2y ago

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.

masklinn 2y ago
> 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).
- pimeys 2y ago
  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.
  - masklinn 2y ago
    > 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.
    - SkiFire13 2y ago
      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.
    - pimeys 2y ago
      It's pretty easy to try out: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=6bfcdc0a94fcbb45cc430ab139a962cb 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.

masklinn 2y ago

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.

Yoric 2y ago
I remember that it actually broke a critical algorithm I was testing at the time. Fun times.
zbentley 2y ago
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 https://www.perlmonks.org/?node_id=1005122
- masklinn 2y ago
  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.
  - zbentley 2y ago
    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 https://github.com/rust-lang/rust/issues/16799 2: https://bugs.ruby-lang.org/issues/4579 https://bugs.ruby-lang.org/issues/4579 3: https://wiki.openssl.org/index.php/Random_fork-safety https://wiki.openssl.org/index.php/Random_fork-safety

tucnak 2y ago

[flagged]

kortex 2y ago
It probably started with Zipf's law in the 1930s and then Murphys law a few years later.
mort96 2y ago
Americans? This is using "law" to mean something akin to "scientific law", such as Newton's three laws of motion or Mendel's three laws of inheritance; it's a description of what will happen. People were using "law" in this way since before the USA even was a country lol

hu3 2y ago

PHP too. Its arrays, which also behave like hash maps, respect insertion order. https://www.php.net/manual/en/language.types.array.php https://www.php.net/manual/en/language.types.array.php