[Python-Dev] Guarantee ordered dict literals in v3.7?

[INADA Naoki]

On Mon, Nov 6, 2017 at 4:54 AM, Serhiy Storchaka <storchaka at 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  <songofacandy at gmail.com>