16 ms·

I bet it's an artifact of Go having a randomized iteration order over maps [0]. Getting a deterministic ordering requires extra work. [0] https://stackoverflow

I bet it's an artifact of Go having a randomized iteration order over maps [0]. Getting a deterministic ordering requires extra work. [0] https://stackoverflow.com/questions/9619479/go-what-determines-the-iteration-order-for-map-keys https://stackoverflow.com/questions/9619479/go-what-determin...

simonw 4y ago
I used to have the exact same problem with Python, until Python 3.7 made maintaining sort order a feature of the language: https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/ https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/
- 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.
  - 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{..}
- hoppla 4y ago
  This burnt me when I wrote an algorithm. I depended on the order of keys in dicts as it allowed me reference the value both by index and key. I wrote the code in python 3.7+, and ended up spending a good amount of time debugging it when I ran it in a earlier python version.
deleted 4y ago
[deleted]
vips7L 4y ago
Does Go not have more than one Map implementation in the standard library?
- deleted 4y ago
  [deleted]
- esprehn 4y ago
  It does not. Maps are not even a real interface you can implement, it's compiler magic encoded in the language spec: https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics https://dave.cheney.net/2018/05/29/how-the-go-runtime-implem... This is all fallout of not having generics.
  - xmonkee 4y ago
    I fucking hate this so much. Honestly Go isn't a bad language, but I dunno why these kind of things just piss me off.
    - hxtk 4y ago
      It seems as though a lot of people view it as hypocritical, e.g., generics for me but not for thee (dated example since there are now generics for everyone). The fact that they needed to make a map a part of the language in order to allow it to be generic and statically-typed proves that generics are useful and should therefore have been a language feature much earlier than they became one. There are a variety of things that the standard library or compiler deal with using weird workarounds that seem to indicate missing language features. The thing is, the features are only "missing" if the language is designed to do the things those features permit. So the counterargument is that Go is a very opinionated language designed to do solve a few classes of problem very easily, like writing database-backed web services, and the reason the standard library or compiler teams have to do weird hacks at times is because Go wasn't made for writing those things, and designing to make those use cases easy would pollute the language from the perspective of someone using it for its intended purpose.
Someone 4y ago
No, it isn’t. “gojq does not keep the order of object keys” isn’t about ordering keys consistently across runs, it’s about keeping them in the order of the input file.
- akpa1 4y ago
  Which it can't do because, as mentioned, Go randomly iterates over maps. That's the data structure that most would use to load arbitrary input files into the program.
  - Someone 4y ago
    If you have a hammer in your toolbox, it doesn’t mean you have to use it in every job. It golangs maps don’t do what you want, pick a different data structure. This is like claiming that, because updating native integers isn’t guaranteed to be atomic in a language, you can’t do multi-threaded programming.
- rfiat 4y ago
  GP is correct, per the README: > gojq does not keep the order of object keys. I understand this might cause problems for some scripts but basically, we should not rely on the order of object keys. Due to this limitation, gojq does not have keys_unsorted function and --sort-keys (-S) option. I would implement when ordered map is implemented in the standard library of Go but I'm less motivated. And later in the same file: gojq does not support some functions intentionally; <snip> --sort-keys, -S (sorts by default because map[string]interface{} does not keep the order),
  - Someone 4y ago
    No, they aren’t. haasted replied to simonw’s > "gojq does not keep the order of object keys" is a bit disappointing with > “I bet it's an artifact of Go having a randomized iteration order over maps. Getting a deterministic ordering requires extra work.” But deterministic iteration order doesn’t imply that the order of keys is kept the same. There are map implementations that keep iteration follow insertion order, but the canonical map does not guarantee that. https://en.wikipedia.org/wiki/Associative_array#Hash_table_implementations https://en.wikipedia.org/wiki/Associative_array#Hash_table_i...: “The most frequently used general purpose implementation of an associative array is with a hash table: an array combined with a hash function that separates each key into a separate "bucket" of the array“ Such implementations iterate over maps in order of hash value (and hash collisions may or may not follow (reverse) insertion order)

simonw 4y ago

I used to have the exact same problem with Python, until Python 3.7 made maintaining sort order a feature of the language: https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/ https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/

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.
- 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{..}
hoppla 4y ago
This burnt me when I wrote an algorithm. I depended on the order of keys in dicts as it allowed me reference the value both by index and key. I wrote the code in python 3.7+, and ended up spending a good amount of time debugging it when I ran it in a earlier python version.

deleted 4y ago

[deleted]

vips7L 4y ago

Does Go not have more than one Map implementation in the standard library?

deleted 4y ago
[deleted]
esprehn 4y ago
It does not. Maps are not even a real interface you can implement, it's compiler magic encoded in the language spec: https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics https://dave.cheney.net/2018/05/29/how-the-go-runtime-implem... This is all fallout of not having generics.
- xmonkee 4y ago
  I fucking hate this so much. Honestly Go isn't a bad language, but I dunno why these kind of things just piss me off.
  - hxtk 4y ago
    It seems as though a lot of people view it as hypocritical, e.g., generics for me but not for thee (dated example since there are now generics for everyone). The fact that they needed to make a map a part of the language in order to allow it to be generic and statically-typed proves that generics are useful and should therefore have been a language feature much earlier than they became one. There are a variety of things that the standard library or compiler deal with using weird workarounds that seem to indicate missing language features. The thing is, the features are only "missing" if the language is designed to do the things those features permit. So the counterargument is that Go is a very opinionated language designed to do solve a few classes of problem very easily, like writing database-backed web services, and the reason the standard library or compiler teams have to do weird hacks at times is because Go wasn't made for writing those things, and designing to make those use cases easy would pollute the language from the perspective of someone using it for its intended purpose.

Someone 4y ago

No, it isn’t. “gojq does not keep the order of object keys” isn’t about ordering keys consistently across runs, it’s about keeping them in the order of the input file.

akpa1 4y ago
Which it can't do because, as mentioned, Go randomly iterates over maps. That's the data structure that most would use to load arbitrary input files into the program.
- Someone 4y ago
  If you have a hammer in your toolbox, it doesn’t mean you have to use it in every job. It golangs maps don’t do what you want, pick a different data structure. This is like claiming that, because updating native integers isn’t guaranteed to be atomic in a language, you can’t do multi-threaded programming.
rfiat 4y ago
GP is correct, per the README: > gojq does not keep the order of object keys. I understand this might cause problems for some scripts but basically, we should not rely on the order of object keys. Due to this limitation, gojq does not have keys_unsorted function and --sort-keys (-S) option. I would implement when ordered map is implemented in the standard library of Go but I'm less motivated. And later in the same file: gojq does not support some functions intentionally; <snip> --sort-keys, -S (sorts by default because map[string]interface{} does not keep the order),
- Someone 4y ago
  No, they aren’t. haasted replied to simonw’s > "gojq does not keep the order of object keys" is a bit disappointing with > “I bet it's an artifact of Go having a randomized iteration order over maps. Getting a deterministic ordering requires extra work.” But deterministic iteration order doesn’t imply that the order of keys is kept the same. There are map implementations that keep iteration follow insertion order, but the canonical map does not guarantee that. https://en.wikipedia.org/wiki/Associative_array#Hash_table_implementations https://en.wikipedia.org/wiki/Associative_array#Hash_table_i...: “The most frequently used general purpose implementation of an associative array is with a hash table: an array combined with a hash function that separates each key into a separate "bucket" of the array“ Such implementations iterate over maps in order of hash value (and hash collisions may or may not follow (reverse) insertion order)