Avoid copy in call_function_var when no extra stack args are passed

[llllllllll]

BPO	26802
Nosy	@vstinner, @vadmium, @serhiy-storchaka, @1st1, @MojoVampire, @llllllllll
Files	call-function-var.patch call-function-var.patch call-function-var-3.patch bench.py

^{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-04-19.20:47:10.666>
created_at = <Date 2016-04-19.01:10:12.132>
labels = ['interpreter-core', 'performance']
title = 'Avoid copy in call_function_var when no extra stack args are passed'
updated_at = <Date 2016-04-20.07:55:49.849>
user = 'https://github.com/llllllllll'

bugs.python.org fields:

activity = <Date 2016-04-20.07:55:49.849>
actor = 'vstinner'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2016-04-19.20:47:10.666>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2016-04-19.01:10:12.132>
creator = 'llllllllll'
dependencies = []
files = ['42512', '42515', '42521', '42524']
hgrepos = []
issue_num = 26802
keywords = ['patch']
message_count = 20.0
messages = ['263702', '263712', '263717', '263741', '263742', '263750', '263751', '263754', '263765', '263770', '263771', '263772', '263774', '263775', '263777', '263778', '263782', '263784', '263808', '263809']
nosy_count = 7.0
nosy_names = ['vstinner', 'python-dev', 'martin.panter', 'serhiy.storchaka', 'yselivanov', 'josh.r', 'llllllllll']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue26802'
versions = ['Python 3.6']

[llllllllll]

When star unpacking positions into a function we can avoid a copy iff there are no extra arguments coming from the stack. Syntactically this looks like: f(*args)

This reduces the overhead of the call by about 25% (~30ns on my machine) based on some light profiling of just * unpacking. I can imagine this having a slight impact on code that uses this feature in a loop.

The cost is minimal when we need to make the copy because the int != 0 check is dwarfed by the allocation. I did not notice a significant change between the slow path and the original code.

The macro benchmark suite did not show a difference on my machine but this is not much more complex code.

[serhiy-storchaka]

stararg can be not exact tuple, but an instance of tuple subclass.

Could you provide a microbenchmark that shows the effect of the optimization?

[llllllllll]

in _PyEval_EvalCodeWithName we will have already pulled the underlying array out of the tuple subclass and the then we will reconstruct the vararg value in the locals from this array. This means that with this patch we can get:

>>> class C(tuple): pass
... 
>>> def f(*args): print(type(args))
... 
>>> f(*C([1, 2, 3]))
<class 'tuple'>

The only case where we get potentially strange behavior is if we have a type whose tp_call did not forward to PyArg_Parse* or the PyTupleObject api and went though the abstract object interface. I ran the tests and the benchmark suite and did not run into any issues here but I can see how this would be potentially problematic behavior.

I have updated the code to also do a PyTuple_CheckExact against stararg. The tests I ran are:

timeit("h(*(a, b, c, d, e, f, g))", 'def h(a, b, c, d, e, f, g): pass\na, b, c, d, e, f, g = range(7)', number=int(10e7))

default: 17.191688070015516
patch: 14.060781285981648

There is also a really great case where you star unpack a tuple of literals which gets pushed into the co_consts:

timeit("f(*('a', 'b', 'c', 'd', 'e', 'f', 'g'))", 'def f(a, b, c, d, e, f, g): pass', number=int(10e7))

default: 13.842308042978402
patch: 9.696972723002546

This case seems far less common, but maybe someone has something like:

a = 1, 2, 3
...
f(*a)

[vstinner]

+ if (!nstar) {
+ /* There are no positional arguments on the stack or in in a
+ sequence that was unpacked. */
+ return PyTuple_New(0);
+ }

It's possible that stararg is already an empty tuple. Is it worth to use it?

+ if (!nstar) {
+ if (stararg != NULL && PyTuple_CheckExact(stararg)) {
+ Py_INCREF(stararg);
+ return stararg;
+ }
+ else {
+ /* There are no positional arguments on the stack or in in a
+ sequence that was unpacked. */
+ return PyTuple_New(0);
+ }
+ }

[vstinner]

call-function-var.patch LGTM.

[vstinner]

FYI I ran the full test suite with the second attached patch and all tests pass.

By the way, please add a suffix like -2, -3, etc. to your patches next time. It's easier to identify them if they have a different name ;-)

[llllllllll]

It's possible that stararg is already an empty tuple. Is it worth to use it?

PyTuple_New(0) should return the unit tuple in most cases:

#if PyTuple_MAXSAVESIZE > 0
    if (size == 0 && free_list[0]) {
        op = free_list[0];
        Py_INCREF(op);
#ifdef COUNT_ALLOCS
        tuple_zero_allocs++;
#endif
        return (PyObject *) op;
    }

Looking at this again I think that checking if stararg is nonnull is more clear, I will update the patch (as call-function-var-3.patch). I cannot exactly rewrite the if to use the control flow you show because that would cause non-tuple subclasses to forward a stararg of () instead of copying it into a normal tuple when no arguments are passed ont the stack.

[MojoVampire]

BTW, for a realistic use case that would be sped up by this patch (possibly a lot), consider a recursive function that is continually doing a "virtual" pop of the first argument, and receiving the rest as varargs, which are then unpacked for the recursive call, e.g., a function to make a multidimensional list populated with zeroes:

    def nestedzeroes(firstdim, *dims):
        '''Make multidimensional list populated with 0s'''
        if not dims:
            return [0] * firstdim
        return [nestedzeroes(*dims) for _ in range(firstdim)]

It's somewhat less artificial in that it multiplies the effect of the optimization in a way that would actually exercise a microbenchmark-like scenario, where the amount of work involved in the star-args-only function calls is an appreciable percentage of the work. Running nestedzeroes(5, 5, 5) to create a 5x5x5 structure would involve 30 recursive calls; for nestedzeroes(10, 10, 10), 110 recursive calls.

I've actually used code like this (admittedly rarely) to avoid the hassle of inlining a many times nested set of list comprehensions to initialize a multidimensional list.

[serhiy-storchaka]

call-function-var-3.patch LGTM. Thank you for your contribution Joe.