On Mon, Nov 6, 2017 at 4:54 AM, Serhiy Storchaka <storch...@gmail.com> wrote: ... > > I didn't try to implement this. But the current implementation requires > periodical reallocating if add and remove items. The following loop > reallocates the dict every len(d) iterations, while the size of the dict is > not changed, and the half of its storage is empty. > > while True: > v = d.pop(k) > ... > d[k] = v >
FYI, Raymond's original compact dict (moving last item to slot used for deleted item) will break OrderedDict. So it's not easy to implement than it looks. OrderedDict uses linked list to keep which slot is used for the key. Moving last item will break it. It means odict.__delitem__ can't use PyDict_DelItem anymore and OrderedDict should touch internal structure of dict. I think current OrderedDict implementation is fragile loose coupling. While two object has different file (dictobject.c and odictobject.c), OrderedDict depends on dict's internal behavior heavily. It prevents optimizing dict. See comment here. https://github.com/python/cpython/blob/a5293b4ff2c1b5446947b4986f98ecf5d52432d4/Objects/dictobject.c#L1082 I don't have strong opinion about what should we do about dict and OrderedDict. But I feel PyPy's approach (using same implementation and just override __eq__ and add move_to_end() method) is most simple. Regards, INADA Naoki <songofaca...@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
