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

[Nick Coghlan]

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