6 ms·

Why is it useful for maps to be sorted by insertion order?

by anonymoushn 6y ago

lightgreen 6y ago
It makes execution reproducible.
- anonymoushn 6y ago
  Almost any hash table implementation will give the same iteration order for the same sequence of insertions and deletions across program executions. So this would already be true even if the order was not the insertion order. Golang starts iterations in a random position each run to prevent people from relying on the ordering.
  - lightgreen 6y ago
    Not “almost any”. Good hashtables intentionally mix random numbers into hashes to prevent DOS attacks. And also, even if hashtables are stable, the hashes of the objects might not be (depend on the addresses for example).
  - arnvald 6y ago
    I think Go does it very well here (since they don't want to guarantee the order) - getting consistent order in almost every case is the worst of both worlds, because people won't learn about the underlying implementation, they'll notice that it seems ordered and will rely on this behaviour.
    - anonymoushn 6y ago
      As lightgreen points out in a sibling comment, it's common recently for languages to use a secure randomized hash like siphash and generate different orderings per program execution. It seems like that's the approach more languages should take.
jarym 6y ago
I guess if you want a pseudo map/list where ordering matters? But truth is semantics of a 'map' have no implicit ordering (at least mathematically). The fact some languages offer this as a convenience is great but its hardly fair to complain about languages that do not.
lightgreen 6y ago
However the author did not mention stable order does not come for free. It is not a trivial decision to make, between ordered and unordered dicts.
- arijun 6y ago
  Actually in this case I believe it did come for free due to a change in the way dict was implemented in 3.6: https://mail.python.org/pipermail/python-dev/2016-September/146327.html https://mail.python.org/pipermail/python-dev/2016-September/...
  - lightgreen 6y ago
    It is not as simple as that. It might looks "free" in this particular implementation, but it obviously prevents further optimizations.
    - cb321 6y ago
      To follow up on lightgreen's comment, in arijun's own linked-to URI they specifically mention the new level of indirection right away. Indirection is not "free" at all. For very large dict()s in main memory/DRAM it could be 2X slower. A hot loop benchmark where the CPU can perfectly predict its near future work and its prefetcher can mask DRAM latency may not reveal this, but a less "simple" benchmark would. The primary point of the ordering feature (and insertion ordering) is because Python uses that very same dict implementation for language features such as keyword args {def foo(\\kwargs)}. Changing to hash-order from "source code"-order can be confusing.
      - arijun 6y ago
        The reason for the change for more compact dicts. Thus the fact that it also preserved insertion order was a happy accident with no additional cost; what I called "free".
    - arijun 6y ago
      You're right. If a more efficient but unordered dict were to come out, it would have to be in an import and have less comfortable syntax, since the base dict has a requirement for preserving insert order. But python is not C, and speed is not the most important consideration. Python often goes for "efficient enough, and very comfortable to use", for example by using lists as its ordered flat container instead of arrays. I think that making dicts ordered is another step in the right direction for Python.
aasasd 6y ago
You can use the same structure to output data to the screen (or elsewhere) and to find stuff by the key.
- anonymoushn 6y ago
  In other words, I must pay the cost of maintaining the ordering even in the 99% of cases when it will not be used.
  - aasasd 6y ago
    Indeed, if you find e.g. PHP too slow, you can switch to Python for speed. To Python. For speed. Compared to PHP.
mehrdadn 6y ago
There are 2 questions here: 1. Why should it use a stable ordering at all? 2. Why should that ordering be the insertion order? #2 isn't a particularly deep question. It has at least one fairly obvious reason: because it's the most intuitive thing to iterate through items and get them back in the same order as you inserted them. Anything else would be less intuitive. #1, though, is more interesting, and it's one of those experience-based things that can be hard to see the significance of initially. One reason for it is that determinism & reproducibility is quite useful in a variety of use cases (e.g. testing), and while it's incredibly easy to lose, it's also quite hard (and often brittle) to gain back afterward (in the cases where it's even possible). By contrast, it's generally far easier to inject randomization at any point when you really need to (e.g. for security). Another reason can be that it reduces degrees of freedom in your program, which is generally a good thing as it helps when reasoning about program behavior. (This is not only during development, but also when debugging: it's incredibly useful to see what see what order items were inserted in to arrive at the current state.) There are probably more, but these are what I can think of off the top of my head. And finally, another overarching reason for both is simply the notion of "information loss" (basically, entropy): it's easy to lose information, but not so easy to get it back. And in some people's experience (including mine), it often pays off in the long run for clients of an API to go out of your way to minimize unnecessary information loss in your library. (That information in this case being the implicit ordering information.) Of course, all this hinges on the trade-off being worthwhile in each case. That's why library writers try to test different workloads to see if e.g. the performance trade-off is worth it. In CPython's case, it appeared it was.

Why is it useful for maps to be sorted by insertion order?

lightgreen 6y ago

It makes execution reproducible.

anonymoushn 6y ago
Almost any hash table implementation will give the same iteration order for the same sequence of insertions and deletions across program executions. So this would already be true even if the order was not the insertion order. Golang starts iterations in a random position each run to prevent people from relying on the ordering.
- lightgreen 6y ago
  Not “almost any”. Good hashtables intentionally mix random numbers into hashes to prevent DOS attacks. And also, even if hashtables are stable, the hashes of the objects might not be (depend on the addresses for example).
- arnvald 6y ago
  I think Go does it very well here (since they don't want to guarantee the order) - getting consistent order in almost every case is the worst of both worlds, because people won't learn about the underlying implementation, they'll notice that it seems ordered and will rely on this behaviour.
  - anonymoushn 6y ago
    As lightgreen points out in a sibling comment, it's common recently for languages to use a secure randomized hash like siphash and generate different orderings per program execution. It seems like that's the approach more languages should take.

jarym 6y ago

I guess if you want a pseudo map/list where ordering matters? But truth is semantics of a 'map' have no implicit ordering (at least mathematically). The fact some languages offer this as a convenience is great but its hardly fair to complain about languages that do not.

lightgreen 6y ago

However the author did not mention stable order does not come for free. It is not a trivial decision to make, between ordered and unordered dicts.

arijun 6y ago
Actually in this case I believe it did come for free due to a change in the way dict was implemented in 3.6: https://mail.python.org/pipermail/python-dev/2016-September/146327.html https://mail.python.org/pipermail/python-dev/2016-September/...
- lightgreen 6y ago
  It is not as simple as that. It might looks "free" in this particular implementation, but it obviously prevents further optimizations.
  - cb321 6y ago
    To follow up on lightgreen's comment, in arijun's own linked-to URI they specifically mention the new level of indirection right away. Indirection is not "free" at all. For very large dict()s in main memory/DRAM it could be 2X slower. A hot loop benchmark where the CPU can perfectly predict its near future work and its prefetcher can mask DRAM latency may not reveal this, but a less "simple" benchmark would. The primary point of the ordering feature (and insertion ordering) is because Python uses that very same dict implementation for language features such as keyword args {def foo(\\kwargs)}. Changing to hash-order from "source code"-order can be confusing.
    - arijun 6y ago
      The reason for the change for more compact dicts. Thus the fact that it also preserved insertion order was a happy accident with no additional cost; what I called "free".
  - arijun 6y ago
    You're right. If a more efficient but unordered dict were to come out, it would have to be in an import and have less comfortable syntax, since the base dict has a requirement for preserving insert order. But python is not C, and speed is not the most important consideration. Python often goes for "efficient enough, and very comfortable to use", for example by using lists as its ordered flat container instead of arrays. I think that making dicts ordered is another step in the right direction for Python.

aasasd 6y ago

You can use the same structure to output data to the screen (or elsewhere) and to find stuff by the key.

anonymoushn 6y ago
In other words, I must pay the cost of maintaining the ordering even in the 99% of cases when it will not be used.
- aasasd 6y ago
  Indeed, if you find e.g. PHP too slow, you can switch to Python for speed. To Python. For speed. Compared to PHP.

mehrdadn 6y ago

There are 2 questions here: 1. Why should it use a stable ordering at all? 2. Why should that ordering be the insertion order? #2 isn't a particularly deep question. It has at least one fairly obvious reason: because it's the most intuitive thing to iterate through items and get them back in the same order as you inserted them. Anything else would be less intuitive. #1, though, is more interesting, and it's one of those experience-based things that can be hard to see the significance of initially. One reason for it is that determinism & reproducibility is quite useful in a variety of use cases (e.g. testing), and while it's incredibly easy to lose, it's also quite hard (and often brittle) to gain back afterward (in the cases where it's even possible). By contrast, it's generally far easier to inject randomization at any point when you really need to (e.g. for security). Another reason can be that it reduces degrees of freedom in your program, which is generally a good thing as it helps when reasoning about program behavior. (This is not only during development, but also when debugging: it's incredibly useful to see what see what order items were inserted in to arrive at the current state.) There are probably more, but these are what I can think of off the top of my head. And finally, another overarching reason for both is simply the notion of "information loss" (basically, entropy): it's easy to lose information, but not so easy to get it back. And in some people's experience (including mine), it often pays off in the long run for clients of an API to go out of your way to minimize unnecessary information loss in your library. (That information in this case being the implicit ordering information.) Of course, all this hinges on the trade-off being worthwhile in each case. That's why library writers try to test different workloads to see if e.g. the performance trade-off is worth it. In CPython's case, it appeared it was.