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

[Guido van Rossum]

Thanks Victor for the review and commit, and thanks Naoki for your
truly amazing implementation work!!

I've also accepted Eric's PEP 468.

IIUC there's one small thing we might still want to change somewhere
after 3.6b1 but before 3.6rc1: the order is not preserved when you
delete some keys and then add some other keys. Apparently PyPy has
come up with a clever solution for this, and we should probably adopt
it, but it's probably best not to hurry that for 3.6b1.

--Guido

On Thu, Sep 8, 2016 at 1:22 PM, Victor Stinner <victor.stinner at gmail.com> wrote:
> Hi,
>
> 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:
>
> Python 3.5.1 (default, Jun 20 2016, 14:48:22)
>>>> def func(**kw): print(kw.keys())
> ...
>>>> func(a=1, b=2, c=3, d=4, e=5)
> dict_keys(['c', 'd', 'e', 'b', 'a'])   # random order
>
> vs
>
> Python 3.6.0a4+ (default:d43f819caea7, Sep  8 2016, 13:05:34)
>>>> def func(**kw): print(kw.keys())
> ...
>>>> func(a=1, b=2, c=3, d=4, e=5)
> dict_keys(['a', 'b', 'c', 'd', 'e'])   # expected order
>
>
> It means that the main goal of the PEP 468 "Preserving the order of
> **kwargs in a function" is now implemented in Python 3.6:
> https://www.python.org/dev/peps/pep-0468/
>
> But Eric Snow still wants to rephrase the PEP 468 to replace
> "OrderedDict" with "ordered mapping".
>
>
> For more information on compact dict, see:
>
> * http://bugs.python.org/issue27350
> * https://mail.python.org/pipermail/python-dev/2016-June/145299.html
> * https://morepypy.blogspot.jp/2015/01/faster-more-memory-efficient-and-more.html
> *https://mail.python.org/pipermail/python-dev/2012-December/123028.html
>
>
> PyPy also implements the "compact dict", but it uses further "tricks"
> to preserve the order even if items are removed and then others are
> added. We might also implement these tricks in CPython, so dict will
> be ordered as well!
>
> --
>
> Moreover, since Guido approved the PEP 509 "Add a private version to
> dict", I just pushed the implementation.
>
> The PEP 509 provides a C API (a dict version field) to implement
> efficient caches on namespaces. It might be used to implement a cache
> on builtins in Python 3.6 using Yury's opcode cache (stay tuned!).
>
> Victor
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> https://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: https://mail.python.org/mailman/options/python-dev/guido%40python.org



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