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

Nick Coghlan ncoghlan at gmail.com
Sun Nov 5 22:13:16 EST 2017

On 6 November 2017 at 09:43, Raymond Hettinger <raymond.hettinger at gmail.com> wrote:

On Nov 4, 2017, at 7:04 PM, Nick Coghlan <ncoghlan at gmail.com> wrote:

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. I've just looked at the MicroPython dictionary implementation and think they won't have a problem implementing O(1) compact dicts with ordering. The likely reason for the confusion is that they are already have an option for an "ordered array" dict variant that does a brute-force linear search. However, their normal hashed lookup is very similar to ours and is easily amenable to being compact and ordered. See: https://github.com/micropython/micropython/blob/77a48e8cd493c0b0e0ca2d2ad58a110a23c6a232/py/map.c#L139 Pretty much any implementation hashed lookup of keys and values is amenable to being compact and ordered. Whatever existing logic that looks up an entry becomes a lookup into a table of indices which in turn references a sequential array of keys and values. This logic is independent of hashing scheme or density, and it has no effect on the number of probes or collision rate. The cost is an extra level of indirection and an extra array of indices (typically very small). The benefit is faster iteration over the smaller dense key/value array, overall memory savings resulting in improved cache utilization, and the side-effect of remembering insertion order. Summary: I think MicroPython will be just fine and if needed I will help create the patch that implements compact-and-ordered behavior.

Nice! That's what I thought based on reading some of the design discussions about CPython's dict implementation, but I didn't know the details of either dict implementation well enough to be confident that the CPython changes would map cleanly to MicroPython's variant.

Cheers, Nick.

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

More information about the Python-Dev mailing list