[Python-Dev] Guarantee ordered dict literals in v3.7?

[Brett Cannon]

On Mon, 6 Nov 2017 at 08:36 Paul Sokolovsky <pmiscml at gmail.com> wrote:

> Hello,
>
> On Mon, 6 Nov 2017 14:30:45 +0100
> Antoine Pitrou <solipsis at pitrou.net> wrote:
>
> > On Tue, 7 Nov 2017 00:14:35 +1100
> > Steven D'Aprano <steve at pearwood.info> wrote:
> > > On Mon, Nov 06, 2017 at 12:27:54PM +0100, Antoine Pitrou wrote:
> > >
> > > > The ordered-ness of dicts could instead become one of those stable
> > > > CPython implementation details, such as the fact that resources
> > > > are cleaned up timely by reference counting, that people
> > > > nevertheless should not rely on if they're writing portable
> > > > code.
> > >
> > > Given that (according to others) none of IronPython, Jython,
> > > Batavia, Nuitka, or even MicroPython, should have trouble
> > > implementing an insertion-order preserving dict, and that PyPy
> > > already has, why should we say it is a CPython implementation
> > > detail?
> >
> > That's not what I'm taking away from Paul Sokolovsky's message I was
> > responding to.  If you think otherwise then please expand and/or
> > contact Paul so that things are made clearer one way or the other.
>
> For MicroPython, it would lead to quite an overhead to make
> dictionary items be in insertion order. As I mentioned, MicroPython
> optimizes for very low bookkeeping memory overhead, so lookups are
> effectively O(n), but orderedness will increase constant factor
> significantly, perhaps 5x.
>
> Also, arguably any algorithm which would *maintain* insertion order
> over mutating operations would be more complex and/or require more
> memory that one which doesn't. (This is based on the idea that
> this problem is equivalent to maintaining a sorted data structure, where
> sorting key is "insertion order").
>
> CPython 3.6 gives **kwargs in the key specification order? That's fine
> if that's all that it says (note that it doesn't say what happens if
> someone takes **kwargs and starts to "del []" or "[] =" it). That
> allows different ways to implement it, per particular implementation's
> choice. That's even implementable in MicroPython. Like, lookups will be
> less efficient, but nobody realistically passes hundreds of kwargs.
>
> It's pretty different to go from that to dictionaries in general.
>
> Saying that a general dict always maintains insertion order is saying
> that "in Python, you have to use complex, memory hungry algorithms for
> a simple mapping type".
>

But that's an implementation detail that most folks won't care about.


>
> Saying something like "dict maintains insertion order until first
> modification" is going down the rabbit hole, making it all confusing,
> hard to remember, crazy-sounding to novices.
>
>
> Why all that, if, since the beginning of times, Python offered a
> structure with guaranteed ordering - list, and structure for efficient
> mapping one values into other - dict. Then even marriage between the
> two - OrderedDict.
>
> Why suddenly once in 25 years there's a need to do something to dict's,
> violating computer science background behind them (one of the reason
> enough people loved Python comparing to other "practical hack"
> languages)?
>

I don't understand what "computer science background" is being violated?


>
> Alternatives were already presented on the thread - if people want more
> and easier ordered dictionaries, it calls to add a special literal
> initializer for them ("o{}" was proposed).
>

I don't see that happening. If OrderedDict didn't lead to syntax then I
don't see why that's necessary now.

I think worrying about future optimizations that order preservation might
prevent is a premature optimization/red herring. None of us can predict the
future so worrying about some algorithmic breakthrough that will suddenly
materialize on how to implement dictionaries seems unnecessary. That line
of thought suggests we should guarantee as little as possible and just make
most stuff undefined behaviour.

I also think Paul S. has made it clear that MicroPython won't be
implementing order-preserving dicts due to their memory constraints. That's
fine, but I think we also need to realize that MicroPython is already a
slight hybrid by being based on Python 3.4 but with a backport of
async/await and a subset of the stdlib.

>From what I have read, this argument breaks down to this:

Standardizing order preserving and ...

   - MicroPython won't implement it, but all other major implementations
   will
   - Those that have order preservation will implement PEPs 468 and 520 for
   free
   - Some minor practical benefits in terms of avoiding accidental reliance
   on ordering

If we don't promise order preservation ...

   - CPython should probably add some perturbing to the iteration order
   - All implementations can handle this without issue or major
   implementation costs


So to me this sounds like a decision between the pragmatism of choosing
semantics that all Python implementations can handle or the developer
benefits of an order-preserving dict everywhere (all the other arguments I
think are minor compared to these two).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20171106/772afac7/attachment.html>