5 ms·

> The surprising/interesting thing about this article is the notion that insertion order is the order that you want to iterate through a hash map. I agree, thi

by arsome 5y ago

> The surprising/interesting thing about this article is the notion that insertion order is the order that you want to iterate through a hash map. I agree, this is what java calls a "LinkedHashMap" and what python calls an "OrderedDictionary" - there are times when it's quite useful, but often it's simply not necessary, uses extra memory and shouldn't be the default when you just need a hashmap.

ErikCorry 5y ago
The nice thing is the compact dictionary doesn't use extra memory, so why not make it the default?
- tialaramex 5y ago
  It may (perhaps, I can't tell) not use "extra memory" compared to the data structure they had before, but it definitely is using memory it wouldn't need if it didn't preserve order. Otherwise it would be more or less a violation of the pigeonhole principle. The insertion order is information, if you don't need to store that anywhere but you promise to give it back anyway that's a hole in your information theory.
  - floitsch 5y ago
    With that reasoning a sorted list would need more memory than an unsorted list.
    - tialaramex 5y ago
      How so? Sorting changes the order of the list, to the extent it's adding information (the sort order) it's also destroying the same amount of information (the previous order). It's easy enough (including by accident) to deliver insertion ordered iterator behaviour for small hash maps that have never had any items removed, but after that things get sticky very quickly.
      - floitsch 5y ago
        You were stating that "[...] it definitely is using memory it wouldn't need if it didn't preserve order.". There is no reason for that. A sorted list doesn't need more memory than an unsorted list. And an insertion-sorted map doesn't need to use more memory than a map that doesn't keep the order. Independently, some properties we deem valuable are often side-products of the way the data-structure works. For example, an efficient binary search tree will naturally tend to be balanced. In the case of efficient hash maps, it is now common to add the key/value pair at the end of an internal vector. Maintaining the insertion order this way doesn't add any cost.
        tialaramex 5y ago
        It actually does have a cost. In fact I'm pretty sure it has two separate types of cost, so let's talk about both of them. Firstly, and this is orthogonal to my original point, whenever people say "Cost" they actually silently mean "... that I care about" and so we're involuntarily obliged to agree to stop caring about anything else. Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections. But my main point is that the requirement for ordering forces you to dispose of otherwise permissible optimisations which could destroy the order. You actually ran head first into this in the article, when repeatedly removing and adding elements blows up by clogging your data structure with tombstones. Swiss Tables wouldn't clog up with tombstones. Since they don't care about ordering they only need tombstones at all in uncommon special cases (specifically, if the entire rest of the group is full or tombstones), in most cases Swiss Tables get to just set removed (key, value) pairs as empty. But this optimisation isn't open to you.
        joshuamorton 5y ago
        Sticking tombstones in the backing array doesn't actually cost you anything though. The backing array still needs to be the same size. Like maybe you end up having to re-hash more often? >Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections. Yes but this cost goes away if you commit to it, and the alternative (like what go does) to force the order to change all the time also comes with a complexity cost vs. doing "nothing" and having the order be arbitrary and sometimes, but not actually, reliable.
- deathanatos 5y ago
  It does, though. See the diagram in the article. There's two allocated arrays there: one for the real hash table (on top) and one for the "backing array" which then stores the actual items. The "extra" bit is the indexes in the top allocation: those indexes would be omitted in a normal (unsorted) hash map. (That is, a normal hash map allocates a single array, which is the storage for both the hash table and the items it contains.¹) (There's also some extra time requirements, too, to chase that additional pointer from the top table to the bottom one.) ¹N.b. in some languages those items will be references, but that doesn't matter for the comparison here.
  - ErikCorry 5y ago
    Note that the bottom array can be densely packed, whereas the top one must have gaps to avoid excessive probing. If you only had one array you would have to put the gaps in that array, and it is at least 2 words per entry (much worse if you are inlining objects). So it's not so clear. If you want to save space you can also omit the hash bits stored in the index and reduce the width of the index entries to 16 or 8 bits on small maps. In practice the compact dict does very well on space. Much better than Java's unordered bucket-based HashMap for example. It's true that there's an extra pointer chase.
    - deathanatos 5y ago
      Ah, that's an excellent point, and it does muddle the water about which would win out. Deletes could still leave holes in the storage array, but I think I agree (and your article also states it) that the common case is likely fill table with data, and then perform lookups. (And I had thought bucket-based hashmaps had very much fallen out of favor to the point where they really weren't the choice of standard libraries anymore, precisely because of the additional allocations & pointer chasing they required? I'm not a Java person.)
      - pclmulqdq 5y ago
        C++ unordered_map unfortunately forces a bucket-based implementation. I don't know about Java.
- filoeleven 5y ago
  I don’t think this holds for persistent data structures that use HAMT. Those have great performance along with the benefits of immutability, and I’m perfectly okay with deferring order to a pretty-printer. It wouldn’t handle insertion order, probably best to do alphabetical by default then. Chrome dec tools does this for js objects (which are map-like) already, and I’ve never had complaints about it.
eximius 5y ago
note: it has been the default on python for some time, then made official (instead of an implementation detail) after some 3.x release. 3.7 maybe?
- chris_st 5y ago
  Turns out it's the default implementation in Ruby as of 2.7 or so as well.
  - majormajor 5y ago
    As of 1.9 :) https://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/ https://www.igvita.com/2009/02/04/ruby-19-internals-ordered-...
stickfigure 5y ago
Or you could look at it as "relaxed ordering is a performance optimization" and shouldn't be taken prematurely. In Java, there is no default; you ask for a HashMap or a LinkedHashMap explicitly. In dynamic languages like Python or JS I prefer default insertion ordered maps because if I wanted tightly optimized code, I wouldn't use those languages in the first place.
oweiler 5y ago
In Kotlin, calling mapOf() gives you a LinkedHashmap. Which is a weird choice IMHO.

by arsome 5y ago

ErikCorry 5y ago

The nice thing is the compact dictionary doesn't use extra memory, so why not make it the default?

tialaramex 5y ago
It may (perhaps, I can't tell) not use "extra memory" compared to the data structure they had before, but it definitely is using memory it wouldn't need if it didn't preserve order. Otherwise it would be more or less a violation of the pigeonhole principle. The insertion order is information, if you don't need to store that anywhere but you promise to give it back anyway that's a hole in your information theory.
- floitsch 5y ago
  With that reasoning a sorted list would need more memory than an unsorted list.
  - tialaramex 5y ago
    How so? Sorting changes the order of the list, to the extent it's adding information (the sort order) it's also destroying the same amount of information (the previous order). It's easy enough (including by accident) to deliver insertion ordered iterator behaviour for small hash maps that have never had any items removed, but after that things get sticky very quickly.
    - floitsch 5y ago
      You were stating that "[...] it definitely is using memory it wouldn't need if it didn't preserve order.". There is no reason for that. A sorted list doesn't need more memory than an unsorted list. And an insertion-sorted map doesn't need to use more memory than a map that doesn't keep the order. Independently, some properties we deem valuable are often side-products of the way the data-structure works. For example, an efficient binary search tree will naturally tend to be balanced. In the case of efficient hash maps, it is now common to add the key/value pair at the end of an internal vector. Maintaining the insertion order this way doesn't add any cost.
      - tialaramex 5y ago
        It actually does have a cost. In fact I'm pretty sure it has two separate types of cost, so let's talk about both of them. Firstly, and this is orthogonal to my original point, whenever people say "Cost" they actually silently mean "... that I care about" and so we're involuntarily obliged to agree to stop caring about anything else. Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections. But my main point is that the requirement for ordering forces you to dispose of otherwise permissible optimisations which could destroy the order. You actually ran head first into this in the article, when repeatedly removing and adding elements blows up by clogging your data structure with tombstones. Swiss Tables wouldn't clog up with tombstones. Since they don't care about ordering they only need tombstones at all in uncommon special cases (specifically, if the entire rest of the group is full or tombstones), in most cases Swiss Tables get to just set removed (key, value) pairs as empty. But this optimisation isn't open to you.
        joshuamorton 5y ago
        Sticking tombstones in the backing array doesn't actually cost you anything though. The backing array still needs to be the same size. Like maybe you end up having to re-hash more often? >Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections. Yes but this cost goes away if you commit to it, and the alternative (like what go does) to force the order to change all the time also comes with a complexity cost vs. doing "nothing" and having the order be arbitrary and sometimes, but not actually, reliable.
deathanatos 5y ago
It does, though. See the diagram in the article. There's two allocated arrays there: one for the real hash table (on top) and one for the "backing array" which then stores the actual items. The "extra" bit is the indexes in the top allocation: those indexes would be omitted in a normal (unsorted) hash map. (That is, a normal hash map allocates a single array, which is the storage for both the hash table and the items it contains.¹) (There's also some extra time requirements, too, to chase that additional pointer from the top table to the bottom one.) ¹N.b. in some languages those items will be references, but that doesn't matter for the comparison here.
- ErikCorry 5y ago
  Note that the bottom array can be densely packed, whereas the top one must have gaps to avoid excessive probing. If you only had one array you would have to put the gaps in that array, and it is at least 2 words per entry (much worse if you are inlining objects). So it's not so clear. If you want to save space you can also omit the hash bits stored in the index and reduce the width of the index entries to 16 or 8 bits on small maps. In practice the compact dict does very well on space. Much better than Java's unordered bucket-based HashMap for example. It's true that there's an extra pointer chase.
  - deathanatos 5y ago
    Ah, that's an excellent point, and it does muddle the water about which would win out. Deletes could still leave holes in the storage array, but I think I agree (and your article also states it) that the common case is likely fill table with data, and then perform lookups. (And I had thought bucket-based hashmaps had very much fallen out of favor to the point where they really weren't the choice of standard libraries anymore, precisely because of the additional allocations & pointer chasing they required? I'm not a Java person.)
    - pclmulqdq 5y ago
      C++ unordered_map unfortunately forces a bucket-based implementation. I don't know about Java.
filoeleven 5y ago
I don’t think this holds for persistent data structures that use HAMT. Those have great performance along with the benefits of immutability, and I’m perfectly okay with deferring order to a pretty-printer. It wouldn’t handle insertion order, probably best to do alphabetical by default then. Chrome dec tools does this for js objects (which are map-like) already, and I’ve never had complaints about it.

eximius 5y ago

note: it has been the default on python for some time, then made official (instead of an implementation detail) after some 3.x release. 3.7 maybe?

chris_st 5y ago
Turns out it's the default implementation in Ruby as of 2.7 or so as well.
- majormajor 5y ago
  As of 1.9 :) https://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/ https://www.igvita.com/2009/02/04/ruby-19-internals-ordered-...

stickfigure 5y ago

Or you could look at it as "relaxed ordering is a performance optimization" and shouldn't be taken prematurely. In Java, there is no default; you ask for a HashMap or a LinkedHashMap explicitly. In dynamic languages like Python or JS I prefer default insertion ordered maps because if I wanted tightly optimized code, I wouldn't use those languages in the first place.

oweiler 5y ago

In Kotlin, calling mapOf() gives you a LinkedHashmap. Which is a weird choice IMHO.