[Python-Dev] Python 3.6 dict becomes compact and gets a private version; and keywords become ordered

[Victor Stinner]

2016-09-12 18:35 GMT+02:00 Guido van Rossum <guido at python.org>:
> Couldn't we use the order in the actual hash table (which IIUC now
> contains just indexes into the ordered vector of key/value/hash
> structs)? That would probably simulate the pre-3.6 order quite
> effectively.

>From what I understood, Python 3.6 dict got two *different* changes:

* modify the dict structure to use two tables instead of only one: an
"index" table (the hash table) and a second key/value table
* tune the dict implementation to only append to the key/value table

The second change depends on the first change.

When a key is deleted, the entry is marked as DUMMY. When we add a new
item, DUMMY entries are skipped and we only append at the end of the
key/value table. Sometimes, the key/value table is compacted to free
memory: all DUMMY entries are removed.

It would be possible to add a flag to allow to reuse DUMMY entries,
which means loosing the order. The order would only be lost when we
add the first item after we removed at least one entry (when the first
DUMMY entry is reused).

The OrderedDict would set the flag to preserve the order.

So technically, it is possible. The question is more what should be
the "default" dict :-) Ordered or not? :-)

Victor