[Python-Dev] Guarantee ordered dict literals in v3.7?

Raymond Hettinger raymond.hettinger at gmail.com
Fri Dec 15 00:28:48 EST 2017

> On Dec 14, 2017, at 6:03 PM, INADA Naoki <songofacandy at gmail.com> wrote:
> If "dict keeps insertion order" is not language spec and we
> continue to recommend people to use OrderedDict to keep
> order, I want to optimize OrderedDict for creation/iteration
> and memory usage.  (See https://bugs.python.org/issue31265#msg301942 )

I support having regular dicts maintain insertion order but am opposed to Inada changing the implementation of collections.OrderedDict   We can have the first without having the second.

Over the holidays, I hope to have time to do further analysis and create convincing demonstrations of why we want to keep the doubly-linked list implementation for collections.OrderedDict().

The current regular dictionary is based on the design I proposed several years ago.  The primary goals of that design were compactness and faster iteration over the dense arrays of keys and values.   Maintaining order was an artifact rather than a design goal.  The design can maintain order but that is not its specialty.

In contrast, I gave collections.OrderedDict a different design (later coded in C by Eric Snow).  The primary goal was to have efficient maintenance of order even for severe workloads such at that imposed by the lru_cache which frequently alters order without touching the underlying dict.   Intentionally, the OrderedDict has a design that prioritizes ordering capabilities at the expense of additional memory overhead and a constant factor worse insertion time.

It is still my goal to have collections.OrderedDict have a different design with different performance characteristics than regular dicts.  It has some order specific methods that regular dicts don't have (such as a move_to_end() and a popitem() that pops efficiently from either end).  The OrderedDict needs to be good at those operations because that is what differentiates it from regular dicts.

The tracker issue https://bugs.python.org/issue31265 is assigned to me and I currently do not approve of it going forward.  The sentiment is nice but it undoes very intentional design decisions.  In the upcoming months, I will give it additional study and will be open minded but it is not cool to use a python-dev post as a way to do an end-run around my objections.

Back to the original topic of ordering, it is my feeling that it was inevitable that sooner or later we would guarantee ordering for regular dicts.  Once we had a performant implementation, the decision would be dominated by how convenient it is users.  Also, a single guarantee is simpler for everyone and is better than having a hodgepodge of rules stating that X and Y are guaranteed while Z is not.

I think an ordering guarantee for regular dicts would be a nice Christmas present for our users and developers.



More information about the Python-Dev mailing list