[Python-Dev] Guarantee ordered dict literals in v3.7?
Guido van Rossum
guido at python.org
Fri Dec 15 19:51:59 EST 2017
Cool, thanks! I'm curious why this was brought up at all then...
On Dec 15, 2017 3:36 PM, "Raymond Hettinger" <raymond.hettinger at gmail.com>
wrote:
>
>
> > On Dec 15, 2017, at 1:47 PM, Guido van Rossum <guido at python.org> wrote:
> >
> > On Fri, Dec 15, 2017 at 12:45 PM, Raymond Hettinger <
> raymond.hettinger at gmail.com> wrote:
> >
> > > On Dec 15, 2017, at 7:53 AM, Guido van Rossum <guido at 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20171215/9cc8e849/attachment.html>
More information about the Python-Dev
mailing list