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

Serhiy Storchaka storchaka at gmail.com
Thu Sep 15 02:31:54 EDT 2016

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.

More information about the Python-Dev mailing list