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

[Paul Sokolovsky]

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".

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)?

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).


-- 
Best regards,
 Paul                          mailto:pmiscml at gmail.com