Speedup method calls 1.2x

[1st1]

BPO	26110
Nosy	@Yhg1s, @brettcannon, @jcea, @ncoghlan, @vstinner, @benjaminp, @DinoV, @methane, @serhiy-storchaka, @soltysh, @jdemeyer, @1st1, @jstasiak, @MojoVampire, @Vgr255, @florinpapa, @efahl, @dopplershift, @Fidget-Spinner
PRs	[Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552 bpo-26110: Add CALL_METHOD_KW opcode to speedup method calls with keywords #26014 bpo-26110: Document CALL_METHOD_KW #26159
Files	call_method_1.patch call_method_2.patch call_method_3.patch call_method_4.patch: updated for Python 3.7 default.json.gz callmethod4.json.gz call_method_5.patch default.json.gz patched.json.gz callmethod-doc.patch callmethod-doc2.patch callmethod-doc3.patch call-method-doc4.patch call-method-doc5.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 = 'https://github.com/1st1'
closed_at = <Date 2017-01-16.08:23:59.319>
created_at = <Date 2016-01-14.17:09:06.979>
labels = ['interpreter-core', '3.7', 'performance']
title = 'Speedup method calls 1.2x'
updated_at = <Date 2021-05-16.09:26:18.303>
user = 'https://github.com/1st1'

bugs.python.org fields:

activity = <Date 2021-05-16.09:26:18.303>
actor = 'kj'
assignee = 'yselivanov'
closed = True
closed_date = <Date 2017-01-16.08:23:59.319>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2016-01-14.17:09:06.979>
creator = 'yselivanov'
dependencies = []
files = ['41614', '43599', '43601', '45786', '45787', '45788', '45866', '45887', '45888', '45889', '45891', '45896', '45963', '46294']
hgrepos = []
issue_num = 26110
keywords = ['patch']
message_count = 31.0
messages = ['258204', '258205', '258206', '258211', '258220', '258222', '259333', '259339', '264659', '269662', '269665', '282620', '282621', '282622', '282627', '283075', '283077', '283093', '283094', '283147', '283148', '283149', '283160', '283161', '283166', '283168', '283177', '285415', '285511', '285544', '345335']
nosy_count = 22.0
nosy_names = ['twouters', 'brett.cannon', 'jcea', 'ncoghlan', 'vstinner', 'benjamin.peterson', 'dino.viehland', 'methane', 'santagada', 'python-dev', 'serhiy.storchaka', 'maciej.szulik', 'jdemeyer', 'yselivanov', 'jstasiak', 'josh.r', 'abarry', 'alecsandru.patrascu', 'florin.papa', 'eric.fahlgren', 'Ryan May', 'kj']
pr_nums = ['552', '26014', '26159']
priority = 'normal'
resolution = 'fixed'
stage = 'commit review'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue26110'
versions = ['Python 3.7']

[1st1]

This issue supersedes issue bpo-6033. I decided to open a new one, since the patch is about Python 3.6 (not 2.7) and is written from scratch.

The idea is to add new opcodes to avoid instantiation of BoundMethods. The patch only affects method calls of Python functions with positional arguments.

I'm working on the attached patch in this repo: https://github.com/1st1/cpython/tree/call_meth2

If the patch gets accepted, I'll update it with the docs etc.

Performance Improvements
------------------------

Method calls in micro-benchmarks are 1.2x faster:

### call_method ###
Avg: 0.330371 -> 0.281452: 1.17x faster

### call_method_slots ###
Avg: 0.333489 -> 0.280612: 1.19x faster

### call_method_unknown ###
Avg: 0.304949 -> 0.251623: 1.21x faster

Improvements in mini-benchmarks, such as Richards are less impressive, I'd say it's 3-7% improvement. The full output of benchmarks/perf.py is here: https://gist.github.com/1st1/e00f11586329f68fd490

When the full benchmarks suite is run, some of them report that they were slow. When I ran them separately several times, they all show no real slowdowns. It's just some of them (such as nbody) are highly unstable.

It's actually possible to improve the performance another 1-3% if we fuse __PyObject_GetMethod with ceval/LOAD_METHOD code. I've tried this here: https://github.com/1st1/cpython/tree/call_meth4, however I don't like to have so many details of object.c into ceval.c.

Changes in the Core
-------------------

Two new opcodes are added -- LOAD_METHOD and CALL_METHOD. Whenever compiler sees a method call "obj.method(..)" with positional arguments it compiles it as follows:

  LOAD_FAST(obj)
  LOAD_METHOD(method)
  {call arguments}
  CALL_METHOD

LOAD_METHOD implementation in ceval looks up "method" on obj's type, and checks that it wasn't overridden in obj.__dict__. Apparently, even with the __dict__ check this is still faster then creating a BoundMethod instance etc.

If the method is found and not overridden, LOAD_METHOD pushes the resolved method object, and 'obj'. If the method was overridden, the resolved method object and NULL are pushed to the stack.

CALL_METHOD then looks at the two stack values after call arguments. If the first one isn't NULL, it means that we have a method call.

Why CALL_METHOD?
----------------

It's actually possible to hack CALL_FUNCTION to support LOAD_METHOD. I've tried this approach in https://github.com/1st1/cpython/tree/call_meth3. It looks like that adding extra checks in CALL_FUNCTION have negative impact on many benchmarks. It's really easier to add another opcode.

Why only pure-Python methods?
-----------------------------

LOAD_METHOD atm works only with methods defined in pure Python. C methods, such as list.append are still wrapped into a descriptor, that creates a PyCFunction object on each attribute access. I've tried to do that in https://github.com/1st1/cpython/tree/call_cmeth. It does impact C method calls in a positive way, although my implementation is very hacky. It still uses LOAD_METHOD and CALL_METHOD opcodes, so my idea is to consider merging this patch first, and then introduce the necessary refactoring of PyCFunction and MethodDesctiptors in a separate issue.

Why only calls with positional arguments?
-----------------------------------------

As showed in "Why CALL_METHOD?", making CALL_FUNCTION to work with LOAD_METHOD slows it down. For keyword and var-arg calls we have three more opcodes -- CALL_FUNCTION_VAR, CALL_FUNCTION_KW, and CALL_FUNCTION_VAR_KW. I suspect that making them work with LOAD_METHOD would slow them down too, which will probably require us to add three (!) more opcodes for LOAD_METHOD.

And these kind of calls require much more overhead anyways, I don't expect them to be as optimizable as positional arg calls.

[vstinner]

For keyword and var-arg calls we have three more opcodes -- CALL_FUNCTION_VAR, CALL_FUNCTION_KW, and CALL_FUNCTION_VAR_KW. I suspect that making them work with LOAD_METHOD would slow them down too, which will probably require us to add three (!) more opcodes for LOAD_METHOD.

I don't think that it's an issue to add 3 more opcodes for performance. If you prefer to limit the number of opcodes, you can pass a flag in arguments. For example, use 2 bytes for 2 arguments instead of only 1?

See also the (now old) WPython project which proposed kind of CISC instructions:
https://code.google.com/p/wpython/

[1st1]

If you prefer to limit the number of opcodes, you can pass a flag in arguments. For example, use 2 bytes for 2 arguments instead of only 1?

I tried two approaches:

1. Push one more leading NULL to the stack in LOAD_METHOD (which makes it push 3 vals). Then, in CALL_FUNCTION, detect when the callable is NULL and to the stuff that CALL_METHOD does.

2. Use a bitflag on oparg for CALL_FUNCTION and CALL_* opcodes. This adds EXTENDED_ARG opcode overhead.

Long story short, the only option would be to add dedicated opcodes to work with LOAD_METHOD. However, I'd prefer to first merge this patch, as it's relatively small and easy to review, and then focus on improving other things (keyword/*arg calls, C methods, etc). This is just a first step.

[gvanrossum]

I like this idea! I like the limitations to positional-only calls. I do think that it would be nice if we could speed up C calls too -- today, s.startswith('abc') is slower than s[:3] == 'abc' precisely because of the lookup. But I'm all for doing this one step at a time, so we can be sure it is solid before taking the next step(s).

[1st1]

I like this idea! I like the limitations to positional-only calls. I do think that it would be nice if we could speed up C calls too -- today, s.startswith('abc') is slower than s[:3] == 'abc' precisely because of the lookup. But I'm all for doing this one step at a time, so we can be sure it is solid before taking the next step(s).

Yes, I think we can make <built-in type>.method(..) calls much faster with LOAD_METHOD. Since those types lack __dict__ and their __class__ is read-only, we can use a far better optimized code path without extra lookups and creation of BoundMethod/PyCFunction objects.

[vstinner]

I'm happy to see people working on optimizing CPython ;-)

[1st1]

For those interested in reviewing this patch at some point: please wait until I upload a new version. The current patch is somewhat outdated.

[alecsandrupatrascu]

Yury, thank you for the heads up! Here at Intel, in the Dynamic Scripting Languages Optimization Team, we can help the community with reviewing and measuring this patch in our quiet and stable environment, the same one that we use to provide public CPython daily measurements. We will wait for your update.

[gvanrossum]

This patch doesn't apply cleanly any more. Is it easy to update?

[methane]

Updated, based on 102241:908b801f8a62

[methane]

Oops, previous patch doesn't update magic number in PC/launcher.c
Should I update it? Or don't touch it to avoid additional conflicts?