[Python-Dev] Compact ordered dict is not ordered for split table. (was: PEP XXX: Compact ordered dict

[INADA Naoki]

On Sun, Jun 26, 2016 at 8:40 AM, Franklin? Lee
<leewangzhong+python at gmail.com> wrote:
> On Jun 21, 2016 11:12 AM, "INADA Naoki" <songofacandy at gmail.com> wrote:
>>
>> I'm sorry, but I hadn't realized which compact ordered dict is
>> not ordered for split table.
>>
>> For example:
>> >>> class A:
>> ...   ...
>> ...
>> >>> a = A()
>> >>> b = A()
>> >>> a.a = 1
>> >>> a.b = 2
>> >>> b.b = 3
>> >>> b.a = 4
>> >>> a.__dict__.items()
>> dict_items([('a', 1), ('b', 2)])
>> >>> b.__dict__.items()
>> dict_items([('a', 4), ('b', 3)])
>>
>>
>> This doesn't affects to **kwargs and class namespace.
>>
>> But if we change the language spec to dict preserves insertion order,
>> this should be addressed.
>
> Is that really how it works? From my understanding of PEP 412, they should
> have different keysets, because one diverged in keys from the other at an
> intermediate step.

See here
https://github.com/python/cpython/blob/3.5/Objects/dictobject.c#L3855-L3866

When keys is resized,

1) If refcnt of old keys is one, new keys are shared with instances
created after.
2) Otherwise, sharing key of the class is totally disabled.


> Another idea (though it has several issues and seems like a step backward):
> a split-table dict can have a separate iteration list, indexing into the
> entry table. There are ways to share iteration lists, and make it so that
> adding the same keys in the same order each time results in the same
> iteration list each time, but this costs overhead. There might be ways of
> reducing the overhead, or the overhead might be replacing bigger overhead,
> but we should decide if the behavior is what we want in the first place.
>

I'll test some ideas.

But for now, I'll update http://bugs.python.org/issue27350 to stop key
sharing when
order is different.  (a. deletion is not allowed, and insertion order
must be same).

It may reduce key sharing rate, but total memory usage must not increase so
much thanks to compact dict.

-- 
INADA Naoki  <songofacandy at gmail.com>