> On Dec 15, 2017, at 1:47 PM, Guido van Rossum <guido@python.org> wrote:
>
> On Fri, Dec 15, 2017 at 12:45 PM, Raymond Hettinger <raymond.hettinger@gmail.com> wrote:
>
> > On Dec 15, 2017, at 7:53 AM, Guido van Rossum <guido@python.org> wrote:
> >
> > Make it so. "Dict keeps insertion order" is the ruling.
>
> On Twitter, someone raised an interesting question.
>
> Is the guarantee just for 3.7 and later?  Or will the blessing also cover 3.6 where it is already true.
>
> The 3.6 guidance is to use OrderedDict() when ordering is required.  As of now, that guidance seems superfluous and may no longer be a sensible practice.  For example, it would be nice for Eric Smith when he does his 3.6 dataclasses backport to not have to put OrderedDict back in the code.
>
> For 3.6 we can't change the language specs, we can just document how it works in CPython. I don't know what other Python implementations do in their version that's supposed to be compatible with 3.6 but I don't want to retroactively declare them non-conforming. (However for 3.7 they have to follow suit.) I also don't think that the "it stays ordered across deletions" part of the ruling is true in CPython 3.6.

FWIW, the regular dict does stay ordered across deletions in CPython3.6:

    >>> d = dict(a=1, b=2, c=3, d=4)
    >>> del d['b']
    >>> d['b'] = 5
    >>> d
    {'a': 1, 'c': 3, 'd': 4, 'b': 5}

Here's are more interesting demonstration:

    from random import randrange, shuffle
    from collections import OrderedDict

    population = 1000000
    s = list(range(population // 4))
    shuffle(s)
    d = dict.fromkeys(s)
    od = OrderedDict.fromkeys(s)
    for i in range(500000):
        k = randrange(population)
        d[k] = i
        od[k] = i
        k = randrange(population)
        if k in d:
            del d[k]
            del od[k]
    assert list(d.items()) == list(od.items())

The dict object insertion logic just appends to the arrays of keys, values, and hashvalues.  When the number of usable elements decreases to zero (reaching the limit of the most recent array allocation), the dict is resized (compacted) left-to-right so that order is preserved.

Here are some of the relevant sections from the 3.6 source tree:

Objects/dictobject.c line 89:

    Preserving insertion order

    It's simple for combined table.  Since dk_entries is mostly append only, we can
    get insertion order by just iterating dk_entries.

    One exception is .popitem().  It removes last item in dk_entries and decrement
    dk_nentries to achieve amortized O(1).  Since there are DKIX_DUMMY remains in
    dk_indices, we can't increment dk_usable even though dk_nentries is
    decremented.

    In split table, inserting into pending entry is allowed only for dk_entries[ix]
    where ix == mp->ma_used. Inserting into other index and deleting item cause
    converting the dict to the combined table.

Objects/dictobject.c::insertdict() line 1140:

        if (mp->ma_keys->dk_usable <= 0) {
            /* Need to resize. */
            if (insertion_resize(mp) < 0) {
                Py_DECREF(value);
                return -1;
            }
            hashpos = find_empty_slot(mp->ma_keys, key, hash);
        }

Objects/dictobject.c::dictresize() line 1282:

            PyDictKeyEntry *ep = oldentries;
            for (Py_ssize_t i = 0; i < numentries; i++) {
                while (ep->me_value == NULL)
                    ep++;
                newentries[i] = *ep++;
            }

>
> I don't know what guidance to give Eric, because I don't know what other implementations do nor whether Eric cares about being compatible with those. IIUC micropython does not guarantee this currently, but I don't know if they claim Python 3.6 compatibility -- in fact I can't find any document that specifies the Python version they're compatible with more precisely than "Python 3".


I did a little research and here' what I found:

"MicroPython aims to implement the Python 3.4 standard (with selected features from later versions)"
-- http://docs.micropython.org/en/latest/pyboard/reference/index.html

"PyPy is a fast, compliant alternative implementation of the Python language (2.7.13 and 3.5.3)."
-- http://pypy.org/

"Jython 2.7.0 Final Released (May 2015)"
-- http://www.jython.org/

"IronPython 2.7.7 released on 2016-12-07"
-- http://ironpython.net/

So, it looks like your could say 3.6 does whatever CPython 3.6 already does and not worry about leaving other implementations behind.  (And PyPy is actually ahead of us here, having compact and order-preserving dicts for quite a while).

Cheers,


Raymond