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

[Nick Coghlan]

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
(since PyPy and CPython both *saved* memory by switching to their
guaranteed order implementations, hence the name "compact dict
representation"), but my (admittedly vague) understand is that the
presence of a space/speed trade-off in their case has something to do
with MicroPython deliberately running with a much higher chance of
hash collisions in general (since the data sets it deals with are
naturally smaller).

So if we make the change, MicroPython will likely go along with it,
but it may mean that dict lookups there become O(N), and folks will be
relying on "N" being consistently small due to memory constraints (but
some typically O(N) algorithms will still become O(N^2) when run on
MicroPython).

I don't think that situation should change the decision, but I do
think it would be helpful if folks that understand CPython's dict
implementation could take a look at MicroPython's dict implementation
and see if it might be possible for them to avoid having to make that
trade-off and instead be able to use a naturally insertion ordered
hashmap implementation.

Cheers,
Nick.

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, the relevant files seem to be:

* https://github.com/micropython/micropython/blob/77a48e8cd493c0b0e0ca2d2ad58a110a23c6a232/py/obj.h#L339
(C level hashmap/ordered array structs)
* https://github.com/micropython/micropython/blob/master/py/map.c (C
level hashmap/ordered array implementation)
* https://github.com/micropython/micropython/blob/master/py/objdict.c
(Python dict wrapper around the mapping impl)

The current behaviour is that the builtin dict uses the hashmap
algorithms, while collections.OrderedDict uses the ordered array
algorithms.

-- 
Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia