New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Clean up and speed up dict iteration #72370
Comments
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 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(): PyDict_Next(): |
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. |
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 |
Also consider adding __length_hint__ to the various mapping views. That would help with a common case of listing the view. |
Dict iterators already have __length_hint__. Dict views have __len__. |
Yes, I missed seeing that. |
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__().
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. |
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. |
LGTM, thanks. |
None of those needs to change during a resize. Only indices array needs to be rebuilt. |
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. |
Actually most of optimization is not specific for new dict implementation. |
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 = (size_t)DK_SIZE(k)-1; i = hash & mask;
for (perturb = hash; dk_get_index(k, i) != DKIX_EMPTY;
perturb >>= PERTURB_SHIFT) {
i = mask & ((i << 2) + i + perturb + 1);
}
dk_set_index(k, i, k->dk_nentries);
} static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
Py_ssize_t i, newsize;
PyDictKeyEntry *ep0;
/* Find the smallest table size > minused. */
for (newsize = PyDict_MINSIZE;
newsize <= minused && newsize > 0;
newsize <<= 1)
;
if (newsize <= 0) {
PyErr_NoMemory();
return -1;
}
for (i = 0; i < mp->dk_nentries; i++) {
PyDictKeyEntry *ep = &ep0[i];
if (ep->me_value != NULL) {
insert_indices_clean(mp, ep->me_hash);
}
}
return 0;
} |
Raymond, I think this is different issue. |
Moved dictresize() discussion to http://bugs.python.org/issue28199 |
Serhiy, may I update your patch, if you're busy in this week? |
Feel free to do this. I'm not such busy, I'm experimenting with other variants. |
Updated with small refactoring. |
I reviewed dict_iter4.patch on Rietveld. |
recreate patch with different option, since Rietveld doesn't accept dict_iter5.patch |
dict_iter7.patch LGTM, go ahead. Just dont forget to mention Serhiy Storchaka as the co-author ;-) |
Please wait until I merge my changes. |
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? |
Serhiy Storchaka added the comment:
Hum, since I expect disagreements on the changes, I propose to split "Some changes don't affect performance" Well, a cleanup is supposed to not affect performances at all :-) |
Refactoring includes replacing PyDict_Next with _PyDict_Next. I'll reduce diff size, hopefully in this weekend. |
dict_iter8.patch is based on dict_iter3.patch. Added some comments and fixing indents. |
New changeset 112714f3745d by Serhiy Storchaka in branch '3.6': |
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. Removed unrelated changes from dict_iter8.patch and added additional check in _PyDict_Next() before committing. |
Misc/NEWS
so that it is managed by towncrier #552Note: 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:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: