5 ms·

Great decision IMO. I remember maintaining a bunch of Python code that we supported on both OSX and Windows. Out of all the platform-specific bugs we had (where

• rob74 7y ago
  The Go designers went the other way (as they often do): > When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next. Actually it is not only "not guaranteed to be the same", the runtime actively makes sure that the iteration order is actually different so you don't even start to rely on it...
  • tele_ski 7y ago
    That seems like it would be a performance hit to actively make it different? That seems like a very weird and strange design decision if true
    • TheNorthman 7y ago
      It actually doesn't make that much of a difference. See this commit for actual benchmarks about the impact: https://github.com/golang/go/commit/3be4d95731a17073afb1f69bde264eecbdfa32bb https://github.com/golang/go/commit/3be4d95731a17073afb1f69b...
    • dallbee 7y ago
      It is a performance hit and I initially had the same reservations. Importantly, the implementation imposes a small overhead on the access time of iteration over a map, but not in a way which changes the scaling behavior. Other map operations are not implicated. I think the decision was wise - it prevents user code from relying on ordered iteration behavior, which allows the go team to switch to different map implementations without fear of breaking user code. If the order had been unspecified, but iteration was still ordered in practice, there'd undoubtedly be (incorrect) user code that relied on that behavior. Amusingly, I now run into engineers who are under the misconception that map iteration is random, and proceed to use maps as an RNG. That's an unfortunate mistake because Go's map iteration is quite non-uniform - it's shuffled just enough to appear random to the untrained eye, while be performant.
    • adev_ 7y ago
      > That seems like it would be a performance hit to actively make it different Not really. I don't know the go implementation but you can get this behaviour by adding an arbitrary "startup defined" seed to your hash function and that does the trick. It also gives the benefit of making hash table attacks harder.
    • jerf 7y ago
      It's a very small performance hit because it doesn't do the work to be uniformly random, just "not always the same". If you think about how you have to iterate through a hash table or similar data structure anyhow, it's either O(1) or O(log n) paid once per "range" on the data structure, which is dwarfed by the actual act of ranging on the data structure. Go's philosophy is also definitely willing to pay that price to avoid a large class of known bugs that has hit all kinds of code bases. It is not about being the fastest language. As compiled languages go, it's solidly middle-tier, and not likely to go up much from there. (Among the C-style compiled languages, it's low-tier on performance, at around half the speed of C in general. However there's enough compiled languages like Haskell that are still generally relatively slow so that Go is mid-tier for compiled languages over all.)
  • 3fe9a03ccd14ca5 7y ago
    It’s kind of annoying, but does catch an easily missed novice mistake.
  • mpfundstein 7y ago
    Ah i love go. While its mega cumbersome sometimes and lacks generics (WHY????) , i found that i write pretty stable code in it that still looks good after years (^^)
  • ivanfon 7y ago
    In case anyone else is curious: https://github.com/golang/go/issues/6719 https://github.com/golang/go/issues/6719
  • Someone 7y ago
    That’s fairly common, as it is protection against denial-of-service attacks that use hash collisions to make code perform poorly (https://events.ccc.de/2011/12/28/crypto-talk-at-28c3-effective-denial-of-service-attacks-against-web-application-platforms-day-2-1400-saal-1/ https://events.ccc.de/2011/12/28/crypto-talk-at-28c3-effecti...) If I read https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ correctly, Perl fixed that in 2003. C#, Java and Swift do it, too. As does (or, reading this, did?) Python (https://bugs.python.org/issue13703 https://bugs.python.org/issue13703)
    • jnwatson 7y ago
      The hash value order and insertion order are unrelated.
    • to11mtm 7y ago
      > C#, Java and Swift do it, too. Welllllllll In the case of C# it is/was more a matter of picking the -correct- Dictionary. 'OrderedDictionary' has been around since Net 2.0 (2005 or so,) as has 'SortedDictionary<TKey, TValue>' But for some ungodly reason, there is no 'OrderedDictionary<TKey,TValue>' included in the framework that you can use. All you get normally is the non-generic one (where you have to type-check everything...) There are internal implementations used by the framework, but you'd have to do some hacky things to even get it to work. However, in my 12 years of C# programming, I've only run into the need for this _once_, and it was to assist interfacing with a VB6 monstrosity.
  • masklinn 7y ago
    Python kinda sorta did the same from Python 3.3 to 3.5: iteration order was not actively randomised but the hash was "seeded" (for DDOS resistance) so iteration order would only be coherent within a run, which in effect made it unreliable. Python 3.6 changed the underlying implementation to one which incidentally made iteration order not rely on the hash function, and as that seemed like a useful property and one which risked causing compatibility issues with alternate implementation (developers would come to rely on cpython's iteration order and code would break on jython or whatever) they decided to make it part of the spec for 3.7.
• quietbritishjim 7y ago
  One particular annoyance of OrderedDict objects was initialising them with literals. You couldn't just do: od = OrderedDict({ "y": "first", "x": "second", }) because, by the time the data got to OrderedDict's constructor, it had already been through a dict. Instead you had to supply a list of lists (or tuple of tuples etc.): od = OrderedDict([ ("y", "first"), ("x", "second"), ]) For hierarchically nested dictionaries, these are quite a bit harder to read.
  • laGrenouille 7y ago
    But you can also just create them with named arguments, like this: collections.OrderedDict(y = "first", x = "second")
    • masklinn 7y ago
      kwarg order wasn't guaranteed either until Python 3.6.
    • gnulinux 7y ago
      This also wasn't guaranteed to work since kwargs is a dict under the hood.
      • masklinn 7y ago
        FWIW they could have used a special-purpose dict guaranteeing order for that. I don't know if they ended up using the normal dicts but the proposal to keep kwarg ordering predates the new dicts, and the PEP even notes that it's unclear the new dicts would be merged. Same with class attribute ordering, PEP 520 still talks about using OrderedDict, however it was only merged after the new dicts, and even if ordering was not defined at the time (as part of Python-the-language) PEP 520 could use this internal property just fine and the ordereddict-based version was stripped out, the PEP was essentially accepted as a no-op (the ordering properties would just be officially documented).
• drngdds 7y ago
  I haven't done a ton of Python, but I can't really think of a situation where relying on a dict to be ordered is an easy mistake to make. Do you have an example?
  • Strilanc 7y ago
    The most common situation I saw was where the entries from the dictionary were being iterated over and used to perform edits on a structure whose edits were nearly commutative. For example, suppose you have a dictionary containing PriorityItem values. PriorityItems are sorted by priority, while the value only matters for equality (affects __eq__ but not __lt__). If you have a dictionary whose values are PriorityItems and you say `sorted(dictionary.values())` the order of the output could vary w.r.t. equal priority items. So if you wrote a test asserting a process hiding a dictionary had a stable ordering of the items, it might consistently pass by accident on your machine and then fail elsewhere.
  • zwp 7y ago
    I saw this in Perl a long time ago but it could just as easily have happened in Python. The dict (Perl hash) was a set of mappings for template replacement of "from" strings to "to" strings. "FOO" => "bar" # Replace FOO with bar The author had considered the case where one key (FOO) might be a left-substring of another (FOOBAR), and so reversed the output from keys() before iterating over the hash. This ensured that FOOBAR, which sorts later, would be substituted before FOO (else FOOBAR -> barBAR, oops). Unfortunately, despite empirical evidence to the contrary at the time, keys() does not guarantee sort-order results https://perldoc.perl.org/functions/keys.html https://perldoc.perl.org/functions/keys.html This worked for a while (appeared to work?) and but was subsequently caught by another developer, who added a sort(). (Get a templating library alreay yeesh). Incidentally Ruby made the transition to sorted Hash some years ago (1.9 maybe?) and I don't remember any great fall-out.
    • jrochkind1 7y ago
      I definitely recall there being no fall out or or problems when ruby did it in I think 1.9. Semantically, I can't think of how there would be. Since previously order was unpredictable and not guaranteed, it could be anything at all; always using insertion order is, after all, one possible value of "anything at all". Only possible downside might be performance (or memory). I recall the ruby maintainers ensuring they had an implementation with very little if any performance/memory implication.
• paulddraper 7y ago
  Internally, Google modifies Java and Python (and Go was made this way and Chrome made JS this way) so that the dictionary traversal is deterministic.