Clean up and speed up dict iteration

[serhiy-storchaka]

BPO	28183
Nosy	@rhettinger, @vstinner, @ned-deily, @methane, @serhiy-storchaka, @zhangyangyu
PRs	[Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552
Files	dict_iter.patch dict_iter2.patch dict_iter3.patch dict_iter4.patch: more PEP7 compliant code dict_iter5.patch dict_iter6.patch dict_iter7.patch dict_iter8.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2016-10-09.20:17:19.798>
created_at = <Date 2016-09-16.22:10:07.621>
labels = ['interpreter-core', '3.7', 'performance']
title = 'Clean up and speed up dict iteration'
updated_at = <Date 2017-03-31.16:36:09.744>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2017-03-31.16:36:09.744>
actor = 'dstufft'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2016-10-09.20:17:19.798>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2016-09-16.22:10:07.621>
creator = 'serhiy.storchaka'
dependencies = []
files = ['44697', '44719', '44857', '44864', '44874', '44876', '44879', '44921']
hgrepos = []
issue_num = 28183
keywords = ['patch']
message_count = 29.0
messages = ['276755', '276789', '276811', '276821', '276823', '276830', '276868', '276873', '276889', '276899', '276902', '276903', '276915', '276919', '276922', '277501', '277502', '277596', '277612', '277631', '277687', '277699', '277701', '277713', '277718', '277752', '277854', '278387', '278388']
nosy_count = 7.0
nosy_names = ['rhettinger', 'vstinner', 'ned.deily', 'methane', 'python-dev', 'serhiy.storchaka', 'xiang.zhang']
pr_nums = ['552']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue28183'
versions = ['Python 3.6', 'Python 3.7']

[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

[zhangyangyu]

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 get entries when iterating.

[serhiy-storchaka]

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 ms
Python 3.6 patched:    Median +- std dev: 34.0 ms +- 0.6 ms

$ ./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.1 ms +- 0.8 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: 249 ms +- 6 ms

$ ./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: 63.7 ms +- 1.5 ms

$ ./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.05 ms

[rhettinger]

Also consider adding __length_hint__ to the various mapping views. That would help with a common case of listing the view.

[serhiy-storchaka]

Dict iterators already have __length_hint__. Dict views have __len__.

[rhettinger]

Yes, I missed seeing that.

[rhettinger]

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 https://code.activestate.com/recipes/578375

    def _resize(self, n):
        '''Reindex the existing hash/key/value entries.
           Entries do not get moved, they only get new indices.
           No calls are made to hash() or __eq__().

    '''
    n = 2 ** n.bit_length()                     # round-up to power-of-two
    self.indices = self._make_index(n)
    for index, hashvalue in enumerate(self.hashlist):
        for i in Dict._gen_probes(hashvalue, n-1):
            if self.indices[i] == FREE:
                break
        self.indices[i] = index
    self.filled = self.used

Likewise, it looks like there is room for improvement in dict_copy(). It can memcpy() all four arrays and then incref all the keys. That should be considerably faster than zeroing new arrays and applying re-insertion logic.

[zhangyangyu]

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.

[methane]

LGTM, thanks.

[rhettinger]

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 needs to be rebuilt.

[rhettinger]

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.