I think what the author requires is iterating over a sorted list of keys. That is pretty easy to implement using the standard library, and imposes the performance penalty only when it is needed.
1. Just a hash table, Rust's std::collections::HashMap, C++ std::unordered_map, Go's map
This type is not about the "order" of its contents. If you want the "order" in any sense, that's not what this is for and you have the wrong type just as surely as if you were surprised that your integer type can't store a half. Types of this kind can be optimised to provide extremely fast indexing by key which is why they exist as this is useful in many problems.
2. A container arranged by the value of the keys, Rust's BTreeMap, C++ std::map
This type is about the order of its contents by value. It doesn't matter when you put a 4 into this container, it goes between 3 and 5 anyway. This type is good when you need to work in that "by value" order later, for example to take the "Most important" item or the "Soonest". It doesn't remember the order in which things were added, and it is relatively slow to find items by their key.
3. A container forever arranged by order of insertion, Python's OrderedDict (and dict), in Rust that's https://crates.io/crates/linked-hash-map LinkedHashMap
This type remembers the order in which you inserted items into the container and can give them all back in that order efficiently. In other ways it's like the first container, but it compromises performance significantly to deliver this "order" promise.
It is problematic that people talk past each other on this, both in terms of a useful discussion on HN, but much worse in a Software Engineerign team if you thought you were being given an OrderedDict, but it was actually a BTreeMap for example.
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.
> 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...
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.
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.
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.
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.
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.
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.
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".
Interesting. Example of that?
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_)
def do_stuff(field, vals):
if field in (<possible action triggers>):
# do something based on field
else:
# other things
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.
No, by key.
The author does not seem to require iterating over a sorted list. Sorting is not the same as ordering. An ordered map is a map in which the insertion order is preserved when iterating over the elements. A sorted map outputs the elements in an order defined by a comparison function when iterating, regardless of their insertion order. You can for example sort alphabetical in case of string keys.
It’s like having an unstable sort as the default standard library sort function. People reasonably expect that when calling sort twice the second sort to do nothing, but you can always find people who will passionately argue that people deserve to get burned if they assume a sort function is stable.
That's obviously not what the OP meant. Also, I don't think there's an efficient way of implementing deletes with an array backed linked list.
Good thing that's not what they are asking at all. They just want an ordered map to be in the standard library.
> That imposes an unnecessary performance overhead to support a small subset of use cases.
Naturally ordered hash maps generally have a small performance hit on lookup and a performance gain on iteration, as iteration goes through a dense array.
Linked hash maps do tend to have worse performances for all cases.
> I think what the author requires is iterating over a sorted list of keys.
Had they needed that, they'd have said that. But they did not. And they specifically refer to an ordered map, and to Python's built-in and Ordered dicts, which are not sorted.