[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Inada Naoki added the comment: @Serhiy > It the pure Python implementation PyDict_GetItem also > returns value, not node of linked list. I missed pure Python implementation used two dicts. @Eric > Please don't miss the fact that the main reason for mirroring the dict table > is to get O(1

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Eric Snow added the comment: Please don't miss the fact that the main reason for mirroring the dict table is to get O(1) node lookup (in the linked list). Otherwise most lookup-dependent operations, like __delitem__(), would become O(n); whereas in the pure-Python implementation they are O(

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Serhiy Storchaka added the comment: It the pure Python implementation PyDict_GetItem also returns value, not node of linked list. > How about raising DeprecationWarning when OrderedDict is passed to PyDict_* APIs? This would violate the Liskov substitution principle and add an overhead for u

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Inada Naoki added the comment: There are some more aggressive ideas. When Eric created C version of OrderedDict, he intended to use it for PEP 468. Unlike pure Python implementation, PyDict_GetItem returns value, not node of linked list. But now, PEP 468 is implemented in regular dict. How a

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Change by Cheryl Sabella : -- versions: +Python 3.8 -Python 3.7 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

INADA Naoki added the comment: pyperformance doesn't show significant performance degration. (using commit 5d8d3d1) $ ./python -m perf compare_to -G --min-speed=2 default.json patched.json Slower (5): - pickle_list: 9.40 us +- 0.98 us -> 9.96 us +- 1.20 us: 1.06x slower (+6%) - pickle_dict: 6

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Serhiy Storchaka added the comment: PR 4901 implements Inada's idea about changing dk_lookup to an index. This decreases the size, but can have negative performance effect (I didn't make benchmarks). -- ___ Python tracker

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Change by Serhiy Storchaka : -- pull_requests: +4796 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://m

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Raymond Hettinger added the comment: I also have misgivings about the extra field. Perhaps solicit some other opinions about whether the trade-off is worth it. Maybe Tim can provide an insight. My suspicion is that the current tight coupling is going to cost us in other ways. The OrderedDi

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Serhiy Storchaka added the comment: But this increases the size of regular dicts. Is it appropriate? -- ___ Python tracker ___ ___ P

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Raymond Hettinger added the comment: This looks reasonable to me. The previous design was too tightly coupled. The regular dict shouldn't have to care about the OrderedDict at all. -- ___ Python tracker __

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Serhiy Storchaka added the comment: Could you please make a review Raymond? -- assignee: -> rhettinger ___ Python tracker ___ ___ P

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

INADA Naoki added the comment: I don't know why dk_lookup is in dictkeys object. But I think it's because sharing 1 word from all key-sharing dict. So ma_clean flag can be in dictkeys object for same reason. BTW, We use dk_lookup function pointer and it tooks 1 word. But PyPy use flags for it.

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Serhiy Storchaka added the comment: Thank you for your microbenchmark Inada. The difference is small, but repeating it with different modifications almost always show small speedup. The only problem is that this change increases the size of dict object by one word (up to 3% for small dicts).

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

INADA Naoki added the comment: Quick microbench: ``` $ ./python -m perf timeit --compare-to=`pwd`/python.master -s 'd = dict.fromkeys(range(1000))' -- "for i in range(1000): del d[i] d[i]=i " python.master: . 124 us +- 9 us python: . 116 us +- 0 us

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Serhiy Storchaka added the comment: Later I'm going to add a flag that will allow regular dicts reuse holes when delete items, while keep OrderedDict and dicts used as class namespace ordered. I'm not sure there will be a benefit, but at least this will open an option. -- ___

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

New submission from Serhiy Storchaka : Currently OrderedDict uses a table of nodes that mirrors the dict table. For keeping it in sync it saves the size and address of the dict table. There are two issues with this. First, this prevent some kind of dict optimization. When dict is resized (afte

[issue31954] Don't prevent dict optimization by coupling with OrderedDict

Change by Serhiy Storchaka : -- keywords: +patch pull_requests: +4254 stage: -> patch review ___ Python tracker ___ ___ Python-bugs-