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

[Paul Sokolovsky]

Hello,

On Sun, 5 Nov 2017 12:04:41 +1000
Nick Coghlan <ncoghlan at gmail.com> wrote:

> On 5 November 2017 at 04:35, Guido van Rossum <guido at python.org>
> wrote:
> > This sounds reasonable -- I think when we introduced this in 3.6 we
> > were worried that other implementations (e.g. Jython) would have a
> > problem with this, but AFAIK they've reported back that they can do
> > this just fine. So let's just document this as a language
> > guarantee.  
> 
> When I asked Damien George about this for MicroPython, he indicated
> that they'd have to choose between guaranteed order and O(1) lookups
> given their current dict implementation. That surprised me a bit

MicroPython hashmap implementation is effectively O(n) (average and
worst case) due to the algorithm parameters chosen (like the load factor
of 1). Of course, parameters could be tweaked, but the ones chosen are
so because the memory usage is far more important for MicroPython
systems than performance characteristics (all due to small amounts of
memory). Like, MicroPython was twice as fast than Python 3.3 on
average, and 1000 times more efficient in the memory usage.

> (since PyPy and CPython both *saved* memory by switching to their
> guaranteed order implementations, hence the name "compact dict

There's nothing to save in MicroPython's dict implementation, simply
because it doesn't waste anything in the first place - uPy's dict entry
is just (key, val) (2 machine words), and load factor of the dict can
reach 1.0 as mentioned.

[]

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

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). That
algorithm randomly had another property. Now there's a seemingly
serious talk of letting that property leak into the *language spec*,
despite the fact that there can be unlimited number of dictionary
algorithms, most of them not having that property. 

What it will lead to is further fragmentation of the community. Python2
vs Python3 split is far from being over, and now there're splits
between:

* people who use "yield from" vs "await"
* people who use f-strings vs who don't
* people who rely on sorted nature of dict's vs who don't

etc.

[]

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


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