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

Guido van Rossum guido at python.org
Mon Sep 12 13:04:18 EDT 2016

Wouldn't attempting to reuse DUMMY entries be expensive? You'd have to search forward in the array. Just keeping a count of DUMMY entries and compacting when there are too many seems better somehow.

On Mon, Sep 12, 2016 at 10:00 AM, Victor Stinner <victor.stinner at gmail.com> wrote:

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

-- --Guido van Rossum (python.org/~guido)

More information about the Python-Dev mailing list