markshannon
commented
6 months ago I performed an experiment to see how well binary ops specialize for reference count and immortality. They specialize quite well, both for the fraction specialized and the hit rates. Refcount stability seems quite good.
Numbers are in millions of instructions. Full stats
1 means refcount of 1, I means immortal, X means anything.
| Op | Count | Miss |
|---|---|---|
| BINARY_OP_II | 2310 | 1.9% |
| BINARY_OP_XI | 2265 | 0.5% |
| BINARY_OP_XX | 1596 | -- |
| BINARY_OP_X1 | 623 | 0.3% |
| BINARY_OP_11 | 550 | 2.4% |
| BINARY_OP_1I | 425 | 5.4% |
| BINARY_OP_1X | 354 | 0.6% |
| BINARY_OP_IX | 155 | 13.6% |
| BINARY_OP_I1 | 113 | 16.6% |
So if we specialize just for refcounts, we will want to specialize for II, XI, and X1 as they are common and have low miss rates.
There is little to gained from the 11 form, as we can't reuse both operands. So, we might as well merge into X1.
1X allows the left hand side to used, and has a low miss rate. This is probably worth specializing for despite its relative rarity.
We might want to implement 1I as well, despite its miss rate and rarity, just because it is so efficient.
All the others probably aren't worth it, so we will want to have four or five specializations, II, XI, X1, 1X and maybe 1I.
Specializing for type and refcount
If we are specializing for refcount and type, we will obviously need to use some sort of table approach to handle the many combinations. We will need to guard on the refcounts, and on the types. Guarding on refcount or immortality is tricky to do with table lookup, without some sort of switch, so we will need to do that at the bytecode level. Type checks can be done without excessive branching using versions.
Both types of guards can be potentially removed in the tier 2 optimizer.
By specializing
BINARY_OPby reference count as well as by type we can potentially speedup tier 2 jitted binary operations quite a lot.It is quite common that one of the operands of
BINARY_OPhas a reference count of 1, so it is profitable to avoid object allocation and reuse that object. We already do that forfloatspecializations ofBINARY_OP. The problem is that the resulting code is quite branchy, and thus bulky, which is a problem for the jit.If we specialize by refcount, the code size shrinks dramatically. For example, the x86-64 code size for
_BINARY_OP_MULTIPLY_FLOATis 232 bytes. If we specialize for the left hand side having a refcount of 1 the equivalent instruction is 143* with a guard for the refcount. If we assume that the optimizer can remove the guard, then the size drops to 74 bytes.If we also specialize for the right hand side having a refcount > 1, then the code size (without guards) drops to 41 bytes, less than 20% of the original code size.
Pyston performs this optimization. It is, I believe, the only specialization that Pyston does that we don't.
There isn't much room for more tier 1 instructions, but by combining this approach with https://github.com/faster-cpython/ideas/issues/660 we can implement this without excessive tier 1 specialization.
Currently,
BINARY_OPspecializes to one of:We can replace these with:
The
L1andR1suffices mean "left has refcount of one" and "right has refcount of one" respectively.intis still worth treating separately because it is both common and more awkward due to the caching of small values.(ignoring BINARY_OP_INPLACE_ADD_UNICODE as a special case)
*This will go down once we have hot/cold splitting