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

[Guido van Rossum]

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)