[New-bugs-announce] [issue28183] Clean up and speed up dict iteration

[Serhiy Storchaka]

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

Seems this is compiler and platform specific, it is reproducible only with GCC on 32 bit.
 
Proposed patch restores 3.5 performance and simplifies the code.

Python 3.6 patched: Median +- std dev: 33.7 ms +- 0.7 ms

Other types of iteration:

$ ./python -m perf timeit -s "d = dict.fromkeys(range(10**6)); v = d.values()" -- "list(v)"
Python 3.5:            Median +- std dev: 26.2 ms +- 0.7 ms
Python 3.6 unpatched:  Median +- std dev: 28.0 ms +- 0.6 ms
Python 3.6 patched:    Median +- std dev: 26.3 ms +- 1.1 ms

$ ./python -m perf timeit -s "d = dict.fromkeys(range(10**6)); v = d.items()" -- "list(v)"
Python 3.5:            Median +- std dev: 232 ms +- 6 ms
Python 3.6 unpatched:  Median +- std dev: 259 ms +- 6 ms
Python 3.6 patched:    Median +- std dev: 243 ms +- 9 ms

_PyDict_Next():
$ ./python -m perf timeit -s "d = dict.fromkeys(range(10**6))" -- "set(d)"
Python 3.5:            Median +- std dev: 68.3 ms +- 1.8 ms
Python 3.6 unpatched:  Median +- std dev: 68.1 ms +- 2.5 ms
Python 3.6 patched:    Median +- std dev: 66.0 ms +- 1.2 ms

PyDict_Next():
$ ./python -m perf timeit -s "from _testcapi import test_dict_iteration as t" -- "t()"
Python 3.5:            Median +- std dev: 3.31 ms +- 0.10 ms
Python 3.6 unpatched:  Median +- std dev: 3.51 ms +- 0.09 ms
Python 3.6 patched:    Median +- std dev: 3.43 ms +- 0.09 ms

----------
components: Interpreter Core
files: dict_iter.patch
keywords: patch
messages: 276755
nosy: haypo, ned.deily, rhettinger, serhiy.storchaka
priority: normal
severity: normal
status: open
title: Clean up and speed up dict iteration
type: performance
versions: Python 3.6, Python 3.7
Added file: http://bugs.python.org/file44697/dict_iter.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue28183>
_______________________________________