3 ms·

There are three distinct types being discussed here, let me try to briefly explain them. 1. Just a hash table, Rust's std::collections::HashMap, C++ std::unord

There are three distinct types being discussed here, let me try to briefly explain them. 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 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.

nbadg 2y ago
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/151263.html https://mail.python.org/pipermail/python-dev/2017-December/1...
- masklinn 2y ago
  > 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.
- fuzztester 2y ago
  >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.
- tialaramex 2y ago
  > 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.
masklinn 2y ago
> 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/ https://docs.rs/indexmap/latest/indexmap/ not a linked hashmap, it was used because it significantly improves iteration speed and uses less memory.
- tialaramex 2y ago
  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.
  - masklinn 2y ago
    > 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.
- assbuttbuttass 2y ago
  The downside of something like indexmap is now removal is O(n)
  - masklinn 2y ago
    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).
bostik 2y ago
> 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".
- fuzztester 2y ago
  >(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?
  - bostik 2y ago
    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.
38 2y ago
> This type is about the order of its contents by value. No, by key.
- tialaramex 2y ago
  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
  - 38 2y ago
    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"

nbadg 2y ago

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/151263.html https://mail.python.org/pipermail/python-dev/2017-December/1...

masklinn 2y ago
> 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.
fuzztester 2y ago
>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.
tialaramex 2y ago
> 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.

masklinn 2y ago

> 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/ https://docs.rs/indexmap/latest/indexmap/ not a linked hashmap, it was used because it significantly improves iteration speed and uses less memory.

tialaramex 2y ago
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.
- masklinn 2y ago
  > 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.
assbuttbuttass 2y ago
The downside of something like indexmap is now removal is O(n)
- masklinn 2y ago
  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).

bostik 2y ago

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

fuzztester 2y ago
>(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?
- bostik 2y ago
  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.

38 2y ago

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

tialaramex 2y ago
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
- 38 2y ago
  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"