Hacker News Reader

> Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container

I believe this misses quite an important bit of history. Python's dict retains key creation order since 3.6, and the behaviour was made official from 3.7 onwards. But before that, the keys were in unspecified order. Not random, because the order was stable: if you iterated through the same dict twice within the same process, you got the keys in the same order.

The property of retaining key creation order was a side effect from the underlying implementation. In the 3.6 release, Python switched over to their new dictionary implementation, lifted from the PyPy project. From what I recall, the reason for the change was that the new implementation had a notably lower per-key overhead. That decrease in memory use resulted, I believe, in the slightly faster performance as well. Order retention came "for free".

Personally I believe that order retention as a default property is a mistake. Now, I admit that OrderedDict semantics are often more convenient, but they break from the expected dict/map semantics with other languages. And since we are stating our opinions, in my mind Go choosing to forcibly randomise maps' key traversal order is a good safeguard. It guarantees that no-one can even accidentally depend on key iteration order. (Yes, I have seen production outages thanks to someone's code implicitly relying on key creation/traversal order when processing RESTful payloads.)

As should be apparent, I disagree with the current behaviour being "least surprising".

>(Yes, I have seen production outages thanks to someone's code implicitly relying on key creation/traversal order when processing RESTful payloads.)

Interesting. Example of that?

Sure. This is from the previous job. And for background: the service in question would routinely have several thousand concurrent, live user sessions. All stateful.

Two teams, let's call them Team A and team B, would have their respective services handling user traffic. Service maintained by Team A would handle the traffic, while service maintained by Team B would handle the more complex background state transitions that Team A would not have to care about during the day.

Service A would hold a complete client session state. Service B was stateless. Messages sent from service A to service B would contain all the necessary data to build up the correct state for every message received. Team A wrote their service in "not Python" language. Team B wrote theirs in Python. Communication between the services was RESTful, so essentially "JSON payload in a HTTP POST message".

Service B had a construction in their code that in simplified terms looked a bit like this:

    data = json.loads(msg.data)
    for key_, val_ in data.items():
        do_stuff(key_, val_)

And then inside the do_stuff() routine, there was a piece of logic that used an implicit state machine. It wasn't written like one, but it happened to rely on the processing order... Like this:

    def do_stuff(field, vals):
        if field in (<possible action triggers>):
             # do something based on field
        else:
             # other things

Because service B was written in Python, and this was post python 3.6 days, the 'data' read from the message created a dictionary with keys in the same order they happened to come off the wire. Everything worked fine, because the way the on-the-wire JSON payload at service A was constructed also happened to put field keys in a specific order. Service B could process the fields in the order they came through and could build a larger state internally based on each of the fields.

Then, as happens to every well used service, requirements change. In order to support new use cases, service A would need to include a new field - and for the maintainers of that service, the most logical place in their internal structure was between existing fields. This change was known, and service B had added support for this additional field. In 'do_stuff' internals, they had added the new field to the end of the possible action triggers. They also had unit tests - written by themselves - to ensure their service would work correctly whether it received old or new payloads.

The unit tests had added the new field after the existing fields in their test inputs. Their internal state machine was coherent and correct.

And then, Team A ships their new service. Service B promptly starts to crash. Every crash triggers Sentry client to serialise the full stack trace and send it over. In order to prevent a cascade failure, Sentry itself has been configured with a throttle, so once enough in-flight request are lined up, it starts to apply backpressure and response delays. Sentry clients within service B end up blocking their respective workers. Service A can not reliably send its message over, because service B is bogged down waiting for N+1 Sentry client submissions to complete. In order to capture the error situations properly, service A also has Sentry client within it...

It takes about 10 minutes for the teams to figure out what's going on before team A rolls back their deployment. But that was nonetheless visible downtime during live trading hours.

The root cause was obviously a logic bug, but it was only possible to build up to having such a logic bug due to the key iteration order semantics.

What a great example, thank you for writing it!

Not to take away from your broader point (that different data types are appropriate in different scenarios), but:

> Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough.

The python dict implementation is actually extremely optimized, and used in very critical hot paths throughout the interpreter and object model (for example, ``object.__dict__``). Additionally, python dicts (in cpython) are implemented in C, so any "slowness" there is going to be the result of the python code written to use the dictionary, and not the dict itself.

Up until python 3.6, cpython dictionaries were not ordered. At version 3.6, cpython dicts were made ordered, but only as an implementation detail. And at version 3.7, the preserves-insertion-order property of dicts was officially made part of the language spec, so that all python implementations need to support it.

The 3.6 change was made purely for performance reasons (and the stdlib already included an OrderedDict anyways). It was then made part of the language spec in 3.7 for several reasons: reduced maintenance burden for OrderedDict, convenience to developers using python, reducing the chance of accidental footguns of people relying on the implementation detail as if it were actually part of the language (and it then being removed later and breaking things), etc.

The decision was made as part of this thread[1], if you're curious.

[1] https://mail.python.org/pipermail/python-dev/2017-December/1...

> reduced maintenance burden for OrderedDict

The maintenance burden for ordered dict was not changed: ODict supports constant time moving to or removing from the start or end, so it has to be a linked hashmap, regardless of the ordering of the underlying map.

>The python dict implementation is actually extremely optimized, and used in very critical hot paths throughout the interpreter and object model (for example, ``object.__dict__``). Additionally, python dicts (in cpython) are implemented in C, so any "slowness" there is going to be the result of the python code written to use the dictionary, and not the dict itself.

Yes. Raymond Hettinger has one or more videos on YouTube titled something like "Python dictionaries" or "Modern Python dictionaries" that talk about the optimisations done on them.

> The python dict implementation is actually extremely optimized

It was upgraded from "optimized" terrible garbage to a sane attempt to do the same thing but smaller and faster. In the Python world I'm sure that's "extremely optimized". In the rest of the world we know it's not optimisation unless you measure and when you measure the Python dict is mediocre (but used to be much worse)

> used in very critical hot paths throughout the interpreter and object model

The old even worse one was used in the very same Python "critical hot paths" for many years.

Actually the earlier Python dict reminds me of "I can't believe it can sort" which is a weird sort algorithm which looks like it's a defective Insertion Sort that won't work, but is actually a working (but O(n*2) best case) sort algorithm. The old dict does in fact provide a hash table type for Python. It's much bigger than it needs to be, in order to enable an "optimization" which also makes it much slower than it needs to be.

> Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough.

That is completely incorrect. The builtin dict is similar to https://docs.rs/indexmap/latest/indexmap/ not a linked hashmap, it was used because it significantly improves iteration speed and uses less memory.

The crucial thing about IndexedMap is that it is not actually order preserving.

If it gets inconvenient to preserve order, it's just not preserved. For example if I put sixty items in, then remove thirty and add forty more, IndexedMap doesn't put all those forty items "after" the remaining thirty from the removal because that's more work.

Python does preserve order, the fact that internally it looks somewhat like IndexedMap is an implementation detail.

> the fact that internally it looks somewhat like IndexedMap is an implementation detail.

It really is not. IndexMap was directly inspired by Python’s naturally ordered dicts. It’s spelled out right in the readme.

And while indexmap has weaker ordering guarantees for performance reasons (though also additional features aplenty), “ordermap” was revived as a wrapper which does conserve ordering on removal.

The downside of something like indexmap is now removal is O(n)

If you do the remove naively yes, but you can use tombstoning which amortises the cost (at that of an increased iteration overhead), or using a non-order-preserving remove (like indexmap itself, though `remove` has been deprecated and you now get to pick your poison).

> This type is about the order of its contents by value.

No, by key.

I deserved that, maybe I should write up a whole blog post about this topic where I can include a diagram so that we're clear it's the value (as opposed to its age or any other characteristic) of the key

if you want your comments to make any sense, you need to use "key value" with every usage of "value", otherwise people are going to think "container value"