On 6 November 2017 at 09:43, Raymond Hettinger <raymond.hettin...@gmail.com> wrote: > On Nov 4, 2017, at 7:04 PM, Nick Coghlan <ncogh...@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 | ncogh...@gmail.com | Brisbane, Australia _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
