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

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.


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

More information about the Python-Dev mailing list