[chippiewill]

> In some communities the reaction would have been to write a good unordered dict which would obviously be even faster

Actually an ordered dictionary has improved performance over an unordered dictionary for the kinds of common Python workloads you encounter in the real world. The reason why is that the design is only incidentally ordered, the design arises from trying to improve memory efficiency and iteration speed. The dict ends up ordered because they stash the real k/v pairs in a regular array which is indexed by the hash table, populating the array is most efficient in insertion order. For pure "unordered map" type operations the newer implementation is actually a tiny bit slower.

[tialaramex]

The main thrust of your claim obviously can't be true and I'm not sure what confusion could lead you to believe that.

Maybe it's easier to see if we're explicit about what the rules are: OrderedDict (now the Python dict) is exactly the same features as a hypothetical UnorderedDict except OrderedDict has the additional constraint that if we iterate over it we get the key/values in the order in which they were inserted, while UnorderedDict can do as it pleases here.

This means OrderedDict is a valid implementation of UnorderedDict. So, necessarily OrderedDict does not have, as you claim, "improved performance over an unordered dictionary". At the very worst it's break even and performance is identical. This is why it's remarkable that Python's previous dict was worse.

But, that's a pretty degenerate case, we can also see that after deletion OrderedDict must use some resources ensuring the ordering constraint is kept. An UnorderedDict needn't do that, and we can definitely do better than OrdererDict.

[nemothekid]

>The main thrust of your claim obviously can't be true

It's surprising that iterating a dense array is faster than iterating a hashmap? I don't think you are parsing the parent post correctly.

If dictionaries are commonly iterated in python, then iterating an array of 100 items that fits in one cache-line will be faster than iterating a hashmap which might have 100 items in 100 cache lines.

[tialaramex]

The claim was that: "Actually an ordered dictionary has improved performance over an unordered dictionary"

Having a dense array is not, as it seems both you and chippiewill imagine, somehow a unique property of ordered dictionaries. An unordered dictionary is free to use exactly the same implementation detail.

The choice to preserve order is in addition to using dense arrays. The OrderedDict must use tombstones in order to preserve ordering, and then periodically rewrite the entire dense array to remove tombstones, while a hypothetical UnorderedDict needn't worry because it isn't trying to preserve ordering so it will be faster here despite also having the dense arrays.

"iterating an array of 100 items that fits in one cache-line will be faster"

On today's hardware a cache line is 64 bytes, so fitting 100 "items" (each 3x 64-bit values, so typically total 2400 bytes with today's Python implementation) in a cache line would not be possible. A rather less impressive "almost three" items fit in a cache line.

But to be sure the dense array is faster for this operation, the problem is that that's not an optimisation as a result of being ordered. It's just an implementation choice and the UnorderedDict is free to make the same choice.

[kalefranz]

Enjoy and appreciate the discussion. Is this in the same neighborhood of why the reworked dict implementation in python 3.6 had insertion order as a detail, but explicitly claimed it was not a feature that should be relied upon? At least until python 3.7 cemented the behavior as a feature.

[nerdponx]

The problem with Python here is that CPython is not only the reference implementation but the de-facto specification. So dicts are still "supposed to be" unordered collections, but now dicts must also preserve insertion order as per the docs and the reference implementation, so now all alternative implementations must also conform to this even if it doesn't make sense for them to conform to it, or they must specifically choose to be non-comformant on this point.

Of course in this case, the order-preserving optimization was actually first implemented by an alternative implementation (PyPY), but I don't think that changes the issue.

[lemagedurage]

Since Python 3.7 preservering insertion-order is part of the language specification.

"the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec."

https://docs.python.org/3/whatsnew/3.7.html

[nerdponx]

Right, but that's kind of my point. Adding it to the language spec now creates an additional and frankly somewhat unnecessary point of compliance for other implementations. Python is already so damn big and complicated, my opinion is that we shouldn't makes its spec even more complicated, even if its reference implementation adds more features like this.