Specialize LOAD_METHOD

[Fidget-Spinner]

Add specialization "families" for PEP 659 adaptive interpreter for LOAD_METHOD.

Background:

LOAD_METHOD is a compiler-level specialization of LOAD_ATTR. It's emitted with CALL_METHOD for calls of the form o.meth(), where o is not a top-level import. When this was added in 3.7, it brought 20% faster method calls by avoiding creating a bound method object.

Specialization

The specialization families for LOAD_METHOD are very similar to LOAD_ATTR (#52) and we can reuse many ideas and code. The speedup comes from avoiding a _PyObject_GetMethod which does two things:

1. _PyType_Lookup (walk the MRO)
2. Check if meth is in o.__dict__ to make sure it's not an attribute.

There are one or two specializations which I'm optimistic for:

• LOAD_METHOD_WITH_HINT (see LOAD_ATTR_WITH_HINT) renamed to LOAD_METHOD_CACHED -- cache the descriptor object
• Optional: LOAD_METHOD_WITH_HINT_NO_DICT -- specialized form of LOAD_METHOD_WITH_HINT for objects with no __dict__

These specializations make sense, but will likely bring little speedup in macrobenchmarks, so we need more profiling:

• LOAD_METHOD_MODULE -- o is a module, almost same as specializing LOAD_ATTR_MODULE
• LOAD_METHOD_CLASS -- o is a class and meth is a classmethod

Also, I don't expect much speedups for builtin methods (e.g {1,2,3}.keys()). Their _PyType_Lookup should be cheap due to the existing type method cache. Classes with a long MRO will probably benefit the most.

Workbranch: python/cpython#27722

[Fidget-Spinner]

I've implemented LOAD_METHOD_WITH_HINT and it passes the entire test suite. See python/cpython@main...Fidget-Spinner:specialize_load_method . Here's some microbenchmarks (release build, no LTO or PGO). I will run pyperformance later:

No speedup for builtin methods:

python.exe" -m timeit -s "x = {}" "x.keys()":
Main:

5000000 loops, best of 5: 56.2 nsec per loop
5000000 loops, best of 5: 56.1 nsec per loop
5000000 loops, best of 5: 56.1 nsec per loop

Specialized:

5000000 loops, best of 5: 58.6 nsec per loop
5000000 loops, best of 5: 59.3 nsec per loop
5000000 loops, best of 5: 59.8 nsec per loop

12% speedup for python methods calls:

Likely even more for long classes with long MRO.

"python.exe" -m timeit -s "
>> class X:
>>  def y(s):
>>   ...
>> x = X()
>> " "x.y()"

Main:

5000000 loops, best of 5: 84.8 nsec per loop
5000000 loops, best of 5: 83.5 nsec per loop
5000000 loops, best of 5: 83.6 nsec per loop

Specialized:

5000000 loops, best of 5: 73.6 nsec per loop
5000000 loops, best of 5: 73.5 nsec per loop
5000000 loops, best of 5: 73.1 nsec per loop

[Fidget-Spinner]

Initial pypeformance figures are somewhat promising as of python/cpython@0f32d60, logging_silent seems like it benefits:

pyperf compare_to 2021-08-05_13-58-main-3d315c311676.json.gz 2021-08-08_04-02-specialize_load_method-0f32d60e2a2b.json.gz  -G --min-speed=2
Slower (5):
- telco: 16.1 ms +- 0.4 ms -> 16.5 ms +- 0.6 ms: 1.03x slower
- dulwich_log: 168 ms +- 2 ms -> 172 ms +- 3 ms: 1.03x slower
- scimark_sparse_mat_mult: 13.0 ms +- 0.1 ms -> 13.3 ms +- 0.1 ms: 1.02x slower
- scimark_fft: 1.01 sec +- 0.01 sec -> 1.03 sec +- 0.00 sec: 1.02x slower
- float: 262 ms +- 4 ms -> 268 ms +- 3 ms: 1.02x slower

Faster (6):
- logging_silent: 400 ns +- 11 ns -> 365 ns +- 10 ns: 1.09x faster
- pickle_list: 10.2 us +- 0.2 us -> 9.85 us +- 0.10 us: 1.04x faster
- regex_dna: 512 ms +- 25 ms -> 494 ms +- 3 ms: 1.03x faster
- hexiom: 22.2 ms +- 0.3 ms -> 21.6 ms +- 0.3 ms: 1.03x faster
- scimark_sor: 478 ms +- 9 ms -> 467 ms +- 5 ms: 1.02x faster
- richards: 174 ms +- 2 ms -> 170 ms +- 2 ms: 1.02x faster

Benchmark hidden because not significant (47): 2to3, chameleon, chaos, crypto_pyaes, deltablue, django_template, fannkuch, go, json_dumps, json_loads, logging_format, logging_simple, mako, meteor_contest, nbody, nqueens, pathlib, pickle, pickle_dict, pickle_pure_python, pidigits, pyflate, python_startup, python_startup_no_site, raytrace, regex_compile, regex_effbot, regex_v8, scimark_lu, scimark_monte_carlo, spectral_norm, sqlalchemy_declarative, sqlalchemy_imperative, sqlite_synth, sympy_expand, sympy_integrate, sympy_sum, sympy_str, tornado_http, unpack_sequence, unpickle, unpickle_list, unpickle_pure_python, xml_etree_parse, xml_etree_iterparse, xml_etree_generate, xml_etree_process

Geometric mean: 1.00x faster

[markshannon]

@Fidget-Spinner did you gather any stats on how often different specializations would apply?
Without that information, we are just guessing.
Performance numbers cannot tell us whether specialization is worth doing, if we don't implement the right specializations.

python/cpython#27701 might help gather more useful stats.

[markshannon]

Here's some approximate stats I've just gathered:

Kind	Percent
Module attribute	4.7%
Python function (instance has dict)	39.4%
Python function (no dict)	3.0%
Builtin function (instance has dict)	3.0%
Builtin function (no dict)	42.5%
Mysteriously missing 😕	~7%

These numbers seem sensible, but I'm a bit surprised by the "Builtin function (instance has dict)" and I don't know why ~7% is missing.

[Fidget-Spinner]

Thanks for gathering those number Mark.

@Fidget-Spinner did you gather any stats on how often different specializations would apply?

Yes, I ran a subset of the test suite, and they agree with your stats. However, your stats are way more comprehensive :). Mine showed anywhere from 50-80% cache hits of LOAD_METHOD_WITH_HINT (currently, this works for Python methods and builtin function, irregardless of dict). Module methods were <10%.

I have a few questions. Are those stats from pyperformance? And are classmethods part of Python function and Builtin function ?

[markshannon]

The stats are from pyperformance, with a debug build.

[gvanrossum]

Maybe "Builtin function (instance has dict)" is for methods inherited from object, e.g. x.__str__? I'm late to this thread so I don't know exactly what these numbers represent, so I don't have any ideas about the mysteriously missing 7%.

[Fidget-Spinner]

@markshannon, after updating my code to work with inherited methods, specializing just for the most common case (where a real method was found) seems to pay off. See python/cpython#27722 (comment) for the pyperformance results.

[Fidget-Spinner]

🎉 merged into CPython in python/cpython@96346cb:

• LOAD_METHOD_CACHED
• LOAD_METHOD_MODULE
• LOAD_METHOD_CLASS

Both Mark's and my pyperformance showed a 2% faster average, with the biggest jump being logging_silent (1.22 faster!).

Some parts can be improved a little further (see python/cpython#27722 (comment)), but with a >90% specialization success on a subset of the python test suite, it's not too urgent. So I think it's done for now. Thanks to Mark for helping out tremendously.

[Fidget-Spinner]

I suspect that part of the missing 7% in Mark's stats is actually our good friend super().

o.meth	Percent of specialization failures
type(o).tp_dictoffset < 0 (ie dynamic size container types with __dict__)	55%
o is good ol' super()	29%
meth is not a method	11%
meth is a builtin classmethod (METH_CLASS) or python @classmethod(func) object	5%

type(o).tp_dictoffset < 0 will be fixed by Mark's work on object layouts with __dict__ at fixed offsets. This alone will bring LOAD_METHOD to 96% successes. super() specialization may bring us to 98.5%.

I will continue monitoring to see if a potential LOAD_METHOD_SUPER will bring us speedups in any of the pyperformance. If it does, I'll open another issue.