Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use FASTCALL in typeobject.c call_method() to avoid temporary tuple #73693

Closed
vstinner opened this issue Feb 9, 2017 · 30 comments
Closed

Use FASTCALL in typeobject.c call_method() to avoid temporary tuple #73693

vstinner opened this issue Feb 9, 2017 · 30 comments
Labels
3.7 interpreter-core performance

Comments

@vstinner
Copy link
Member

@vstinner vstinner commented Feb 9, 2017

BPO 29507
Nosy @rhettinger, @vstinner, @methane, @serhiy-storchaka, @1st1
Files
  • method_fastcall.patch
  • callmethod.patch
  • method_fastcall2.patch
  • method_fastcall3.patch
  • method_fastcall4.patch
  • bench.py
  • callmethod2.patch
  • callmethod3.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 2017-03-14.21:38:51.342>
    created_at = <Date 2017-02-09.00:17:38.154>
    labels = ['interpreter-core', '3.7', 'performance']
    title = 'Use FASTCALL in typeobject.c call_method() to avoid temporary tuple'
    updated_at = <Date 2017-03-14.21:38:51.341>
    user = 'https://github.com/vstinner'

    bugs.python.org fields:

    activity = <Date 2017-03-14.21:38:51.341>
    actor = 'vstinner'
    assignee = 'none'
    closed = True
    closed_date = <Date 2017-03-14.21:38:51.342>
    closer = 'vstinner'
    components = ['Interpreter Core']
    creation = <Date 2017-02-09.00:17:38.154>
    creator = 'vstinner'
    dependencies = []
    files = ['46601', '46603', '46606', '46610', '46611', '46612', '46615', '46619']
    hgrepos = []
    issue_num = 29507
    keywords = ['patch']
    message_count = 30.0
    messages = ['287371', '287372', '287387', '287399', '287401', '287410', '287413', '287418', '287436', '287439', '287440', '287453', '287460', '287461', '287462', '287463', '287464', '287465', '287467', '287468', '287469', '287470', '287471', '287476', '287481', '287490', '287492', '287496', '287529', '289621']
    nosy_count = 6.0
    nosy_names = ['rhettinger', 'vstinner', 'methane', 'python-dev', 'serhiy.storchaka', 'yselivanov']
    pr_nums = []
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'performance'
    url = 'https://bugs.python.org/issue29507'
    versions = ['Python 3.7']

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    Subset of the (almost) rejected issue bpo-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 bpo-29263 "Implement LOAD_METHOD/CALL_METHOD for C functions".

    @vstinner vstinner added 3.7 interpreter-core performance labels Feb 9, 2017
    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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.

    @methane
    Copy link
    Member

    @methane methane commented Feb 9, 2017

    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.

    @methane
    Copy link
    Member

    @methane methane commented Feb 9, 2017

    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.

    @methane
    Copy link
    Member

    @methane methane commented Feb 9, 2017

    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)

    @methane
    Copy link
    Member

    @methane methane commented Feb 9, 2017

    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%)

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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().

    @methane
    Copy link
    Member

    @methane methane commented Feb 9, 2017

    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.)

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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%)

    @methane
    Copy link
    Member

    @methane methane commented Feb 9, 2017

    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.

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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): (...)

    @rhettinger
    Copy link
    Contributor

    @rhettinger rhettinger commented Feb 9, 2017

    +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.

    @python-dev
    Copy link
    Mannequin

    @python-dev python-dev mannequin commented Feb 9, 2017

    New changeset 7b8df4a5d81d by Victor Stinner in branch 'default':
    Optimize slots: avoid temporary PyMethodObject
    https://hg.python.org/cpython/rev/7b8df4a5d81d

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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.

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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?

    @1st1
    Copy link
    Member

    @1st1 1st1 commented Feb 9, 2017

    patch looks good to me.

    @python-dev
    Copy link
    Mannequin

    @python-dev python-dev mannequin commented Feb 9, 2017

    New changeset be663c9a9e24 by Victor Stinner in branch 'default':
    Issue bpo-29507: Update test_exceptions
    https://hg.python.org/cpython/rev/be663c9a9e24

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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.

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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).

    @methane
    Copy link
    Member

    @methane methane commented Feb 9, 2017

    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.

    @python-dev
    Copy link
    Mannequin

    @python-dev python-dev mannequin commented Feb 9, 2017

    New changeset e5cd74868dfc by Victor Stinner in branch 'default':
    Issue bpo-29507: Fix _PyObject_CallFunctionVa()
    https://hg.python.org/cpython/rev/e5cd74868dfc

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 9, 2017

    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?

    @python-dev
    Copy link
    Mannequin

    @python-dev python-dev mannequin commented Feb 10, 2017

    New changeset b1dc6b6 by Victor Stinner in branch 'master':
    Issue bpo-29507: Fix _PyObject_CallFunctionVa()
    b1dc6b6

    @methane
    Copy link
    Member

    @methane methane commented Feb 10, 2017

    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?

    @methane
    Copy link
    Member

    @methane methane commented Feb 10, 2017

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 10, 2017

    > 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 ;-)

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 10, 2017

    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.

    @methane
    Copy link
    Member

    @methane methane commented Feb 10, 2017

    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.

    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Feb 10, 2017

    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 bpo-29524 with a patch creating Objects/call.c.

    @vstinner vstinner changed the title Use FASTCALL in call_method() to avoid temporary tuple Use FASTCALL in typeobject.c call_method() to avoid temporary tuple Mar 14, 2017
    @vstinner
    Copy link
    Member Author

    @vstinner vstinner commented Mar 14, 2017

    call_method() of typeobject.c has been optimized by the commit 516b981. I consider that the initial issue is now fixed.

    I created the issue bpo-29811 to discuss optimizing callmethod() of call.c which is more complex.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    3.7 interpreter-core performance
    Projects
    None yet
    Development

    No branches or pull requests

    4 participants