Repository navigation
Tuple creation is too slow #67695
Description
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 = None
closed_at = <Date 2016-12-18.13:02:51.224>
created_at = <Date 2015-02-24.08:08:32.468>
labels = ['interpreter-core', 'performance']
title = 'Tuple creation is too slow'
updated_at = <Date 2016-12-18.13:02:51.222>
user = 'https://github.com/serhiy-storchaka'bugs.python.org fields:
activity = <Date 2016-12-18.13:02:51.222>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2016-12-18.13:02:51.224>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2015-02-24.08:08:32.468>
creator = 'serhiy.storchaka'
dependencies = []
files = ['38223', '38244', '42569', '42571', '45725', '45726', '45953']
hgrepos = []
issue_num = 23507
keywords = ['patch']
message_count = 25.0
messages = ['236480', '236654', '236656', '236661', '236691', '236692', '236696', '240693', '240845', '240862', '263991', '264012', '264026', '264061', '282179', '282180', '282186', '282187', '282188', '282190', '282195', '282214', '282217', '282229', '283554']
nosy_count = 10.0
nosy_names = ['rhettinger', 'pitrou', 'scoder', 'vstinner', 'ezio.melotti', 'python-dev', 'serhiy.storchaka', 'yselivanov', 'jstasiak', 'Demur Rumed']
pr_nums = []
priority = 'low'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue23507'
versions = ['Python 3.5']
Activity
serhiy-storchaka commentedon Feb 24, 2015
Currently tuples creating uses free lists. But this optimization is not enough. When reuse cached tuple for arguments of repeatedly called functions, the performance of some builtins can be significantly increased.
The same effect can be achieved for itertools functions.
I don't propose to commit this complicated patch, but these results can be used as a guide to the optimization of tuple creating. It is surprising to me that this patch has any effect at all.
[-]Tuple creation is two slow[/-][+]Tuple creation is too slow[/+]rhettinger commentedon Feb 26, 2015
I had done something like this for zip() long ago and had gotten a nice speed boost. I remember looking at whether it should be applied elsewhere but don't remember why I decided against it.
serhiy-storchaka commentedon Feb 26, 2015
Note the check for Py_REFCNT() == 1. Whithout it the code would be incorrect.
serhiy-storchaka commentedon Feb 26, 2015
Fixed bugs found by Victor. Thank you Victor.
Yes, zip() already uses similar approach.
pitrou commentedon Feb 26, 2015
Maybe we want a facility to create on-stack static-size tuples?
pitrou commentedon Feb 26, 2015
How many functions can benefit from this approach, though?
serhiy-storchaka commentedon Feb 26, 2015
There is no guarantee that called function doesn't save the reference to args.
From hand-writing caching? Any function, that repeatedly call other functions many times. In additional to sorted()/list.sort() with the key argument, filter() and map(), these are min() and max() with the key argument, some iterators from itertools (groupby(), dropwhile(), takewhile(), accumulate(), filterfalse()). May be some functions that are thin wrappers around special method (e.g. round()).
But it is more interesting to investigate why PyTuple_New() is so slow in comparison with hand-written caching. It it can be speeded up, then mauch more code can benefit from this.
pitrou commentedon Apr 13, 2015
By the way, is PyTuple_New() really the culprit here? Or is it the valist handling in PyObject_CallFunctionObjArgs()?
rhettinger commentedon Apr 14, 2015
Unassigning because I don't have an interest in going further down this path. I used this technique with zip() because tuple reuse nicely benefited the common case of "for a,b,c in zip(alist, blist, clist): ...".
On another thread, I did see mention of removing the memset() from tuple creation and that seems like a promising direction.
serhiy-storchaka commentedon Apr 14, 2015
map doesn't use PyObject_CallFunctionObjArgs(). If compare results for map with results for filter and list.sort, seems that PyTuple_New() is responsible for 24% and PyObject_CallFunctionObjArgs() adds other 14%.
6 remaining items
serhiy-storchaka commentedon Dec 1, 2016
Here is an example that shows increased stack consumption.
With old code it counts to 74700, with the patch it counts only to 65400.
Please revert your changes.
vstinner commentedon Dec 1, 2016
I rewrote bench_builtins.py to use my new perf module.
Python 3.7 is between 1.27x and 1.42x faster than Python 3.6, but sorted(list) is slower. I don't know why sorted(list) is slower. It doesn't use a key function, and so should not be impacted by FASTCALL changes made since Python 3.6.
Benchmark results of Python 3.7 (include latest FASTCALL patches) compared to Python 3.5 (no FASTCALL):
filter(lambda x: x, range(1000)): Median +- std dev: [3.5] 126 us +- 7 us -> [3.7] 94.6 us +- 4.8 us: 1.34x faster (-25%)
map(lambda x, y: x+y, range(1000), range(1000)): Median +- std dev: [3.5] 163 us +- 10 us -> [3.7] 115 us +- 7 us: 1.42x faster (-30%)
map(lambda x: x, range(1000)): Median +- std dev: [3.5] 115 us +- 6 us -> [3.7] 90.9 us +- 5.4 us: 1.27x faster (-21%)
sorted(list): Median +- std dev: [3.5] 17.5 us +- 1.0 us -> [3.7] 19.7 us +- 1.1 us: 1.12x slower (+12%)
sorted(list, key=lambda x: x): Median +- std dev: [3.5] 122 us +- 10 us -> [3.7] 91.8 us +- 5.7 us: 1.33x faster (-25%)
Note: you need the development version of perf to run the script (future version 0.9.2).
vstinner commentedon Dec 1, 2016
Serhiy: "I don't propose to commit this complicated patch, but these results can be used as a guide to the optimization of tuple creating. It is surprising to me that this patch has any effect at all."
A new "fast call" calling convention was added to Python 3.6 to avoid the creation of temporary tuples to pass function arguments. Benchmarks confirm that Python 3.7 is faster than Python 3.5 of functions that Serhiy suggested to optimize. I confirm that I was also surprised that fast call has a significant effect on performance!
Fast calls don't require complex code like reuse_argtuples_3.patch which requires to check carefully the reference counter. In the past, a similar optimization on property_descr_get() introduced complex bugs: see issue bpo-24276 and issue bpo-26811. Fast calls don't use such issues.
The implementation of fast calls is currently incomplete: tp_new, tp_init and tp_call slots still require a tuple and a dict for positional and keyword arguments. I'm working on an enhancement for Python 3.7 to support also fast calls for these slots. In the meanwhile, callbacks using tp_call don't benefit yet on fast calls.
That's why I had to keep the tuple/refcount optimization in property_descr_get(), to not introduce a performance regression.
I consider that this issue can now be closed as "fixed".
serhiy-storchaka commentedon Dec 1, 2016
Victor, your changes introduced a regression.
vstinner commentedon Dec 1, 2016
Serhiy Storchaka: "Victor, your changes introduced a regression."
I suppose that you are refering to sorted(list) which seems to be slower. Do you have a specific change in mind? As I wrote, it doesn't use a key function, and so should not be impacted by my work on fast calls. I opened a new issue bpo-28852 to track this performance regression.
vstinner commentedon Dec 2, 2016
So can I close again this issue?
serhiy-storchaka commentedon Dec 2, 2016
No, I'm referring to the crashing. The code that worked before your changes now are crashing. Please revert your changes and find a way to optimize a function calling without increasing stack consumption.
vstinner commentedon Dec 2, 2016
haypo: "status: open -> closed"
Oops, it's a mistake, sorry. I only wanted to ask the question, not to close the issue.
Serhiy Storchaka: "No, I'm referring to the crashing. The code that worked before your changes now are crashing."
Sorry, I didn't notice that you attached a script! I opened the issue bpo-28858.
serhiy-storchaka commentedon Dec 18, 2016
Here is rebased patch (just for history). Caching argtuple is not faster (or even slower) than using fast call.
Regression in stack consumption is fixed in bpo-28858.
Thanks Victor!