5 ms·

Other languages don't generally have special order guarantees about standard maps. This seems very idiosyncratic.

by alayne 7y ago

dukoid 7y ago
Java added LinkedHashMap a while ago. I tend to default to it except for small temporary use cases where order absolutely won't matter or have an outside impact...
- masklinn 7y ago
  LinkedHashMap is not Java's "standard maps" though. If you tend to use it by default it's really a personal idiosyncrasy, especially as LLHM tend to be larger and slower than regular hashmaps due to having to maintain a doubly linked list. Python has had one such in the standard library for a decade or so.
  - oh-4-fucks-sake 7y ago
    Yep. Also, LinkedHashMap maintains ordering based on insertion order. So, iff you insert your data ordered how you want it, it's behaving as an ordered map. If you want true, self-reordering map, what you want is a TreeMap. Beauty with that one is that you have full control over defining the custom ordering function, because we're not always indexing a map by primitives or autoboxed type. I try to use it sparingly though as you're paying log(n) on pretty much all map operations. While we're here, another tidbit that's often overlooked in the Java collections: If you reallly care about iteration performance, your data is without nulls, your data is already ordered how you like it or you don't care about ordering, your qty items >= 10, and you don't need random access, then ArrayDeque is gonna be your horse because of how much better it co-locates its contents in memory and how much less overhead is required to maintain it during each operation compared to all the other List implementations, including ArrayList and LinkedList.
  - xxs 7y ago
    LHM is not slower for iteration (it's faster actually). LHM indeed pays 2 references per node but they are well worth as it has deterministic ordering/iteration and I have witnessed numerous cases with HashMap that show up in production only due to iteration order (esp after rehashing). The code is broken but the cases did not reproduce during testing... Now if the two extra references are an issue, consider that HashMap is quite space inefficient with having a dedicated node per each entry - that's the main price. The (simple) node memory footprint is 36bytes on heaps less than 32GB, i.e. compact pointers. The extra references add another 8 bytes for having an insert or access order. If the goal is getting a compact low memory footprint, HashMap is not fit for purpose. Overall it's the jack of all trades and even got reworked (java8) to support tri-based collision resolution for keys that implement Comparable. Couple years back I wrote CompactHashMap (under CC0) that has an average cost of 10bytes per entry and it's extremely compact for small sizes with having only 2 fields on its right own, so even small/empty maps are tiny. In microbenchmarks (same used in openjdk) it handily (2x) beats java.util.HashMap on "Traverse key or value", get/put have similar performance, and "Search Absent" is worse. The point is: LHM should be the go-to hashmap for java as being node based hashmap is justified (unlike java.util.HashMap)
gmanley 7y ago
I can't speak for all "other" languages but Ruby made the change years ago from 1.8 to 1.9. Ruby calls them hashes but they're standard maps. Obviously Ruby and Python are very similar but I think the point stands.
andrewshadura 7y ago
Tcl's dicts are ordered.
pimlottc 7y ago
For almost all intents and purposes, object keys have been ordered in JavaScript since ES2015. Map has always been ordered. https://www.stefanjudis.com/today-i-learned/property-order-is-predictable-in-javascript-objects-since-es2015/ https://www.stefanjudis.com/today-i-learned/property-order-i...
l_t 7y ago
JavaScript Maps are iterated over in insertion order.
_whiteCaps_ 7y ago
Golang map iteration is returned in random order specifically to make sure that people don't rely on the order. I think this feature says a lot about the philosophy of Python vs Go.
- MereInterest 7y ago
  Sounds like a fast and idiomatic way to shuffle a deck of cards is then to convert to a map and back.
  - kragen 7y ago
    No, it isn't random enough for that.
    - jarekkruk 7y ago
      IIRC it used to just start iteration at a pseudorandom index and then iterate normally. I looked at it couple years ago, don't know if they changed it.
      - kragen 7y ago
        It seems to do that, but I think it also tweaks the hash function for each newly created map, because in the code linked from https://news.ycombinator.com/item?id=22278753 https://news.ycombinator.com/item?id=22278753 I'm not getting rotations of the same iteration order when I generate two maps. There doesn't seem to be any randomness in mapiternext() itself. You could imagine that the hash function itself might do an adequate job of randomizing the order of the cards, though, especially if salted with a per-map salt. SipHash, for example, would probably not have any detectable biases in the distribution of the permutations thus produced. But whatever hash function Golang is using for my structs has an easily visible bias, as described in that comment.
  - thedirt0115 7y ago
    Convert a deck of cards ([]Card?) to a map (map[Card]bool?) and back just to shuffle? That's unlikely to be faster or more idiomatic than a straightforward implementation of the Fisher-Yates shuffle[1]. Try writing the code to do it both ways and compare. [1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
reubenmorais 7y ago
std::map in C++ stores keys in order. You have to use std::unordered_map to not get that behavior.
- xyzzyz 7y ago
  Yes, but that’s different kind of order. Python dicts order is insertion order, while std::map is key order.
jnwatson 7y ago
Users of JSON, probably the most common data interchange format on the planet, frequently have implicit requirements about key ordering. It is highly convenient to be able to parse a JSON string into a native Python data structure, add a field, emit it back, and preserve the ordering.
- anthonypasq 7y ago
  in what reasonable use case would the order of the properties on an object matter? I can't think of one
  - jwkane 7y ago
    when you are diffing the serialized output?
    - philwelch 7y ago
      From what I recall of the JSON standard itself, there's no guarantee about key ordering being significant. If you're diffing serialized output to compare two JSON objects you need to be serializing it in a consistent format, otherwise even whitespace is going to throw you off.
      - jwkane 7y ago
        It's significant to a human that wants to know what has changed.
        philwelch 7y ago
        If a human is inspecting serialized JSON using pen and paper, the human is presumably clever enough to match up key for key regardless of ordering. If the human is using a computer to compare two JSON payloads (as the use of a diffing algorithm suggests), the human and computer should be clever enough as a team to realize that they could just deserialize and reserialize each JSON payload such that the keys were lexicographically sorted and the data was pretty-printed in the exact same way before running it through the diffing algorithm. `jq -Sc` would do the trick.
Izkata 7y ago
In regards to sibling replies, does it feel to anyone else like everything (except golang) is converging towards PHP's array() ?
- masklinn 7y ago
  Interestingly enough here it was kinda but kinda not the other way around: historically PHP used a closed-addressing hash map and threaded a doubly linked list through it to maintain the insertion order. But the dict TFA talks about doesn't use a doubly linked list, or closed addressing, its ordering is a side-effect of its implementation but not originally a core goal (memory saving and iteration speed were). It'd probably been proposed by others before but it came to wider attention after Raymond Hettinger (a core dev) proposed it a few years back[0]. PHP actually released it first[1], closely followed by pypy[2]. CPython only got around to it some time later[3] [0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... [1] https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implem... [2] https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff... [3] https://docs.python.org/3/whatsnew/3.6.html?highlight=3.6#whatsnew36-compactdict https://docs.python.org/3/whatsnew/3.6.html?highlight=3.6#wh...
pletnes 7y ago
The ordering property is a side effect of the new and more cpu/memory efficient data structure. It would be very surprising to say no to a 2x performance jump to avoid the (sometimes useful) ordering.

Other languages don't generally have special order guarantees about standard maps. This seems very idiosyncratic.

by alayne 7y ago

Other languages don't generally have special order guarantees about standard maps. This seems very idiosyncratic.

Java added LinkedHashMap a while ago. I tend to default to it except for small temporary use cases where order absolutely won't matter or have an outside impact...

masklinn 7y ago
LinkedHashMap is not Java's "standard maps" though. If you tend to use it by default it's really a personal idiosyncrasy, especially as LLHM tend to be larger and slower than regular hashmaps due to having to maintain a doubly linked list. Python has had one such in the standard library for a decade or so.
- oh-4-fucks-sake 7y ago
  Yep. Also, LinkedHashMap maintains ordering based on insertion order. So, iff you insert your data ordered how you want it, it's behaving as an ordered map. If you want true, self-reordering map, what you want is a TreeMap. Beauty with that one is that you have full control over defining the custom ordering function, because we're not always indexing a map by primitives or autoboxed type. I try to use it sparingly though as you're paying log(n) on pretty much all map operations. While we're here, another tidbit that's often overlooked in the Java collections: If you reallly care about iteration performance, your data is without nulls, your data is already ordered how you like it or you don't care about ordering, your qty items >= 10, and you don't need random access, then ArrayDeque is gonna be your horse because of how much better it co-locates its contents in memory and how much less overhead is required to maintain it during each operation compared to all the other List implementations, including ArrayList and LinkedList.
- xxs 7y ago
  LHM is not slower for iteration (it's faster actually). LHM indeed pays 2 references per node but they are well worth as it has deterministic ordering/iteration and I have witnessed numerous cases with HashMap that show up in production only due to iteration order (esp after rehashing). The code is broken but the cases did not reproduce during testing... Now if the two extra references are an issue, consider that HashMap is quite space inefficient with having a dedicated node per each entry - that's the main price. The (simple) node memory footprint is 36bytes on heaps less than 32GB, i.e. compact pointers. The extra references add another 8 bytes for having an insert or access order. If the goal is getting a compact low memory footprint, HashMap is not fit for purpose. Overall it's the jack of all trades and even got reworked (java8) to support tri-based collision resolution for keys that implement Comparable. Couple years back I wrote CompactHashMap (under CC0) that has an average cost of 10bytes per entry and it's extremely compact for small sizes with having only 2 fields on its right own, so even small/empty maps are tiny. In microbenchmarks (same used in openjdk) it handily (2x) beats java.util.HashMap on "Traverse key or value", get/put have similar performance, and "Search Absent" is worse. The point is: LHM should be the go-to hashmap for java as being node based hashmap is justified (unlike java.util.HashMap)

gmanley 7y ago

I can't speak for all "other" languages but Ruby made the change years ago from 1.8 to 1.9. Ruby calls them hashes but they're standard maps. Obviously Ruby and Python are very similar but I think the point stands.

andrewshadura 7y ago

Tcl's dicts are ordered.

pimlottc 7y ago

For almost all intents and purposes, object keys have been ordered in JavaScript since ES2015. Map has always been ordered. https://www.stefanjudis.com/today-i-learned/property-order-is-predictable-in-javascript-objects-since-es2015/ https://www.stefanjudis.com/today-i-learned/property-order-i...

l_t 7y ago

JavaScript Maps are iterated over in insertion order.

_whiteCaps_ 7y ago

Golang map iteration is returned in random order specifically to make sure that people don't rely on the order. I think this feature says a lot about the philosophy of Python vs Go.

MereInterest 7y ago
Sounds like a fast and idiomatic way to shuffle a deck of cards is then to convert to a map and back.
- kragen 7y ago
  No, it isn't random enough for that.
  - jarekkruk 7y ago
    IIRC it used to just start iteration at a pseudorandom index and then iterate normally. I looked at it couple years ago, don't know if they changed it.
    - kragen 7y ago
      It seems to do that, but I think it also tweaks the hash function for each newly created map, because in the code linked from https://news.ycombinator.com/item?id=22278753 https://news.ycombinator.com/item?id=22278753 I'm not getting rotations of the same iteration order when I generate two maps. There doesn't seem to be any randomness in mapiternext() itself. You could imagine that the hash function itself might do an adequate job of randomizing the order of the cards, though, especially if salted with a per-map salt. SipHash, for example, would probably not have any detectable biases in the distribution of the permutations thus produced. But whatever hash function Golang is using for my structs has an easily visible bias, as described in that comment.
- thedirt0115 7y ago
  Convert a deck of cards ([]Card?) to a map (map[Card]bool?) and back just to shuffle? That's unlikely to be faster or more idiomatic than a straightforward implementation of the Fisher-Yates shuffle[1]. Try writing the code to do it both ways and compare. [1]: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

reubenmorais 7y ago

std::map in C++ stores keys in order. You have to use std::unordered_map to not get that behavior.

xyzzyz 7y ago
Yes, but that’s different kind of order. Python dicts order is insertion order, while std::map is key order.

jnwatson 7y ago

Users of JSON, probably the most common data interchange format on the planet, frequently have implicit requirements about key ordering. It is highly convenient to be able to parse a JSON string into a native Python data structure, add a field, emit it back, and preserve the ordering.

anthonypasq 7y ago
in what reasonable use case would the order of the properties on an object matter? I can't think of one
- jwkane 7y ago
  when you are diffing the serialized output?
  - philwelch 7y ago
    From what I recall of the JSON standard itself, there's no guarantee about key ordering being significant. If you're diffing serialized output to compare two JSON objects you need to be serializing it in a consistent format, otherwise even whitespace is going to throw you off.
    - jwkane 7y ago
      It's significant to a human that wants to know what has changed.
      - philwelch 7y ago
        If a human is inspecting serialized JSON using pen and paper, the human is presumably clever enough to match up key for key regardless of ordering. If the human is using a computer to compare two JSON payloads (as the use of a diffing algorithm suggests), the human and computer should be clever enough as a team to realize that they could just deserialize and reserialize each JSON payload such that the keys were lexicographically sorted and the data was pretty-printed in the exact same way before running it through the diffing algorithm. `jq -Sc` would do the trick.

Izkata 7y ago

In regards to sibling replies, does it feel to anyone else like everything (except golang) is converging towards PHP's array() ?

masklinn 7y ago
Interestingly enough here it was kinda but kinda not the other way around: historically PHP used a closed-addressing hash map and threaded a doubly linked list through it to maintain the insertion order. But the dict TFA talks about doesn't use a doubly linked list, or closed addressing, its ordering is a side-effect of its implementation but not originally a core goal (memory saving and iteration speed were). It'd probably been proposed by others before but it came to wider attention after Raymond Hettinger (a core dev) proposed it a few years back[0]. PHP actually released it first[1], closely followed by pypy[2]. CPython only got around to it some time later[3] [0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... [1] https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implem... [2] https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff... [3] https://docs.python.org/3/whatsnew/3.6.html?highlight=3.6#whatsnew36-compactdict https://docs.python.org/3/whatsnew/3.6.html?highlight=3.6#wh...

pletnes 7y ago

The ordering property is a side effect of the new and more cpu/memory efficient data structure. It would be very surprising to say no to a 2x performance jump to avoid the (sometimes useful) ordering.