Hello, On Sun, 5 Nov 2017 12:04:41 +1000 Nick Coghlan <ncogh...@gmail.com> wrote:
> On 5 November 2017 at 04:35, Guido van Rossum <gu...@python.org> > wrote: > > This sounds reasonable -- I think when we introduced this in 3.6 we > > were worried that other implementations (e.g. Jython) would have a > > problem with this, but AFAIK they've reported back that they can do > > this just fine. So let's just document this as a language > > guarantee. > > When I asked Damien George about this for MicroPython, he indicated > that they'd have to choose between guaranteed order and O(1) lookups > given their current dict implementation. That surprised me a bit MicroPython hashmap implementation is effectively O(n) (average and worst case) due to the algorithm parameters chosen (like the load factor of 1). Of course, parameters could be tweaked, but the ones chosen are so because the memory usage is far more important for MicroPython systems than performance characteristics (all due to small amounts of memory). Like, MicroPython was twice as fast than Python 3.3 on average, and 1000 times more efficient in the memory usage. > (since PyPy and CPython both *saved* memory by switching to their > guaranteed order implementations, hence the name "compact dict There's nothing to save in MicroPython's dict implementation, simply because it doesn't waste anything in the first place - uPy's dict entry is just (key, val) (2 machine words), and load factor of the dict can reach 1.0 as mentioned. [] > I don't think that situation should change the decision, Indeed, it shouldn't. What may change it is the simple and obvious fact that there's no need to change anything, as proven by the 25-year history of the language. What happens now borders on technologic surrealism - the CPython, after many years of persuasion, switched its dict algorithm, rather inefficient in terms of memory, to something else, less inefficient (still quite inefficient, taking "no overhead" as the baseline). That algorithm randomly had another property. Now there's a seemingly serious talk of letting that property leak into the *language spec*, despite the fact that there can be unlimited number of dictionary algorithms, most of them not having that property. What it will lead to is further fragmentation of the community. Python2 vs Python3 split is far from being over, and now there're splits between: * people who use "yield from" vs "await" * people who use f-strings vs who don't * people who rely on sorted nature of dict's vs who don't etc. [] > P.S. If anyone does want to explore MicroPython's dict implementation, > and see if there might be an alternate implementation strategy that > offers both O(1) lookup and guaranteed ordering without using > additional memory That would be the first programmer in the history to have a cake and eat it too. Memory efficiency, runtime efficiency, sorted order: choose 2 of 3. -- 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
