Hacker News Reader

Comment by paulhodge | Hacker News Reader

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 it worked on one OS and not the other), one of the most common causes was code that relied on a certain key order. And we knew that relying on key order was bad, we're supposed to use things like OrderedDict, blah blah blah. It was still a really easy mistake to make, just like it's really easy to have memory safety bugs in C.

At some point, if a human error is common enough, it makes pragmatic sense to change the design so the error is impossible.

View on HN

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.

But you can also just create them with named arguments, like this:

    collections.OrderedDict(y = "first", x = "second")

kwarg order wasn't guaranteed either until Python 3.6.

This also wasn't guaranteed to work since kwargs is a dict under the hood.

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).

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...

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

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/3be4d95731a17073afb1f69b...

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.

> 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.

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.)

It’s kind of annoying, but does catch an easily missed novice mistake.

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 (^^)

In case anyone else is curious: https://github.com/golang/go/issues/6719

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-effecti...)

If I read 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)

The hash value order and insertion order are unrelated.

> 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.

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.

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?

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

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.

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.

The Perl example sounds like someone incorrectly assuming that the output from `keys` be ordered, when it's explicitely not:

> Hash entries are returned in an apparently random order. The actual random order is specific to a given hash; the exact same series of operations on two hashes may result in a different order for each hash.

Applying a `sort` to the output of `keys` is second nature to me - I'm always aware that hash entries are unordered in Perl.

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.

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.

Reply on news.ycombinator.com