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

[Serhiy Storchaka]

On 08.09.16 23:22, Victor Stinner wrote:
> I pushed INADA Naoki's implementation of the "compact dict". The hash
> table now stores indices pointing to a new second table which contains
> keys and values: it adds one new level of indirection. The table of
> indices is "compact": use 1, 2, 4 or 8 bytes per indice depending on
> the size of the dictionary. Moreover, the keys/values table is also
> more compact: its size is 2/3 of the indices table.
>
> A nice "side effect" of compact dict is that the dictionary now
> preserves the insertion order. It means that keyword arguments can now
> be iterated by their creation order:

Note that this is made at the expense of the 20% slowing down an iteration.

$ ./python -m timeit -s "d = dict.fromkeys(range(10**6))" -- "list(d)"
Python 3.5: 66.1 msec per loop
Python 3.6: 82.5 msec per loop

Fortunately the cost of the lookup (the most critical operation for 
dicts) seems left the same.

But this can be an argument against using this technique in sets.