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

[Steven D'Aprano]

On Mon, Nov 06, 2017 at 12:18:17PM +0200, Paul Sokolovsky wrote:

> > I don't think that situation should change the decision, 
> 
> Indeed, it shouldn't. What may change it is the simple and obvious fact
> that there's no need to change anything, as proven by the 25-year
> history of the language.

I disagree -- the history of Python shows that having dicts be unordered 
is a PITA for many Python programmers. Python eventually gained an 
ordered dict because it provides useful functionality that developers 
demand.

Every new generation of Python programmers comes along and gets confused 
by why dicts mysteriously change their order from how they were entered, 
why doctests involving dicts break, why keyword arguments lose their 
order, why they have to import a module to get ordered dicts instead of 
having it be built-in, etc. Historically, we had things like 
ConfigParser reordering ini files when you write them.

Having dicts be unordered is not a positive virtue, it is a limitation. 
Up until now, it was the price we've paid for having fast, O(1) dicts. 
Now we have a dict implementation which is fast, O(1) and ordered. Why 
pretend that we don't? This is a long-requested feature, and the cost 
appears to be small: by specifying this, all we do is rule out some, but 
not all, hypothetical future optimizations.

Unordered dicts served CPython well for 20+ years, but I doubt many 
people will miss them.


> What happens now borders on technologic surrealism - the CPython, after
> many years of persuasion, switched its dict algorithm, rather
> inefficient in terms of memory, to something else, less inefficient
> (still quite inefficient, taking "no overhead" as the baseline).

Trading off space for time is a very common practice. You said that 
lookups on MicroPython's dicts are O(N). How efficient is µPy when doing 
a lookup of a dict with ten million keys?

µPy has chosen to optimize for space, rather than time. That's great. 
But I don't think you should sneer at CPython's choice to optimize for 
time instead.

And given that µPy's dicts already fail to meet the expected O(1) dict 
behviour, and the already large number of functional differences (not 
just performance differences) between µPy and Python:

http://docs.micropython.org/en/latest/pyboard/genrst/index.html

I don't think that this will make much practical difference. MicroPython 
users already cannot expect to run arbitrary Python code that works in 
other implementations: the Python community is fragmented between µPy 
code written for tiny machines, and Python code for machines with lots 
of memory.


> That
> algorithm randomly had another property. Now there's a seemingly
> serious talk of letting that property leak into the *language spec*,

It will no more be a "leak" than any other deliberate design choice.


> despite the fact that there can be unlimited number of dictionary
> algorithms, most of them not having that property. 

Sure. So what? There's an unlimited number of algorithms that don't 
provide the functionality that we want. There are an unlimited number of 
sort algorithms, but Python guarantees that we're only going to use 
those that are stable. Similar applies for method resolution (which µPy 
already violates), strings, etc.


> What it will lead to is further fragmentation of the community.

Aren't you concerned about fragmenting the community because of the 
functional differences between MicroPython and the specs?

Sometimes a small amount of fragmentation is unavoidable, and not 
necessarily a bad thing.


> > P.S. If anyone does want to explore MicroPython's dict implementation,
> > and see if there might be an alternate implementation strategy that
> > offers both O(1) lookup and guaranteed ordering without using
> > additional memory
> 
> That would be the first programmer in the history to have a cake and
> eat it too. Memory efficiency, runtime efficiency, sorted order: choose
> 2 of 3.

Given that you state that µPy dicts are O(N) and unordered, does that 
mean you picked only 1 out of 3?


-- 
Steve