-
-
Notifications
You must be signed in to change notification settings - Fork 31.6k
BUILD_MAP_UNPACK_WITH_CALL is slow #71545
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
Comments
BUILD_MAP_UNPACK_WITH_CALL is _really_ slow, wasting much of its time asserting that keys are non overlapping. This patch optimizes a fast path for distinct dicts, especially useful for bpo-27213 where BUILD_MAP_UNPACK_WITH_CALL is generated for a single **kw rather than needing **kw1,**kw2 to hit this slow opcode This patch tracks size of dictionary, if size doesn't increase by same size as the dict we updated sum with, then we scan to find where collision is. Further optimization can be done by scanning size of dicts to preallocate dictionary Microbenchmark: Unpatched takes ~15s |
The problem is that var-keyword argument can be not a dict, but general mapping. This optimization is applicable only if it is a dict. |
mapaca2 heavy handily deals with the must-work-with-all-mappings by converting any non dict mappings on the stack with dicts when with_call is true I'm not sure if it'd be better to seek a less opcode centric fix-- ie introduce a method to dictobject which returns None if no collision occurs otherwise it returns the first key which collides and stops updating at that point. PyDict_DistinctUpdate |
(returning None wouldn't work because that may be the key, but something like returning the dict itself (ie an unhashable) or keeping this as a C API & returning NULL would work) |
I wonder how feasible it would be for e.g. dict.__setitem__ to check if a key already exists; it would be a special path that's not taken normally, but filling the mapping on call enables it, and it raises if it sees a duplicate. I think that inserting the check in there would reduce complexity and probably have a negligible impact on performance. I don't know if that's a good idea, just throwing this out here. |
I think this kills the optimization effect for non-dicts. See on PyDict_Merge(). It takes the boolean parameter that controls the behavior in case of matching keys. I think the best would be to rename it to say _PyDict_MergeEx(), extend the boolean parameter to ternary parameter, and raise an exception if it is in the third state and matching keys are found. PyDict_Merge() would be implemented as a simple wrapper around _PyDict_MergeEx(). We should check wherever this affects the performance of dict.update(). |
See also issue bpo-27845: "Optimize update_keyword_args() function". |
Here is a patch that gets rid of calculating intersections. I didn't make benchmarking still. |
The side effect of the last patch is fixing a regression in 3.6 and a bug in 3.5 (bpo-28257). |
Microbenchmarks: $ ./python -m timeit -s "def f(**kw): pass" -s "b = {'b': 2}" -- "f(a=1, **b)"
Unpatched: 100000 loops, best of 3: 7.64 usec per loop
Patched: 100000 loops, best of 3: 3.14 usec per loop
$ ./python -m timeit -s "def f(**kw): pass" -s "a = {'a': 1}; b = {'b': 2}" -- "f(**a, **b)"
Unpatched: 100000 loops, best of 3: 6.93 usec per loop
Patched: 100000 loops, best of 3: 2.66 usec per loop
$ ./python -m timeit -s "def f(a=None, b=None): pass" -s "b = {'b': 2}" -- "f(a=1, **b)"
Unpatched: 100000 loops, best of 3: 7.27 usec per loop
Patched: 100000 loops, best of 3: 2.83 usec per loop
$ ./python -m timeit -s "def f(a=None, b=None): pass" -s "a = {'a': 1}; b = {'b': 2}" -- "f(**a, **b)"
Unpatched: 100000 loops, best of 3: 6.47 usec per loop
Patched: 100000 loops, best of 3: 2.31 usec per loop |
Impressive numbers but... is it a perf regression compared to Python 3.5 (and even 2.7)? Or a perf speedup compared to Python 3.5? |
Yes, it is expected perf regression compared to Python 3.5 and 2.7 when pass keyword arguments and single var-keyword argument (because 3.6 uses BUILD_MAP_UNPACK_WITH_CALL, while 2.7 and 3.5 don't need it for this case). In case of multiple var-keyword arguments (all versions need BUILD_MAP_UNPACK_WITH_CALL) even unpatched 3.6 is faster than 3.5. $ ./python -m timeit -s "def f(**kw): pass" -s "b = {'b': 2}" -- "f(a=1, **b)"
Python 2.7: 100000 loops, best of 3: 2.21 usec per loop
Python 3.5: 100000 loops, best of 3: 4.31 usec per loop
Python 3.6 unpatched: 100000 loops, best of 3: 7.64 usec per loop
Python 3.6 patched: 100000 loops, best of 3: 3.14 usec per loop
$ ./python -m timeit -s "def f(**kw): pass" -s "a = {'a': 1}; b = {'b': 2}" -- "f(**a, **b)"
Python 3.5: 100000 loops, best of 3: 11.6 usec per loop
Python 3.6 unpatched: 100000 loops, best of 3: 6.93 usec per loop
Python 3.6 patched: 100000 loops, best of 3: 2.66 usec per loop
$ ./python -m timeit -s "def f(a=None, b=None): pass" -s "b = {'b': 2}" -- "f(a=1, **b)"
Python 2.7: 100000 loops, best of 3: 1.97 usec per loop
Python 3.5: 100000 loops, best of 3: 3.75 usec per loop
Python 3.6 unpatched: 100000 loops, best of 3: 7.27 usec per loop
Python 3.6 patched: 100000 loops, best of 3: 2.83 usec per loop
$ ./python -m timeit -s "def f(a=None, b=None): pass" -s "a = {'a': 1}; b = {'b': 2}" -- "f(**a, **b)"
Python 3.5: 100000 loops, best of 3: 10.6 usec per loop
Python 3.6 unpatched: 100000 loops, best of 3: 6.47 usec per loop
Python 3.6 patched: 100000 loops, best of 3: 2.31 usec per loop |
Updated patch addresses Victor's comments. |
New changeset 148172f75d43 by Serhiy Storchaka in branch '3.6': New changeset 489ad68b35c0 by Serhiy Storchaka in branch 'default': New changeset ec84d815e90f by Serhiy Storchaka in branch '3.5': New changeset 29a658d47ae8 by Serhiy Storchaka in branch '2.7': |
test_unpack_ex fails on several buildbots: test test_unpack_ex failed
**********************************************************************
File "/home/buildbot/buildarea/3.6.intel-ubuntu-skylake/build/Lib/test/test_unpack_ex.py", line ?, in test.test_unpack_ex.__test__.doctests
Failed example:
{**1}
Expected:
Traceback (most recent call last):
...
TypeError: 'int' object is not a mapping
Got:
Traceback (most recent call last):
File "/home/buildbot/buildarea/3.6.intel-ubuntu-skylake/build/Lib/doctest.py", line 1330, in __run
compileflags, 1), test.globs)
File "<doctest test.test_unpack_ex.__test__.doctests[38]>", line 1, in <module>
{**1}
TypeError: 'int' object is not a mapping1
**********************************************************************
File "/home/buildbot/buildarea/3.6.intel-ubuntu-skylake/build/Lib/test/test_unpack_ex.py", line ?, in test.test_unpack_ex.__test__.doctests
Failed example:
{**[]}
Expected:
Traceback (most recent call last):
...
TypeError: 'list' object is not a mapping
Got:
Traceback (most recent call last):
File "/home/buildbot/buildarea/3.6.intel-ubuntu-skylake/build/Lib/doctest.py", line 1330, in __run
compileflags, 1), test.globs)
File "<doctest test.test_unpack_ex.__test__.doctests[39]>", line 1, in <module>
{**[]}
TypeError: 'list' object is not a mapping1
**********************************************************************
1 items had failures:
2 of 85 in test.test_unpack_ex.__test__.doctests
***Test Failed*** 2 failures. |
New changeset e2d4e077cfb2 by Berker Peksag in branch '3.6': New changeset 9abb316f1593 by Berker Peksag in branch 'default': |
Thanks Berker! This was temporary change for debugging. I forgot to remove it. |
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: