[Python-Dev] Guarantee ordered dict literals in v3.7?
steve at pearwood.info
Mon Nov 6 22:51:49 EST 2017
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
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
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:
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
> 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?
More information about the Python-Dev