4 ms·

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-

by 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.
  - cb321 6y ago
    What Python calls "list" other languages call "array" (or "vector" or "seq" or "dynarray" or ...). So, it is not at all "instead of arrays" as you said, but rather "arrays by another name". People usually say "linked list" or "singly linked list" or "doubly linked list" to refer to the idea/data structure that does pointer hopping during traversal.
    - arijun 6y ago
      Most languages don’t have dynamically resizing arrays, so IMHO vec is a better fit. But my point wasn’t about the name. It was that if you don’t want to incur the costs associated with automatic resizing or with the indirection in python lists (as they are built as arrays of pointers), you have to use a different, less convenient library, like array or numpy. And that’s ok, considering the language goals.

by arijun 6y ago

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.
- cb321 6y ago
  What Python calls "list" other languages call "array" (or "vector" or "seq" or "dynarray" or ...). So, it is not at all "instead of arrays" as you said, but rather "arrays by another name". People usually say "linked list" or "singly linked list" or "doubly linked list" to refer to the idea/data structure that does pointer hopping during traversal.
  - arijun 6y ago
    Most languages don’t have dynamically resizing arrays, so IMHO vec is a better fit. But my point wasn’t about the name. It was that if you don’t want to incur the costs associated with automatic resizing or with the indirection in python lists (as they are built as arrays of pointers), you have to use a different, less convenient library, like array or numpy. And that’s ok, considering the language goals.