Add _PyObject_FastCall()

[vstinner]

BPO	27128
Nosy	@scoder, @vstinner, @serhiy-storchaka, @1st1, @ztane
Files	fastcall.patch default-May26-13-36-33.log fastcall-2.patch fast_call_alt.patch fastcall-3.patch

^{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-09-01.13:13:54.081>
created_at = <Date 2016-05-26.10:15:56.728>
labels = ['performance']
title = 'Add _PyObject_FastCall()'
updated_at = <Date 2016-09-01.13:13:54.079>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2016-09-01.13:13:54.079>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2016-09-01.13:13:54.081>
closer = 'vstinner'
components = []
creation = <Date 2016-05-26.10:15:56.728>
creator = 'vstinner'
dependencies = []
files = ['43011', '43014', '44041', '44079', '44128']
hgrepos = []
issue_num = 27128
keywords = ['patch']
message_count = 32.0
messages = ['266422', '266424', '266429', '266430', '268057', '268059', '272138', '272139', '272197', '272264', '272268', '272479', '272503', '272884', '272887', '272888', '272891', '273136', '273140', '273143', '273144', '273153', '273166', '273175', '273349', '273350', '273351', '273365', '273371', '273388', '273402', '274123']
nosy_count = 6.0
nosy_names = ['scoder', 'vstinner', 'python-dev', 'serhiy.storchaka', 'yselivanov', 'ztane']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue27128'
versions = ['Python 3.6']

[vstinner]

Since the issue bpo-26814 proved that avoiding the creation of temporary tuples to call Python and C functions makes Python faster (between 2% and 29% depending on the benchmark), I extracted a first "minimal" patch to start merging this work.

The first patch adds new functions:

• PyObject_CallNoArg(func) and PyObject_CallArg1(func, arg): public functions
• _PyObject_FastCall(func, args, nargs, kwargs): private function

I hesitate between the C types "int" and "Py_ssize_t" for nargs. I read once that using "int" can cause performance issues on a loop using "i++" and "data[i]" because the compiler has to handle integer overflow of the int type.

The "int" type is also annoying on Windows 64-bit, it causes compiler warnings on downcast like PyTuple_GET_SIZE(co->co_argcount) stored into a C int.

_PyObject_FastCall() avoids the creation of tuple for:

• All Python functions (PyFunction_Check)
• C functions using METH_NOARGS or METH_O

The patch removes the "cache tuple" optimization from property_descr_get(), it uses PyObject_CallArg1() instead. It means that the optimization is (currently) missed in some cases compared to the current code, but the code is safer and simpler.

The patch adds Python/pystack.c which currently only contains _PyStack_AsTuple(), but will contain more code later.

I tried to write the smallest patch, but I started to use PyObject_CallNoArg() and PyObject_CallArg1() when the code already created a tuple at each call: PyObject_CallObject(), call_function_tail() and PyEval_CallObjectWithKeywords().

In the patch, keywords are not used in fast calls. But they will be used later. I prefer to start directly with keywords than changing the calling convention once again later.

--

Later, I will propose other patches to:

• add METH_FASTCALL calling convention for C functions
• modify Argument Clinic to use METH_FASTCALL

So the fast call will be taken in more cases.

--

The long term plan is to slowly use the new FASTCALL calling convention "everywhere". The tricky point are tp_new, tp_init and tp_call attributes of type objects. In the issue bpo-26814, I wrote a patch adding Py_TPFLAGS_FASTNEW, Py_TPFLAGS_FASTINIT and Py_TPFLAGS_FASTCALL flags to use the FASTCALL calling convention for tp_new, tp_init and tp_call. The problem is that calling directly these methods looks common. If we can the calling convention of these methods, it will break the C API, I propose to discuss that later ;-)

An alternative is to add a tp_fastcall method to PyTypeObject and use a wrapper for tp_call for backward compatibility. This option has also drawbacks. Again, I propose to discuss this later, and first start to focus on the changes that don't break anything ;-)

[vstinner]

Quick & dirty microbenchmark: I ran bench_fast-2.py of the issue bpo-26814. It looks like everything is slower :-p In fact, I already noticed this issue and I think that it is fixed with better compilation option: use "./configure --with-lto" and "make profile-opt". See my article:
https://haypo.github.io/journey-to-stable-benchmark-deadcode.html

----------------------------------+-------------+---------------
Tests | original | fastcall
----------------------------------+-------------+---------------
filter | 76.2 us () | 116 us (+52%)
map | 73.6 us () | 102 us (+38%)
sorted(list, key=lambda x: x) | 82 us () | 121 us (+48%)
sorted(list) | 14.7 us () | 17.3 us (+18%)
b=MyBytes(); bytes(b) | 182 ns () | 243 ns (+33%)
namedtuple.attr | 802 ns () | 1.44 us (+80%)
object.__setattr__(obj, "x", 1) | 133 ns () | 166 ns (+25%)
object.__getattribute__(obj, "x") | 116 ns () | 142 ns (+22%)
getattr(1, "real") | 76 ns () | 95 ns (+25%)
bounded_pymethod(1, 2) | 72 ns () | 102 ns (+42%)
unbound_pymethod(obj, 1, 2) | 71 ns () | 99 ns (+38%)
func() | 57 ns () | 81 ns (+41%)
func(1, 2, 3) | 72 ns () | 100 ns (+39%)
----------------------------------+-------------+---------------
Total | 248 us () | 358 us (+44%)
----------------------------------+-------------+---------------

At least, we have a starting point ;-)

[vstinner]

default-May26-13-36-33.log: CPython benchmark suite run using stable config.

Faster (15):

• regex_effbot: 1.26x faster
• telco: 1.08x faster
• unpack_sequence: 1.07x faster
• mako_v2: 1.05x faster
• meteor_contest: 1.05x faster
• chaos: 1.04x faster
• nbody: 1.04x faster
• call_method_slots: 1.04x faster
• etree_iterparse: 1.04x faster
• etree_parse: 1.04x faster
• call_method: 1.03x faster
• raytrace: 1.03x faster
• nqueens: 1.03x faster
• call_method_unknown: 1.03x faster
• formatted_logging: 1.02x faster

Slower (8):

• etree_generate: 1.05x slower
• etree_process: 1.03x slower
• call_simple: 1.03x slower
• chameleon_v2: 1.02x slower
• pathlib: 1.02x slower
• float: 1.02x slower
• silent_logging: 1.02x slower
• json_load: 1.02x slower

[vstinner]

Updated bench_fast-2.py result with Python compiled with PGO+LTO, with benchmark.py fixed to compute average + standard deviation. Only getattr() really seems slower:

----------------------------------+-----------------------+--------------------------
Tests | original | fastcall
----------------------------------+-----------------------+--------------------------
filter | 75.8 us +- 0.1 us () | 78.1 us +- 0.1 us
map | 72.6 us +- 0.1 us () | 71.4 us +- 0.0 us
sorted(list, key=lambda x: x) | 83.7 us +- 0.1 us () | 82.3 us +- 0.3 us
sorted(list) | 14.9 us +- 0.0 us () | 14.7 us +- 0.0 us
b=MyBytes(); bytes(b) | 199 ns +- 2 ns () | 194 ns +- 1 ns
namedtuple.attr | 830 ns +- 20 ns () | 1.09 us +- 0.01 us (+31%)
object.__setattr__(obj, "x", 1) | 133 ns +- 0 ns () | 134 ns +- 1 ns
object.__getattribute__(obj, "x") | 117 ns +- 0 ns () | 115 ns +- 1 ns
getattr(1, "real") | 93.2 ns +- 0.9 ns () | 76.9 ns +- 0.7 ns (-17%)
bounded_pymethod(1, 2) | 73.4 ns +- 0.6 ns () | 70.7 ns +- 0.4 ns
unbound_pymethod(obj, 1, 2) | 74.5 ns +- 0.2 ns () | 71.8 ns +- 0.6 ns
func() | 60.2 ns +- 0.4 ns () | 59.3 ns +- 0.1 ns
func(1, 2, 3) | 74.6 ns +- 0.4 ns () | 72.2 ns +- 0.3 ns
----------------------------------+-----------------------+--------------------------
Total | 249 us () | 248 us
----------------------------------+-----------------------+--------------------------

[serhiy-storchaka]

See bpo-27213. Maybe fast call with keyword arguments would avoid the creation of a dict.

[vstinner]

Serhiy Storchaka added the comment:

See bpo-27213. Maybe fast call with keyword arguments would avoid the creation of a dict.

In a first verison of my implementation, I used dictionary items
stored a a list of (key, value) tuples in the same PyObject* C array
than positional parameters.

But in practice, it's very rare in the C code base to have to call a
function with keyword parameters, but most functions expect keyword
parameters as a dict. They are implemented with
PyArg_ParseTupleAndKeywords() which expects a dict.

[vstinner]

Rebased patch.

[vstinner]

(Oops, I removed a broken fastcall-2.patch which didn't include new pystack.c/pystack.h files. It's now fixed in the new fastcall-2.patch.)

[vstinner]

I spent the last 3 months on making the CPython benchmark suite more stable and enhance my procedure to run benchmarks to ensure that benchmarks are more stable.

See my articles:
https://haypo-notes.readthedocs.io/microbenchmark.html#my-articles

I forked and enhanced the benchmark suite to use my perf module to run benchmarks in multiple processes:
https://hg.python.org/sandbox/benchmarks_perf

I ran this better benchmark suite on fastcall-2.patch on my laptop. The result is quite good:
----------------

$ python3 -m perf compare_to ref.json fastcall.json -G  --min-speed=5
Slower (4):
- fastpickle/pickle_dict: 326 us +- 15 us -> 350 us +- 29 us: 1.07x slower
- regex_effbot: 49.4 ms +- 1.3 ms -> 53.0 ms +- 1.2 ms: 1.07x slower
- fastpickle/pickle: 432 us +- 8 us -> 457 us +- 10 us: 1.06x slower
- pybench.ComplexPythonFunctionCalls: 838 ns +- 11 ns -> 884 ns +- 8 ns: 1.05x slower

Faster (13):

• spectral_norm: 289 ms +- 6 ms -> 250 ms +- 5 ms: 1.16x faster
• pybench.SimpleIntFloatArithmetic: 622 ns +- 9 ns -> 559 ns +- 10 ns: 1.11x faster
• pybench.SimpleIntegerArithmetic: 621 ns +- 10 ns -> 560 ns +- 9 ns: 1.11x faster
• pybench.SimpleLongArithmetic: 891 ns +- 12 ns -> 816 ns +- 10 ns: 1.09x faster
• pybench.DictCreation: 852 ns +- 13 ns -> 788 ns +- 16 ns: 1.08x faster
• pybench.ForLoops: 10.8 ns +- 0.3 ns -> 9.99 ns +- 0.23 ns: 1.08x faster
• pybench.NormalClassAttribute: 1.85 us +- 0.02 us -> 1.72 us +- 0.04 us: 1.08x faster
• pybench.SpecialClassAttribute: 1.86 us +- 0.02 us -> 1.73 us +- 0.03 us: 1.07x faster
• pybench.NestedForLoops: 21.9 ns +- 0.3 ns -> 20.7 ns +- 0.3 ns: 1.05x faster
• pybench.SimpleListManipulation: 501 ns +- 4 ns -> 476 ns +- 5 ns: 1.05x faster
• elementtree/process: 192 ms +- 3 ms -> 183 ms +- 2 ms: 1.05x faster
• elementtree/generate: 225 ms +- 5 ms -> 214 ms +- 4 ms: 1.05x faster
• hexiom2/level_25: 21.3 ms +- 0.3 ms -> 20.3 ms +- 0.1 ms: 1.05x faster

Benchmark hidden because not significant (84): (...)
----------------

Most benchmarks are not significant which is expected since fastcall-2.patch is really the most simple patch to start the work on "FASTCALL", it doesn't really implement any optimization, it only adds a new infrastructure to implement new optimizations.

A few benchmarks are faster (only benchmarks at least 5% faster are shown using --min-speed=5).

4 benchmarks are slower, but the slowdown should be temporarily: new optimizations should these benchmarks slower. See the issue bpo-26814 for more a concrete implementation and a lot of benchmark results if you don't trust me :-)

I consider that benchmarks proved that there is no major slowdown, so fastcall-2.patch can be merged to be able to start working on real optimizations.

[serhiy-storchaka]

Benchmarking results look nice, but despite the fact that this patch is only small part of bpo-26814, it looks to me larger that it could be.

1. The patch includes two parts: adding _PyObject_FastCall() and adding PyObject_CallNoArg() and PyObject_CallArg1(). How large the role of latter functions in the speed up? Can we first just add _PyObject_FastCall() and measure the effect of adding PyObject_CallNoArg() and PyObject_CallArg1() separately? Can existing function PyObject_Call() be optimized to achieve a comparable benefit?

2. I think that supporting keyword arguments in _PyObject_FastCall() doesn't make much sense now. Calling with keyword arguments adds such much overhead, that it dwarfs the benefit of avoiding the creation of one tuple. I think that the patch can be simpler if drop the support of keyword arguments.

3. The patch adds two files for one function _PyStack_AsTuple(). I would prefer something like _PyTuple_FromArray(). It could be used in other places, not just in argument parsing.

[vstinner]

Benchmarking results look nice, but despite the fact that this patch is
only small part of bpo-26814, it looks to me larger that it could be.

Oh I failed to express my intent. This initial patch is not expected to
introduce any speedup. In fact I noticed major performance regressions on
the CPython benchmark suite using my full fastcall patch. It took me time
to understand that they are more issues with benchmarks than my work. This
minimum patch only adds new functions but don't really use them. I patched
a few functions to show how the new functions can be used. I spent most of
my time just to ensure that the minimum patch doesn't introduce performance
regression.

1. The patch includes two parts: adding _PyObject_FastCall() and adding
   PyObject_CallNoArg() and PyObject_CallArg1(). How large the role of latter
   functions in the speed up?

See my remark above, no speedup is expected.

Do you suggest to not add these 2 new functions? Since they are well
defined and simple, I chose to make them public. Their API is nicer than
_PyObject_Call().

Can existing function PyObject_Call() be optimized to achieve a
comparable benefit?

Sorry, I don't understand. This function requires a tuple. The whole
purpose of my patch is to avoid temporary tuples.

In my full patch, PyObject_Call() calls _PyObject_FastCall() in most cases.

2. I think that supporting keyword arguments in _PyObject_FastCall()
   doesn't make much sense now.

Well, I can add support for keyword arguments later and start with an
assertion (fail if they are used). But I really need them in the API, and I
don't want to change to API later.

I plan to add a new METH_FASTCALL calling convention for C functions. I
would prefer to not have two new calling conventions, but use Argument
Clinic to emit efficient code to parse arguments.

Calling with keyword arguments adds such much overhead, that it dwarfs
the benefit of avoiding the creation of one tuple. I think that the patch
can be simpler if drop the support of keyword arguments.

Keyword arguments are optional. Having support for them cost nothing when
they are not used.

3. The patch adds two files for one function _PyStack_AsTuple(). I would
   prefer something like _PyTuple_FromArray(). It could be used in other
   places, not just in argument parsing.

I really want to have a "pystack" API. In this patch, the new file looks
useless, but in the full patch there are many functions including a few
complex functions. I prefer to add the file now and complete it later.

I'm limited by Mercurial and our workflow (tools), it would be much easier
to explain my work using a patch serie, but it's not possible to publish a
patch serie...

[serhiy-storchaka]

Do you suggest to not add these 2 new functions?

Yes, I suggest to not add them. The API for calling is already too large.
Internally we can directly use _PyObject_FastCall(), and third party code
should get benefit from optimized PyObject_CallFunctionObjArgs().

> Can existing function PyObject_Call() be optimized to achieve a
> comparable benefit?
Sorry, I don't understand. This function requires a tuple. The whole
purpose of my patch is to avoid temporary tuples.

Sorry, I meant PyObject_CallFunctionObjArgs() and like.

Keyword arguments are optional. Having support for them cost nothing when
they are not used.

My point is that if keyword arguments are used, this is not a fast call, and
should use old calling protocol. The overhead of creating a tuple for args is
dwarfen by the overhead of creating a dict for kwargs and parsing it.

I really want to have a "pystack" API. In this patch, the new file looks
useless, but in the full patch there are many functions including a few
complex functions. I prefer to add the file now and complete it later.

But for now there is no a "pystack" API. What do you want to add? Can it be
added with prefixes PyDict_, PyArg_ or PyEval_? On other side, other code can
get a benefit from using _PyTuple_FromArray().

Here is alternative simplified patch.

1. _PyStack_AsTuple() is renamed to _PyTuple_FromArray() (-2 new files).
2. Optimized PyObject_CallFunctionObjArgs(), PyObject_CallMethodObjArgs() and
   _PyObject_CallMethodIdObjArgs().
3. Removed PyObject_CallNoArg() and PyObject_CallArg1(). Invocations are
   replaced by PyObject_CallFunctionObjArgs().
4. Removed support of keyword arguments in _PyObject_FastCall() (saved about
   20 lines and few runtime checks in _PyCFunction_FastCall).
5. Reverted changes in Objects/descrobject.c. They added a regression in
   namedtuple attributes access.

[ztane]

About "I hesitate between the C types "int" and "Py_ssize_t" for nargs. I read once that using "int" can cause performance issues on a loop using "i++" and "data[i]" because the compiler has to handle integer overflow of the int type."

This is true because of -fwrapv, but I believe it is true also for Py_ssize_t which is also of signed type. However, there would be a speed-up achievable by disabling -fwrapv, because only then the i++; data[i] can be safely optimized into *(++data)

[vstinner]

Serhiy Storchaka added the comment:

> Do you suggest to not add these 2 new functions?

Yes, I suggest to not add them. The API for calling is already too large.
Internally we can directly use _PyObject_FastCall(), and third party code
should get benefit from optimized PyObject_CallFunctionObjArgs().

Well, we can start without them, and see later if it's worth it.

I didn't propose to add new functions to make the code faster, but to
make the API simpler.

I dislike PyEval_CallObjectWithKeywords(func, arg, kw) because it has
a special case if arg is a tuple. If arg is a tuple, the tuple is
unpacked. It already leaded to a complex and very bug in the
implementation of generators! See the issue bpo-21209. I'm not sure that
such use case is well known and understood by everyone...

It's common to call a function with no argument or just one argument,
so I proposed to add an obvious and simple API for these common cases.
Well, again, I will open a new issue to discuss that.

> > Can existing function PyObject_Call() be optimized to achieve a
> > comparable benefit?
> Sorry, I don't understand. This function requires a tuple. The whole
> purpose of my patch is to avoid temporary tuples.

Sorry, I meant PyObject_CallFunctionObjArgs() and like.

Yes, my full patch does optimize these functions:
https://hg.python.org/sandbox/fastcall/file/2dc558e01e66/Objects/abstract.c#l2523

> Keyword arguments are optional. Having support for them cost nothing when
> they are not used.

My point is that if keyword arguments are used, this is not a fast call, and
should use old calling protocol. The overhead of creating a tuple for args is
dwarfen by the overhead of creating a dict for kwargs and parsing it.

I'm not sure that I understand your point.

For example, in my full patch, I have a METH_FASTCALL calling
convention for C functions. With this calling convention, a function
accepts positional arguments and keyword arguments. If you don't pass
keyword arguments, the call should be faster according to my
benchmarks.

How do you want to implement METH_FASTCALL if you cannot pass keyword
arguments? Does it mean that METH_FASTCALL can only be used by the
functions which don't accept keyword arguments at all?

It's ok if passing keyword arguments is not faster, but simply as fast
as before, if the "positional arguments only" case is faster, no?

> I really want to have a "pystack" API. In this patch, the new file looks
> useless, but in the full patch there are many functions including a few
> complex functions. I prefer to add the file now and complete it later.

But for now there is no a "pystack" API. What do you want to add?

See my fastcall branch:

https://hg.python.org/sandbox/fastcall/file/2dc558e01e66/Include/pystack.h
https://hg.python.org/sandbox/fastcall/file/2dc558e01e66/Python/pystack.c

All these functions are private. They are used internally to implement
all functions of the Python C API to call functions.

On other side, other code can get a benefit from using _PyTuple_FromArray().

Ah? Maybe you should open a different issue for that.

I prefer to have an API specific to build a "stack" to call functions.

Here is alternative simplified patch.

1. _PyStack_AsTuple() is renamed to _PyTuple_FromArray() (-2 new files).
2. Optimized PyObject_CallFunctionObjArgs(), PyObject_CallMethodObjArgs() and
   _PyObject_CallMethodIdObjArgs().

My full patch does optimize "everything", it's deliberate to start
with something useless but short.

5. Reverted changes in Objects/descrobject.c. They added a regression in
   namedtuple attributes access.

Ah? What is the regression?