Broader specialization in the Specializing Adaptive Interpreter for better JIT performance

[markshannon]

Until now, our choice of specialization in the SAI has been driven by performance of the interpreter alone https://github.com/python/cpython/blob/main/InternalDocs/interpreter.md#performance-analysis.

However, we now expect any further performance improvements to be provided by the JIT, not the interpreter.
This means that specializations other role, that of gathering type and branching information for the JIT, is at least as important as pure interpreter performance.

We should therefore seek to broaden specialization to gather more information, as long as it does not make interpreter performance worse, or at least no significantly so.

Using some old stats, by fraction of unspecialized bytecode executed, the top 10 were:
BINARY_OP 31.3%
FOR_ITER 19.4%
LOAD_ATTR 10.9%
STORE_SUBSCR 9.2%
BINARY_SLICE 7.3%
COMPARE_OP 7.0%
TO_BOOL 5.8%
CALL 2.5%
CONTAINS_OP 2.4%
SEND 1.7%

We should fully specialize most, if not all, of these.

In general, the above instructions have a matching __dunder__ method which determines the behavior of the operation. Recording the type of the operand(s) allows us to know what __dunder__ method is to be called.

We cannot specialize for all possible types, but we can ensure we have good inputs and type information for the JIT by adding the following two specializations for all families of instructions:

• __dunder__ implemented in Python. Most of the above instructions have a matching __dunder__ method. These specializations should jump directly into the method. LOAD_ATTR_GETATTRIBUTE_OVERRIDDEN already does this for LOAD_ATTR. Other families should follow this template.
• __dunder__ implemented in C. In practice, this is just the generic instruction with a bit more information recorded.

Three instructions need special casing:

• BINARY_OP. Because the behavior depends on two types, we will need a table driven approach: Specialize long tail of binary operations using a table. #100239
• BINARY_SLICE. This is supposed to avoid creating temporary slice objects for expressions like a[b:c] but has yet to be implemented properly. There is no corresponding __dunder__ method, so we would need to expose slicing methods to use.
• SEND. There is no __send__ method. For iterators, __next__ is called if the value is None, otherwise .send() is called. Rather than try to replicate the specializations of FOR_ITER we should maybe look to combine SEND and FOR_ITER much like we did for CALL and CALL_METHOD

First step

Add two specializations for __dunder__ in Python and the fallback __dunder__ in C for:

• FOR_ITER
• LOAD_ATTR
• STORE_SUBSCR
• COMPARE_OP
• TO_BOOL
• CALL
• CONTAINS_OP

For a total of 12 new instructions as LOAD_ATTR already has the specialization for the Python __getattribute__ and CALL already has the generic fallback.

Second step

Implement #100239

Third step

Handle BINARY_SLICE and SEND

Linked PRs

• gh-143732: Add specialization for TO_BOOL #148113
• gh-143732: allow dict subclasses to be specialized  #148128
• gh-143732: Add tier2 specialization for TO_BOOL #148271

[Fidget-Spinner]

An alternative if we do slow down the interpreter from making it too large (very likely for computed goto/switch-case interpreter), we can just ifdef those cases out in non-JIT builds, and just reserve the opcodes for use. This way, the default build interpreter won't slow down.

[kumaraditya303]

SEND. There is no send method. For iterators, next is called if the value is None, otherwise .send() is called. Rather than try to replicate the specializations of FOR_ITER we should maybe look to combine SEND and FOR_ITER much like we did for CALL and CALL_METHOD

As a data point, any coroutine runner like asyncio or trio uses coroutine.send(arg) to iterate through the coroutine. Currently each such call goes through vectorcall to in the end setup a new frame and send arg to generator. I think it could be optimized like CALL_COROUTINE_SEND where the frame can be inlined and avoid going through vectorcall.

the pyperformance benchmarks uses the C implementation of asyncio and there is no trio benchmark so this case is not represented but this is an important missed specialization.

[markshannon]

@kumaraditya303 We should rewrite send() in byteocde, rather than adding even more specializations.

[markshannon]

An alternative if we do slow down the interpreter from making it too large (very likely for computed goto/switch-case interpreter), we can just ifdef those cases out in non-JIT builds, and just reserve the opcodes for use. This way, the default build interpreter won't slow down.

👍

That should allow us to add these without worrying about interpreter-only performance too much.
Although, I'm hoping that we won't need this, as we already have far too many different configurations.

[markshannon]

One other consideration is the increase in size of inline caches necessary to store the type information and possible pointers.
To specialize for a method __dunder__ we need a version number for the guard and a pointer to the __dunder__ function.
Rather than put the pointer to the function inline we can cache it on the class, as we already do for __getitem__ and __init__ storing them in the class's _specialization_cache. If we expect specializations to be overwhelmingly builtin classes, a single 16bit cache is sufficient, but we will generally need a 32 bit (2 code units) cache.

Family	Current space in cache	Additional space needed for version
BINARY_OP	4	0
CALL	3	0
FOR_ITER	0	1*
LOAD_ATTR	8	0**
STORE_SUBSCR	0	2
COMPARE_OP	0	2
TO_BOOL	2	0
CONTAINS_OP	0	2

*We expect that most if not all iterators written in Python will be generators.
** No need to store the method in the _specialization_cache as there is space to store in inline

[markshannon]

These are the specializations I think we should add to start with:

Family	__dunder__ in Python	__dunder__ in C
FOR_ITER	FOR_ITER_PY_DUNDER	FOR_ITER_GENERIC
CALL	CALL_PY_DUNDER	(already exists)
LOAD_ATTR	(already exists)	LOAD_ATTR_GENERIC
TO_BOOL	TO_BOOL_PY_DUNDER	TO_BOOL_GENERIC
STORE_SUBSCR	STORE_SUBSCR_PY_DUNDER	STORE_SUBSCR_GENERIC
CONTAINS_OP	CONTAINS_OP_PY_DUNDER	CONTAINS_OP_GENERIC

We can leave BINARY_OP and COMPARE_OP for later, as they need more complex table-based approaches.

[kumaraditya303]

We should rewrite send() in byteocde, rather than adding even more specializations.

Do you mean something like #142864 for send with one arg?

[markshannon]

We should rewrite send() in byteocde, rather than adding even more specializations.

Do you mean something like #142864 for send with one arg?

No. Rewrite send itself, not its callers.
Something like faster-cpython/ideas#448 (comment)

[markshannon]

See also #145047

[eendebakpt]

@markshannon I started working on the _TO_BOOL_GENERIC case. I have a working branch TO_BOOL_GENERIC that adds the opcode _TO_BOOL_GENERIC (which gives better specialization for the JIT) and adds a tier 2 specialization _TO_BOOL_DICT (tier 2 so we do not add too many tier 1 opcodes). The new _TO_BOOL_GENERIC is macro(TO_BOOL_GENERIC) = unused/1 + _RECORD_TOS_TYPE + _GUARD_TYPE_VERSION + _TO_BOOL; so is still using the "normal" conversion to bool. Would you mind having a look whether this is in the right direction?

Microbenchmarks shows the effect of the _TO_BOOL_DICT:

Test	main median (range)	feature median (range)	Speedup
if dct: (dict)	12.5 (12.1–13.2) ns	8.8 (8.5–9.3) ns	+29.4%
if t: (tuple)	12.2 (11.9–13.1) ns	12.3 (11.9–12.5) ns	-0.7%
if s: (set)	12.3 (12.2–20.6) ns	12.3 (12.2–13.1) ns	-0.1%
if f: (float)	11.7 (11.2–12.0) ns	11.7 (11.4–13.7) ns	-0.3%
a.append(i)	8.1 (8.0–9.1) ns	7.9 (7.7–8.5) ns	+2.8%

If I understand your ideas correctly we should adapt the code further so that _TO_BOOL_GENERIC calls directly the appropriate method for conversion to bool. Is that part needed or would the current approach already be good enough (since it does propagate the type information and allows jit specializations).