Hello, On Tue, 7 Nov 2017 17:33:03 +1100 Steven D'Aprano <st...@pearwood.info> wrote:
> On Mon, Nov 06, 2017 at 06:35:48PM +0200, Paul Sokolovsky wrote: > > > For MicroPython, it would lead to quite an overhead to make > > dictionary items be in insertion order. As I mentioned, MicroPython > > optimizes for very low bookkeeping memory overhead, so lookups are > > effectively O(n), but orderedness will increase constant factor > > significantly, perhaps 5x. > > Paul, it would be good if you could respond to Raymond's earlier > comments where he wrote: > > 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 > > Raymond has also volunteered to assist with this. I tried to do that, let me summarize previous point and give IMHO re: contributing an alternative: MicroPython's dict implementation is optimized for the least bookkeeping overhead, not performance on overlarge datasets. For the heap sizes we target (64KB on average), that's a good choice (put it differently, MicroPython's motto is "system's memory (all bunch kilobytes of it) belongs to user, not to MicroPython"). Adding insertion order would either: 1. Lead to significant (several times) slowdown, or 2. To noticeable memory overhead. Note that MicroPython uses the absolute minimum for a dictionary entry - 2 words (key and value). Adding even one extra word (e.g. some indirection pointer) means increasing overhead by 50%, cutting useful user memory size by third. With all that in mind, MicroPython is a very configurable project (215 config options as of this moment). We can have a config option for dict implementation too. But, the points above still hold - MicroPython targets low-memory systems and doesn't really target plenty-of-memory systems (there was never an aim to compete with CPython, the aim was to bring Python (the language) where CPython could never go). Put it another way, the alternative dict implementation is not expected to be used by default. If, with all the above in mind, someone, especially a CPython developer, wants to contribute an alternative dict implementation, it would be gladly accepted. (Note that if CPython followed the same policy, i.e. allowed compile-time selection of old vs new dict algorithm, we wouldn't have this thread.) (Disclaimer: all the above is just my IMHO as a long-time contributor, I'm not a MicroPython BDFL). And I really appreciate all the attention to MicroPython - that's the biggest case on my memory on python-dev. [] -- Best regards, Paul mailto:pmis...@gmail.com _______________________________________________ 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
