5 ms·

Go actually went in the other direction for a bunch of reasons (e.g. hash collision dos) and made key order quasi-random when iterating. Small maps used to main

by c2h5oh 4y ago

Go actually went in the other direction for a bunch of reasons (e.g. hash collision dos) and made key order quasi-random when iterating. Small maps used to maintain order, but a change was made to randomize that so people didn't rely on that and get stung when their maps got larger: https://github.com/golang/go/issues/6719 https://github.com/golang/go/issues/6719

tialaramex 4y ago
Right, the startling thing about Python's previous dict was that it was so terrible that the ordered dict was actually significantly faster. It's like if you did such a bad job making a drag racer that the street legal model of the same car was substantially faster over a quarter mile despite also having much better handling and reliability. In some communities the reaction would have been to write a good unordered dict which would obviously be even faster, but since nobody is exactly looking for the best possible performance from Python, they decided that ordered behaviour was worth the price, and it's not as though existing Python programmers could complain since it was faster than what they'd been tolerating previously. Randomizing is the other choice if you actually want your maps to be fast and want to resist Hyrum's law, but see the absl experience - they initially didn't bother to randomize tiny maps but then the order of those tiny maps changed for technical reasons and... stuff broke. Because hey, in testing I made six of this tiny map, they always had the same order therefore (ignoring the documentation imploring me not to) I shall assume the order is always the same...
- alecthomas 4y ago
  > Right, the startling thing about Python's previous dict was that it was so terrible that the ordered dict was actually significantly faster. I've never heard that before and it would be really surprising, given that Python's builtin dict is used for everything from local symbol to object field lookup. Do you have more information?
  - aaronbee 4y ago
    Here’s a description of the new map implementation and why it’s more efficient: https://www.pypy.org/posts/2015/01/faster-more-memory-efficient-and-more-4096950404745375390.html https://www.pypy.org/posts/2015/01/faster-more-memory-effici...
    - adgjlsfhk1 4y ago
      Note that this applies more for python than efficient languages. In python, objects are big, and require an indirection. In faster languages, many objects can be smaller than a pointer and stored inline. As such, dictionaries that have vectorized lookups generally can be made faster.
- chippiewill 4y ago
  > In some communities the reaction would have been to write a good unordered dict which would obviously be even faster Actually an ordered dictionary has improved performance over an unordered dictionary for the kinds of common Python workloads you encounter in the real world. The reason why is that the design is only incidentally ordered, the design arises from trying to improve memory efficiency and iteration speed. The dict ends up ordered because they stash the real k/v pairs in a regular array which is indexed by the hash table, populating the array is most efficient in insertion order. For pure "unordered map" type operations the newer implementation is actually a tiny bit slower.
  - tialaramex 4y ago
    The main thrust of your claim obviously can't be true and I'm not sure what confusion could lead you to believe that. Maybe it's easier to see if we're explicit about what the rules are: OrderedDict (now the Python dict) is exactly the same features as a hypothetical UnorderedDict except OrderedDict has the additional constraint that if we iterate over it we get the key/values in the order in which they were inserted, while UnorderedDict can do as it pleases here. This means OrderedDict is a valid implementation of UnorderedDict. So, necessarily OrderedDict does not have, as you claim, "improved performance over an unordered dictionary". At the very worst it's break even and performance is identical. This is why it's remarkable that Python's previous dict was worse. But, that's a pretty degenerate case, we can also see that after deletion OrderedDict must use some resources ensuring the ordering constraint is kept. An UnorderedDict needn't do that, and we can definitely do better than OrdererDict.
    - nemothekid 4y ago
      >The main thrust of your claim obviously can't be true It's surprising that iterating a dense array is faster than iterating a hashmap? I don't think you are parsing the parent post correctly. If dictionaries are commonly iterated in python, then iterating an array of 100 items that fits in one cache-line will be faster than iterating a hashmap which might have 100 items in 100 cache lines.
      - 4y ago
Groxx 4y ago
`select{..}` cases with multiple valid channel operations also select randomly. I really like it, it helps you discover (and fix) order-dependent logic WAY earlier. Though I would really like some way to influence how long it blocks before selecting one (to simulate high load scenarios, and trigger more logical races).
- gabereiser 4y ago
  you'll need an interrupt chan for that if you're in a select{..}

by c2h5oh 4y ago

tialaramex 4y ago

Right, the startling thing about Python's previous dict was that it was so terrible that the ordered dict was actually significantly faster. It's like if you did such a bad job making a drag racer that the street legal model of the same car was substantially faster over a quarter mile despite also having much better handling and reliability. In some communities the reaction would have been to write a good unordered dict which would obviously be even faster, but since nobody is exactly looking for the best possible performance from Python, they decided that ordered behaviour was worth the price, and it's not as though existing Python programmers could complain since it was faster than what they'd been tolerating previously. Randomizing is the other choice if you actually want your maps to be fast and want to resist Hyrum's law, but see the absl experience - they initially didn't bother to randomize tiny maps but then the order of those tiny maps changed for technical reasons and... stuff broke. Because hey, in testing I made six of this tiny map, they always had the same order therefore (ignoring the documentation imploring me not to) I shall assume the order is always the same...

alecthomas 4y ago
> Right, the startling thing about Python's previous dict was that it was so terrible that the ordered dict was actually significantly faster. I've never heard that before and it would be really surprising, given that Python's builtin dict is used for everything from local symbol to object field lookup. Do you have more information?
- aaronbee 4y ago
  Here’s a description of the new map implementation and why it’s more efficient: https://www.pypy.org/posts/2015/01/faster-more-memory-efficient-and-more-4096950404745375390.html https://www.pypy.org/posts/2015/01/faster-more-memory-effici...
  - adgjlsfhk1 4y ago
    Note that this applies more for python than efficient languages. In python, objects are big, and require an indirection. In faster languages, many objects can be smaller than a pointer and stored inline. As such, dictionaries that have vectorized lookups generally can be made faster.
chippiewill 4y ago
> In some communities the reaction would have been to write a good unordered dict which would obviously be even faster Actually an ordered dictionary has improved performance over an unordered dictionary for the kinds of common Python workloads you encounter in the real world. The reason why is that the design is only incidentally ordered, the design arises from trying to improve memory efficiency and iteration speed. The dict ends up ordered because they stash the real k/v pairs in a regular array which is indexed by the hash table, populating the array is most efficient in insertion order. For pure "unordered map" type operations the newer implementation is actually a tiny bit slower.
- tialaramex 4y ago
  The main thrust of your claim obviously can't be true and I'm not sure what confusion could lead you to believe that. Maybe it's easier to see if we're explicit about what the rules are: OrderedDict (now the Python dict) is exactly the same features as a hypothetical UnorderedDict except OrderedDict has the additional constraint that if we iterate over it we get the key/values in the order in which they were inserted, while UnorderedDict can do as it pleases here. This means OrderedDict is a valid implementation of UnorderedDict. So, necessarily OrderedDict does not have, as you claim, "improved performance over an unordered dictionary". At the very worst it's break even and performance is identical. This is why it's remarkable that Python's previous dict was worse. But, that's a pretty degenerate case, we can also see that after deletion OrderedDict must use some resources ensuring the ordering constraint is kept. An UnorderedDict needn't do that, and we can definitely do better than OrdererDict.
  - nemothekid 4y ago
    >The main thrust of your claim obviously can't be true It's surprising that iterating a dense array is faster than iterating a hashmap? I don't think you are parsing the parent post correctly. If dictionaries are commonly iterated in python, then iterating an array of 100 items that fits in one cache-line will be faster than iterating a hashmap which might have 100 items in 100 cache lines.
    - 4y ago

Groxx 4y ago

`select{..}` cases with multiple valid channel operations also select randomly. I really like it, it helps you discover (and fix) order-dependent logic WAY earlier. Though I would really like some way to influence how long it blocks before selecting one (to simulate high load scenarios, and trigger more logical races).

gabereiser 4y ago
you'll need an interrupt chan for that if you're in a select{..}