[issue28183] Clean up and speed up dict iteration

Changes by Donald Stufft : -- pull_requests: +852 ___ Python tracker ___ ___

[issue28183] Clean up and speed up dict iteration

Serhiy Storchaka added the comment: Few weeks I tried to rewrite loops in more fast way, but I have not found anything significantly faster or clearer. Some forms of was a few percent faster, but I would be difficult to explain this effect. Most likely it was an artifact of the compilation.

[issue28183] Clean up and speed up dict iteration

Roundup Robot added the comment: New changeset 112714f3745d by Serhiy Storchaka in branch '3.6': Issue #28183: Optimize and cleanup dict iteration. https://hg.python.org/cpython/rev/112714f3745d -- nosy: +python-dev ___ Python tracker

[issue28183] Clean up and speed up dict iteration

INADA Naoki added the comment: dict_iter8.patch is based on dict_iter3.patch. Added some comments and fixing indents. No change about _PyDict_Next API. -- Added file: http://bugs.python.org/file44921/dict_iter8.patch ___ Python tracker

[issue28183] Clean up and speed up dict iteration

INADA Naoki added the comment: Refactoring includes replacing PyDict_Next with _PyDict_Next. It can improve performance by skipping some checks. But it would be too small to see difference from benchmark. I'll reduce diff size, hopefully in this weekend. --

[issue28183] Clean up and speed up dict iteration

STINNER Victor added the comment: Serhiy Storchaka added the comment: > It looks to me that the patch contain unneeded changes. Some changes don't > affect performance, others don't look well justified. Are there benchmarks > that confirm the benefit of these changes? Hum, since I expect

[issue28183] Clean up and speed up dict iteration

Serhiy Storchaka added the comment: It looks to me that the patch contain unneeded changes. Some changes don't affect performance, others don't look well justified. Are there benchmarks that confirm the benefit of these changes? -- ___ Python

[issue28183] Clean up and speed up dict iteration

Serhiy Storchaka added the comment: Please wait until I merge my changes. -- ___ Python tracker ___ ___

[issue28183] Clean up and speed up dict iteration

STINNER Victor added the comment: dict_iter7.patch LGTM, go ahead. Just dont forget to mention Serhiy Storchaka as the co-author ;-) -- ___ Python tracker

[issue28183] Clean up and speed up dict iteration

Changes by INADA Naoki : Added file: http://bugs.python.org/file44879/dict_iter7.patch ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

INADA Naoki added the comment: recreate patch with different option, since Rietveld doesn't accept dict_iter5.patch -- Added file: http://bugs.python.org/file44876/dict_iter6.patch ___ Python tracker

[issue28183] Clean up and speed up dict iteration

Changes by INADA Naoki : Added file: http://bugs.python.org/file44874/dict_iter5.patch ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

STINNER Victor added the comment: I reviewed dict_iter4.patch on Rietveld. -- ___ Python tracker ___ ___

[issue28183] Clean up and speed up dict iteration

INADA Naoki added the comment: Draft Misc/NEWS entry (and commit message) is: Core and Builtins - +- Issue #28183: Optimize dict iteration. + -- ___ Python tracker

[issue28183] Clean up and speed up dict iteration

Changes by INADA Naoki : -- versions: +Python 3.7 Added file: http://bugs.python.org/file44864/dict_iter4.patch ___ Python tracker

[issue28183] Clean up and speed up dict iteration

INADA Naoki added the comment: Updated with small refactoring. Confirmed passes quicktest and no warning from clang on OS X. -- Added file: http://bugs.python.org/file44857/dict_iter3.patch ___ Python tracker

[issue28183] Clean up and speed up dict iteration

Serhiy Storchaka added the comment: Feel free to do this. I'm not such busy, I'm experimenting with other variants. -- ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

INADA Naoki added the comment: Serhiy, may I update your patch, if you're busy in this week? -- ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

Raymond Hettinger added the comment: Moved dictresize() discussion to http://bugs.python.org/issue28199 -- ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

Serhiy Storchaka added the comment: Raymond, I think this is different issue. -- ___ Python tracker ___ ___

[issue28183] Clean up and speed up dict iteration

Raymond Hettinger added the comment: Here is a rough (very rough and not compileable) sketch of the direction that resizing should take: static void insert_indices_clean(PyDictObject *mp, Py_hash_t hash) { size_t i, perturb; PyDictKeysObject *k = mp->ma_keys; size_t mask =

[issue28183] Clean up and speed up dict iteration

Serhiy Storchaka added the comment: Actually most of optimization is not specific for new dict implementation. -- ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

Raymond Hettinger added the comment: We can still clean this up for Python 3.6. We're in feature freeze, not development freeze. The compact dict patch was very rough when it landed and is expected to continue to be polished so that the expected benefits are realized. -- versions:

[issue28183] Clean up and speed up dict iteration

Changes by Serhiy Storchaka : -- assignee: -> serhiy.storchaka versions: -Python 3.6 ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

Raymond Hettinger added the comment: > Raymond: With such implementation keys, values and hashes are all > organized together and there seems no _resize operation can only > adjust hashes without breaking the entire layout. None of those needs to change during a resize. Only indices array

[issue28183] Clean up and speed up dict iteration

INADA Naoki added the comment: LGTM, thanks. -- ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue28183] Clean up and speed up dict iteration

Xiang Zhang added the comment: Serhiy: Patch LGTM except two trivial comments on Rietveld. Raymond: With such implementation keys, values and hashes are all organized together and there seems no _resize operation can only adjust hashes without breaking the entire layout. --

[issue28183] Clean up and speed up dict iteration

Raymond Hettinger added the comment: Also, please take a look at resizing. It looks like it is doing way too much work. The original keys, values, and hashes shouldn't move at all, only the indices array needs to updated. Here is the pure python version from the original proof-of-concept at

[issue28183] Clean up and speed up dict iteration

Raymond Hettinger added the comment: Yes, I missed seeing that. -- ___ Python tracker ___ ___

[issue28183] Clean up and speed up dict iteration

Serhiy Storchaka added the comment: Dict iterators already have __length_hint__. Dict views have __len__. -- ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

Raymond Hettinger added the comment: Also consider adding __length_hint__ to the various mapping views. That would help with a common case of listing the view. -- ___ Python tracker

[issue28183] Clean up and speed up dict iteration

Serhiy Storchaka added the comment: Good catch Xiang Zhang! I missed this point. Here is fixed patch. $ ./python -m perf timeit -s "d = dict.fromkeys(range(10**6))" -- "list(d)" Python 3.5:Median +- std dev: 33.8 ms +- 0.7 ms Python 3.6 unpatched: Median +- std dev: 37.8 ms +- 0.5

[issue28183] Clean up and speed up dict iteration

Xiang Zhang added the comment: Serhiy, I don't understand your patch. You delete the logic about split table and then iterating split table actually fails. >>> class C: ... pass ... >>> a, b = C(), C() >>> a.a, a.b = 1, 2 >>> list(b.__dict__) ['a', 'b'] >>> Without attributes now b also

[issue28183] Clean up and speed up dict iteration

Changes by STINNER Victor : -- nosy: +methane, xiang.zhang ___ Python tracker ___

[issue28183] Clean up and speed up dict iteration

New submission from Serhiy Storchaka: In some circumstances iterating dict under 3.6 can be 20% slower than under 3.5. $ ./python -m perf timeit -s "d = dict.fromkeys(range(10**6))" -- "list(d)" Python 3.5: Median +- std dev: 33.8 ms +- 0.7 ms Python 3.6: Median +- std dev: 37.8 ms +- 0.5 ms