Supporting insertion-order preservation property of dicts (compat with Python 3.7+)
Python 3.7 made dicts ordered by default, see https://docs.python.org/3/whatsnew/3.7.html
Since it's part of the Python spec, and there are situations where this feature is useful, it makes sense to consider how MicroPython could support it. It may be that it's not realistic to have such a feature in MicroPython by default, maybe in the end it's just a build option for those who need it.
The problem is that implementing it efficiently (retaining O(1) lookup) requires more memory for the dict implementation than is currently used. The alternative is to make lookups O(N) which is proposed in #5323 (see that PR for further discussion).
Another alternative might be to just have ordered dicts only in certain places. There are currently requests for it in the following places:
- class members / locals-dict: #6130
- json loading of dicts: #6135
py/map: Convert map implementation to preserve insertion order (WIP, RFC)
This PR changes the map implementation to make maps preserve insertion order, ie dicts are ordered by default. At this stage it's just for discussion, there's not (yet) any intention of merging it. See #6170 for additional discussion on this topic.
It uses a similar algorithm to PyPy/CPython. RAM overhead compared to the existing (non-order preserving) implementation is +12.5% for dicts with <255 elements, and +25% for dicts with <65535 elements. The code change is surprisingly simple.
TODO:
- support dicts >65535 elements
- make it optional at compile-time
- make OrderedDict use this new implementation
- implement more efficient deletion (currently there are pathological cases where the dict will grow forever if elements are continuously deleted and inserted)
- profile performance and memory use