| msg268951 - (view) |
Author: Philip Dubé (Demur Rumed) * |
Date: 2016-06-21 01:45 |
| 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 #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: from timeit import timeit def f(**x):return x timeit(lambda:f(**{'a':2},**{'b':2})) Unpatched takes ~15s Patched takes ~5s |
|
|
| msg268967 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) *  |
Date: 2016-06-21 05:00 |
| 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. |
|
|
| msg268989 - (view) |
Author: Philip Dubé (Demur Rumed) * |
Date: 2016-06-21 13:03 |
| 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 |
|
|
| msg268990 - (view) |
Author: Philip Dubé (Demur Rumed) * |
Date: 2016-06-21 13:05 |
| (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) |
|
|
| msg268992 - (view) |
Author: Anilyka Barry (abarry) *  |
Date: 2016-06-21 13:15 |
| `dict` subclasses can be hashable - it's a very bad idea, but not guarded against. If you were to do this, I'd suggest going the exception way, à la StopIteration. 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. |
|
|
| msg268997 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2016-06-21 13:43 |
| 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(). |
|
|
| msg273680 - (view) |
Author: STINNER Victor (vstinner) * |
Date: 2016-08-25 21:45 |
| See also issue #27845: "Optimize update_keyword_args() function". |
|
|
| msg275710 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2016-09-10 22:56 |
| Here is a patch that gets rid of calculating intersections. I didn't make benchmarking still. |
|
|
| msg277279 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2016-09-23 14:08 |
| The side effect of the last patch is fixing a regression in 3.6 and a bug in 3.5 (). |
|
|
| msg277283 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2016-09-23 15:31 |
| 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 |
|
|
| msg277285 - (view) |
Author: STINNER Victor (vstinner) * |
Date: 2016-09-23 16:23 |
| > $ ./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 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? |
|
|
| msg277287 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2016-09-23 16:58 |
| 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 |
|
|
| msg277297 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2016-09-23 20:47 |
| Updated patch addresses Victor's comments. |
|
|
| msg277859 - (view) |
Author: Roundup Robot (python-dev) |
Date: 2016-10-02 08:12 |
| New changeset 148172f75d43 by Serhiy Storchaka in branch '3.6': Issue #27358: Optimized merging var-keyword arguments and improved error https://hg.python.org/cpython/rev/148172f75d43 New changeset 489ad68b35c0 by Serhiy Storchaka in branch 'default': Issue #27358: Optimized merging var-keyword arguments and improved error https://hg.python.org/cpython/rev/489ad68b35c0 New changeset ec84d815e90f by Serhiy Storchaka in branch '3.5': Issue #27358: Backported tests. https://hg.python.org/cpython/rev/ec84d815e90f New changeset 29a658d47ae8 by Serhiy Storchaka in branch '2.7': Issue #27358: Backported tests. https://hg.python.org/cpython/rev/29a658d47ae8 |
|
|
| msg277866 - (view) |
Author: Berker Peksag (berker.peksag) * |
Date: 2016-10-02 09:15 |
| test_unpack_ex fails on several buildbots: http://buildbot.python.org/all/builders/x86-64%20Ubuntu%2015.10%20Skylake%20CPU%203.6/builds/120/steps/test/logs/stdio 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 {**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 {**[]} 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. |
|
|
| msg277877 - (view) |
Author: Roundup Robot (python-dev) |
Date: 2016-10-02 10:06 |
| New changeset e2d4e077cfb2 by Berker Peksag in branch '3.6': Issue #27358: Fix typo in error message https://hg.python.org/cpython/rev/e2d4e077cfb2 New changeset 9abb316f1593 by Berker Peksag in branch 'default': Issue #27358: Merge from 3.6 https://hg.python.org/cpython/rev/9abb316f1593 |
|
|
| msg277878 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2016-10-02 10:10 |
| Thanks Berker! This was temporary change for debugging. I forgot to remove it. |
|
|