classification
Title: Use FASTCALL in typeobject.c call_method() to avoid temporary tuple
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: haypo, inada.naoki, python-dev, rhettinger, serhiy.storchaka, yselivanov
Priority: normal Keywords: patch

Created on 2017-02-09 00:17 by haypo, last changed 2017-03-14 21:38 by haypo. This issue is now closed.

Files
File name Uploaded Description Edit
method_fastcall.patch haypo, 2017-02-09 00:17 review
callmethod.patch inada.naoki, 2017-02-09 10:37 review
method_fastcall2.patch inada.naoki, 2017-02-09 12:20 review
method_fastcall3.patch inada.naoki, 2017-02-09 14:04 review
method_fastcall4.patch haypo, 2017-02-09 16:27 review
bench.py haypo, 2017-02-09 16:27
callmethod2.patch inada.naoki, 2017-02-09 23:27 review
callmethod3.patch inada.naoki, 2017-02-10 08:19 review
Messages (30)
msg287371 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 00:17
Subset of the (almost) rejected issue #29259 (tp_fastcall), attached patch adds _PyMethod_FastCall() and uses it in call_method() of typeobject.c. The change avoids the creation of a temporary tuple for Python functions and METH_FASTCALL C functions.

Currently, call_method() calls method_call() which calls _PyObject_Call_Prepend(), and calling method_call() requires a tuple for positional arguments.

Example of benchmark on __getitem__(): 1.3x faster (-22%).

$ ./python -m perf timeit -s 'class C:' -s ' def __getitem__(self, index): return index' -s 'c=C()' 'c[0]' 

Median +- std dev: 130 ns +- 1 ns => 102 ns +- 1 ns


See also the issue #29263 "Implement LOAD_METHOD/CALL_METHOD for C functions".
msg287372 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 00:19
Maybe PyObject_Call(), _PyObject_FastCallDict(), etc. can also be modified to get the following fast-path:

+    if (Py_TYPE(func) == &PyMethod_Type) {
+        result = _PyMethod_FastCall(func, args, nargs);
+    }

But I don't know how common it is to get a PyMethod_Type object in these functions, nor the code of the additional if.
msg287387 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-09 08:08
Maybe, we can skip Method object entirely using _PyObject_GetMethod().
Currently it is used only in LOAD_METHOD.
But PyObject_CallMethod(), _PyObject_CallMethodId(), PyObject_CallMethodObjArgs(), _PyObject_CallMethodIdObjArgs() can use it too.
msg287399 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-09 10:37
> But PyObject_CallMethod(), _PyObject_CallMethodId(), PyObject_CallMethodObjArgs(), _PyObject_CallMethodIdObjArgs() can use it too.

CallMethod[Id]ObjArgs() can use it easily.
But format support is not so easy.
msg287401 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-09 11:00
callmethod.patch:

+ ../python.default -m perf compare_to default.json patched2.json -G --min-speed=1
Slower (5):
- logging_silent: 717 ns +- 9 ns -> 737 ns +- 8 ns: 1.03x slower (+3%)
- fannkuch: 1.04 sec +- 0.01 sec -> 1.06 sec +- 0.02 sec: 1.02x slower (+2%)
- call_method: 14.5 ms +- 0.1 ms -> 14.7 ms +- 0.1 ms: 1.02x slower (+2%)
- call_method_slots: 14.3 ms +- 0.3 ms -> 14.6 ms +- 0.1 ms: 1.02x slower (+2%)
- scimark_sparse_mat_mult: 8.66 ms +- 0.21 ms -> 8.76 ms +- 0.25 ms: 1.01x slower (+1%)

Faster (17):
- scimark_lu: 433 ms +- 28 ms -> 410 ms +- 24 ms: 1.06x faster (-5%)
- unpickle: 32.9 us +- 0.2 us -> 31.7 us +- 0.3 us: 1.04x faster (-4%)
- sqlite_synth: 10.0 us +- 0.2 us -> 9.77 us +- 0.24 us: 1.03x faster (-3%)
- telco: 21.1 ms +- 0.7 ms -> 20.6 ms +- 0.4 ms: 1.03x faster (-2%)
- unpickle_list: 8.22 us +- 0.18 us -> 8.02 us +- 0.17 us: 1.03x faster (-2%)
- json_dumps: 30.3 ms +- 0.8 ms -> 29.6 ms +- 0.4 ms: 1.02x faster (-2%)
- nbody: 245 ms +- 6 ms -> 240 ms +- 5 ms: 1.02x faster (-2%)
- meteor_contest: 207 ms +- 2 ms -> 203 ms +- 2 ms: 1.02x faster (-2%)
- scimark_fft: 738 ms +- 14 ms -> 727 ms +- 17 ms: 1.02x faster (-2%)
- pickle_pure_python: 1.27 ms +- 0.02 ms -> 1.25 ms +- 0.02 ms: 1.01x faster (-1%)
- django_template: 401 ms +- 4 ms -> 395 ms +- 5 ms: 1.01x faster (-1%)
- sqlalchemy_declarative: 317 ms +- 3 ms -> 313 ms +- 4 ms: 1.01x faster (-1%)
- json_loads: 64.2 us +- 1.0 us -> 63.4 us +- 1.0 us: 1.01x faster (-1%)
- nqueens: 270 ms +- 2 ms -> 267 ms +- 2 ms: 1.01x faster (-1%)
- crypto_pyaes: 234 ms +- 1 ms -> 231 ms +- 3 ms: 1.01x faster (-1%)
- chaos: 300 ms +- 2 ms -> 297 ms +- 4 ms: 1.01x faster (-1%)
- sympy_expand: 1.01 sec +- 0.01 sec -> 1.00 sec +- 0.01 sec: 1.01x faster (-1%)

Benchmark hidden because not significant (42)
msg287410 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-09 12:20
I'm sorry, callmethod.patch is tuned other place, and causing SEGV.

method_fastcall2.patch is tuning same function (call_method() in typeobject.c), and uses trick to bypass temporary method object (same to _PyObject_GetMethod()).

$ ./python -m perf timeit --compare-to `pwd`/python.default  -s 'class C:' -s ' def __getitem__(self, index): return index' -s 'c=C()' 'c[0]'
python.default: ..................... 155 ns +- 4 ns
python: ..................... 111 ns +- 1 ns

Median +- std dev: [python.default] 155 ns +- 4 ns -> [python] 111 ns +- 1 ns: 1.40x faster (-28%)
msg287413 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 12:39
> method_fastcall2.patch is tuning same function (call_method() in typeobject.c), and uses trick to bypass temporary method object (same to _PyObject_GetMethod()).

Oh, great idea! That's why I put you in the nosy list ;-) You know better than me this area of the code.

> Median +- std dev: [python.default] 155 ns +- 4 ns -> [python] 111 ns +- 1 ns: 1.40x faster (-28%)

Wow, much better than my patch. Good job!

Can we implement the same optimization in callmethod() of Objects/abstract.c? Maybe add a "is_method" argument to the static function _PyObject_CallFunctionVa(), to only enable the optimization for callmehod().
msg287418 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-09 14:04
method_fastcall3.patch implement the trick in more general way.
(I haven't ran test yet since it's midnight.  I'll post result later.)
msg287436 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 16:27
method_fastcall4.patch: Based on method_fastcall3.patch, I just added call_unbound() and call_unbound_noarg() helper functions to factorize code. I also modified mro_invoke() to be able to remove lookup_method().

I confirm the speedup with attached bench.py:

Median +- std dev: [ref] 121 ns +- 5 ns -> [patch] 82.8 ns +- 1.0 ns: 1.46x faster (-31%)
msg287439 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-09 17:44
method_fastcall4.patch looks clean enough, and performance benefit seems nice.

I don't know current test suite covers unusual special methods.
Maybe, we can extend test_class to cover !unbound (e.g. @classmethod) case.
msg287440 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 17:50
method_fastcall4.patch benchmark results. It's not the first time that I notice that fannkuch and nbody benchmarks become slower. I guess that it's effect of changing code placement because of unrelated change in the C code.

Results don't seem significant on such macro benchmarks (may be random performance changes due to code placement). IMHO the change is worth it! "1.46x faster (-31%)" on a microbenchmark is significant and the change is small.

$ python3 -m perf compare_to /home/haypo/benchmarks/2017-02-08_15-49-default-f507545ad22a.json method_fastcall4_ref_f507545ad22a.json -G --min-speed=5
Slower (2):
- fannkuch: 900 ms +- 20 ms -> 994 ms +- 10 ms: 1.10x slower (+10%)
- nbody: 215 ms +- 3 ms -> 228 ms +- 4 ms: 1.06x slower (+6%)

Faster (3):
- scimark_lu: 357 ms +- 23 ms -> 298 ms +- 8 ms: 1.19x faster (-16%)
- scimark_sor: 400 ms +- 11 ms -> 355 ms +- 12 ms: 1.12x faster (-11%)
- raytrace: 1.05 sec +- 0.01 sec -> 984 ms +- 15 ms: 1.07x faster (-6%)

Benchmark hidden because not significant (59): (...)
msg287453 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-02-09 20:45
+1 Though this is a rather large and impactful patch, I think it is a great idea.  It will be one of the highest payoff applications of FASTCALL, broadly benefitting a lot of code.

Let's be sure to be extra careful with this one because it is touching central parts of the language, so any errors or subtle behavior changes will be felt by a lot of code, some of which is sure to hit the rare corner cases and to rely on implementation details.
msg287460 - (view) Author: Roundup Robot (python-dev) Date: 2017-02-09 22:00
New changeset 7b8df4a5d81d by Victor Stinner in branch 'default':
Optimize slots: avoid temporary PyMethodObject
https://hg.python.org/cpython/rev/7b8df4a5d81d
msg287461 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 22:14
Raymond Hettinger: "+1 Though this is a rather large and impactful patch, I think it is a great idea.  It will be one of the highest payoff applications of FASTCALL, broadly benefitting a lot of code."

In my experience, avoiding temporary tuple to pass positional arguments provides a speedup to up 30% faster in the best case. Here it's 1.5x faster because the optimization also avoids the creation of temporary PyMethodObject.


"Let's be sure to be extra careful with this one because it is touching central parts of the language, so any errors or subtle behavior changes will be felt by a lot of code, some of which is sure to hit the rare corner cases and to rely on implementation details."

I reviewed Naoki's patch carefully, but in fact it isn't as big as I expected.

In Python 3.6, call_method() calls tp_descr_get of PyFunction_Type which creates PyMethodObject. The tp_call of PyMethodObject calls the function with self, nothing crazy.

The patch removes a lot of steps and (IMHO) makes the code simpler than before (when calling Python methods).

I'm not saying that such change is bugfree-proof :-) But we are far from Python 3.7 final, so it's the right time to push such large optimization.
msg287462 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 22:22
Naoki: "method_fastcall4.patch looks clean enough, and performance benefit seems nice."

Ok, I pushed the patch with minor changes:

* replace "variants:" with "Variants:"
* rename lookup_maybe_unbound() to lookup_maybe_method()
* rename lookup_method_unbound() to lookup_method()


"I don't know current test suite covers unusual special methods."

What do you mean by "unusual special methods"?


"Maybe, we can extend test_class to cover !unbound (e.g. @classmethod) case."

It's hard to test all cases, since they are a lot of function types in Python, and each slot (wrapper in typeobject.c) has its own C implementation.

But yeah, in general more tests don't harm :-)

Since the patch here optimizes the most common case, a regular method implemented in Python, I didn't add a specific test with the change. This case is already very well tested, like everything in the stdlib, no?

--

I tried to imagine how we could avoid temporary method objects in more cases like Python class methods (using @classmethod), but I don't think that it's worth it.

It would require more complex code for a less common case. Or do someone see other common cases which would benefit of a similar optimization?
msg287463 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2017-02-09 22:25
patch looks good to me.
msg287464 - (view) Author: Roundup Robot (python-dev) Date: 2017-02-09 22:51
New changeset be663c9a9e24 by Victor Stinner in branch 'default':
Issue #29507: Update test_exceptions
https://hg.python.org/cpython/rev/be663c9a9e24
msg287465 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 23:12
Oh, I was too lazy to run the full test suite, I only ran a subset and I was bitten by buildbots :-) test_unraisable() of test_exceptions fails. IHMO the BrokenRepr subtest on this test function is really implementation specific.

To fix buildbots, I removed the BrokenRepr unit test, but kept the other cases on test_unraisable(): change be663c9a9e24. See my commit message for the full rationale.

In fact, the patch changed the error message logged when a destructor fails. Example:
---
class Obj:
    def __del__(self):
        raise Exception("broken del")

    def __repr__(self):
        return "<useful repr>"

obj = Obj()
del obj
---

Before, contains "<useful repr>":
---
Exception ignored in: <bound method Obj.__del__ of <useful repr>>
Traceback (most recent call last):
  File "x.py", line 3, in __del__
    raise Exception("broken del")
Exception: broken del
---

After, "<useful repr>" is gone:
---
Exception ignored in: <function Obj.__del__ at 0x7f10294c3110>
Traceback (most recent call last):
  File "x.py", line 3, in __del__
    raise Exception("broken del")
Exception: broken del
---


There is an advantage. The error message is now better when repr(obj) fails. Example:
---
class Obj:
    def __del__(self):
        raise Exception("broken del")

    def __repr__(self):
        raise Excepiton("broken repr")

obj = Obj()
del obj
---

Before, raw "<object repr() failed>" with no information on the type:
---
Exception ignored in: <object repr() failed>
Traceback (most recent call last):
  File "x.py", line 3, in __del__
    raise Exception("broken del")
Exception: broken del
---

After, the error message includes the type:
---
Exception ignored in: <function Obj.__del__ at 0x7f162f873110>
Traceback (most recent call last):
  File "x.py", line 3, in __del__
    raise Exception("broken del")
Exception: broken del
---


Technically, slot_tp_finalize() can call lookup_maybe() to get a bound method if the unbound method failed. The question is if it's worth it? In general, I dislike calling too much code to log an exception, since it's likely to raise a new exception. It's exactly the case here: logging an exception raises a new exception (in repr())!

Simpler option: revert the change in slot_tp_finalize() and document that's it's deliberate to get a bound method to get a better error message.


The question is a tradeoff between performance and correctness.
msg287467 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 23:18
I checked typeobject.c: there is a single case where we use the result of lookup_maybe_method()/lookup_method() for something else than calling the unbound method: slot_tp_finalize() calls PyErr_WriteUnraisable(del), the case discussed in my previous message which caused test_exceptions failure (now fixed).
msg287468 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-09 23:27
Thanks for finishing my draft patch, Victor.

callmetohd2.patch is same trick for PyObject_CallMethod* APIs in abstract.c.
It fixes segv in callmethod.patch.
And APIs receiving format string can do same trick when format is empty too.

As I grepping "PyObject_CallMethod", there are many format=NULL callers.
msg287469 - (view) Author: Roundup Robot (python-dev) Date: 2017-02-09 23:41
New changeset e5cd74868dfc by Victor Stinner in branch 'default':
Issue #29507: Fix _PyObject_CallFunctionVa()
https://hg.python.org/cpython/rev/e5cd74868dfc
msg287470 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-09 23:50
callmethod2.patch: I like that change on object_vacall(), I'm not sure about the change on PyObject_CallMethod*() only for empty format string.

I suggest to split your patch into two parts, and first focus on object_vacall(). Do you have a benchmark for this one?

Note: I doesn't like the name I chose for object_vacall(). If we modify it, I would suggest to rename it objet_call_vargs() instead.

Anyway, before pushing anything more, I would like to take a decision on the repr()/test_exceptions issue. What do you think Naoki?
msg287471 - (view) Author: Roundup Robot (python-dev) Date: 2017-02-10 00:00
New changeset b1dc6b6d5fa20f63f9651df2e7986a066c88ff7d by Victor Stinner in branch 'master':
Issue #29507: Fix _PyObject_CallFunctionVa()
https://github.com/python/cpython/commit/b1dc6b6d5fa20f63f9651df2e7986a066c88ff7d
msg287476 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-10 05:12
> I'm not sure about the change on PyObject_CallMethod*() only for empty format string.

There are many place using _PyObject_CallMethodId() to call method without args.
Maybe, we should recommend to use _PyObject_CallMethodIdObjArgs() when no arguments, and replace all caller in cpython?
msg287481 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-10 08:19
performance benefit is small.
https://gist.github.com/methane/32fe57cd4aaac1c5c37f75cbbfbe7562
msg287490 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-10 09:00
>> I'm not sure about the change on PyObject_CallMethod*() only for empty format string.
>
> There are many place using _PyObject_CallMethodId() to call method without args.

I'm more interested by an optimization PyObject_CallMethod*() for any number of arguments, as done in typeobject.c ;-)
msg287492 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-10 09:20
> performance benefit is small.
> https://gist.github.com/methane/32fe57cd4aaac1c5c37f75cbbfbe7562

Are you using PGO+LTO compilation? Without PGO, the noise of code placement can be too high. In your "perf stat" comparisons, I see that "insn per cycle" is lower with the patch, which sounds like a code placement issue like a performance issue with the patch.
msg287496 - (view) Author: INADA Naoki (inada.naoki) * (Python committer) Date: 2017-02-10 09:38
Yes, I used --enable-optimization this time.
But my patch is not good for branch prediction of my CPU in this time.
I'm willing Object/call.c solves such placement issue.

BTW, since benefit of GetMethod is small, how about this?

* Add _PyMethod_FastCallKeywords
* Call it from _PyObject_FastCall*

_PyObject_FastCall* can use FASTCALL C function and method (PyCFunction),
and Python function (PyFunction).
Python method (PyMethod) is last common callable PyObject_FastCall* can't use FASTCALL.
msg287529 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-02-10 12:54
> I'm willing Object/call.c solves such placement issue.

I also *hope* that a call.c file would *help* a little bit, but I'm not sure that it will fix *all* code placement issues.

I created the issue #29524 with a patch creating Objects/call.c.
msg289621 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2017-03-14 21:38
call_method() of typeobject.c has been optimized by the commit 516b98161a0e88fde85145ead571e13394215f8c. I consider that the initial issue is now fixed.

I created the issue #29811 to discuss optimizing callmethod() of call.c which is more complex.
History
Date User Action Args
2017-03-14 21:38:51hayposetstatus: open -> closed
resolution: fixed
messages: + msg289621

stage: resolved
2017-03-14 21:33:18hayposettitle: Use FASTCALL in call_method() to avoid temporary tuple -> Use FASTCALL in typeobject.c call_method() to avoid temporary tuple
2017-02-10 12:54:21hayposetmessages: + msg287529
2017-02-10 09:38:15inada.naokisetmessages: + msg287496
2017-02-10 09:20:04hayposetmessages: + msg287492
2017-02-10 09:00:45hayposetmessages: + msg287490
2017-02-10 08:19:53inada.naokisetfiles: + callmethod3.patch

messages: + msg287481
2017-02-10 05:12:07inada.naokisetmessages: + msg287476
2017-02-10 00:00:20python-devsetmessages: + msg287471
2017-02-09 23:50:16hayposetmessages: + msg287470
2017-02-09 23:41:40python-devsetmessages: + msg287469
2017-02-09 23:27:27inada.naokisetfiles: + callmethod2.patch

messages: + msg287468
2017-02-09 23:18:31hayposetmessages: + msg287467
2017-02-09 23:12:03hayposetmessages: + msg287465
2017-02-09 22:51:18python-devsetmessages: + msg287464
2017-02-09 22:25:00yselivanovsetmessages: + msg287463
2017-02-09 22:22:20hayposetmessages: + msg287462
2017-02-09 22:14:32hayposetmessages: + msg287461
2017-02-09 22:00:33python-devsetnosy: + python-dev
messages: + msg287460
2017-02-09 20:45:30rhettingersetnosy: + rhettinger
messages: + msg287453
2017-02-09 17:50:57hayposetmessages: + msg287440
2017-02-09 17:44:02inada.naokisetmessages: + msg287439
2017-02-09 16:27:39hayposetfiles: + bench.py
2017-02-09 16:27:28hayposetfiles: + method_fastcall4.patch

messages: + msg287436
2017-02-09 14:04:38inada.naokisetfiles: + method_fastcall3.patch

messages: + msg287418
2017-02-09 12:40:55hayposetnosy: + yselivanov
2017-02-09 12:39:32hayposetmessages: + msg287413
2017-02-09 12:20:19inada.naokisetfiles: + method_fastcall2.patch

messages: + msg287410
2017-02-09 11:00:56inada.naokisetmessages: + msg287401
2017-02-09 10:37:31inada.naokisetfiles: + callmethod.patch

messages: + msg287399
2017-02-09 08:08:09inada.naokisetmessages: + msg287387
2017-02-09 00:19:54hayposetmessages: + msg287372
2017-02-09 00:17:38haypocreate