On May 26, 2018, at 7:20 AM, INADA Naoki firstname.lastname@example.org wrote:
Because doubly linked list is very memory inefficient, every implementation would be forced to implement dict like PyPy (and CPython) for efficiency. But I don't know much about current MicroPython and other Python implementation's plan to catch Python 3.6 up.
FWIW, Python 3.7 is the first Python that where the language guarantees that regular dicts are order preserving. And the feature being discussed in this thread is for Python 3.8.
What potential implementation obstacles do you foresee? Can you imagine any possible way that an implementation would have an order preserving dict but would be unable to trivially implement __reversed__? How could an implementation have a __setitem__ that appends at the end, and a popitem() that pops from that same end, but still not be able to easily iterate in reverse? It really doesn't matter whether an implementer uses a dense array of keys or a doubly-linked-list; either way, looping backward is as easy as going forward.
P.S. It isn't going to be hard to update MicroPython to have a compact and ordered dict (based on my review of their existing dict implementation). This is something they are really going to want because of the improved memory efficiency. Also, they're also already going to need it just to comply with guaranteed keyword argument ordering and guaranteed ordering of class dictionaries.