[Python-Dev] Guarantee ordered dict literals in v3.7? (original) (raw)

Nick Coghlan ncoghlan at gmail.com
Sat Nov 4 22:04:41 EDT 2017

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:

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

More information about the Python-Dev mailing list