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

[INADA Naoki]

There are three options I can think.


1) Revert key-shared dict (PEP412).

pros: Removing key-shared dict makes dict implementation simple.

cons: In some applications, PEP 412 is far more compact than compact
ordered dict.  (Note: Using __slots__ may help such situation).


2) Don't make "keeping insertion order" is Python Language Spec.

pros: Best efficiency

cons: Different behavior between normal dict and instance.__dict__ may
confuse people.


3) More strict rule for key sharing dict.

My idea is:
* Increasing number of entries (inserting new key) can be possible
only if refcnt of keys == 1.

* Inserting new item (with existing key) into dict is allowed only when
  insertion position == number of items in the dict (PyDictObject.ma_used).

pros: We can have "dict keeping insertion order".

cons: Can't use key-sharing dict for many cases.  Small and harmless
change may cause
sudden memory usage increase.  (__slots__ is more predicable).


On Wed, Jun 22, 2016 at 12:10 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.
>
>
> On Tue, Jun 21, 2016 at 2:02 PM, INADA Naoki <songofacandy at gmail.com> wrote:
>> On Tue, Jun 21, 2016 at 12:17 PM, Oleg Broytman <phd at phdru.name> wrote:
>>> Hi!
>>>
>>> On Tue, Jun 21, 2016 at 11:14:39AM +0900, INADA Naoki <songofacandy at gmail.com> wrote:
>>>> Here is my draft, but I haven't
>>>> posted it yet since
>>>> my English is much worse than C.
>>>> https://www.dropbox.com/s/s85n9b2309k03cq/pep-compact-dict.txt?dl=0
>>>
>>>    It's good enough for a start (if a PEP is needed at all). If you push
>>> it to Github I'm sure they will come with pull requests.
>>>
>>> Oleg.
>>
>> Thank you for reading my draft.
>>
>>> (if a PEP is needed at all)
>>
>> I don't think so. My PEP is not for changing Python Language,
>> just describe implementation detail.
>>
>> Python 3.5 has new OrderedDict implemented in C without PEP.
>> My patch is relatively small than it.  And the idea has been well known.
>>
>> --
>> INADA Naoki  <songofacandy at gmail.com>
>
>
>
> --
> INADA Naoki  <songofacandy at gmail.com>



-- 
INADA Naoki  <songofacandy at gmail.com>