Cross Module Quickening Paper

[Fidget-Spinner]

I found this interesting paper on Cross-Module Quickening, by Felix Berlakovich and Stefan Brunthaler at ECOOP 2024. It makes use of CPython 3.12.0's specializing interpreter to quicken across C extensions. So far it seems they introduce more specializations to achieve this. Still reading the paper to learn more.

The key idea is to provide the C extension with an interface to register specialized, extension-specific interpreter instructions

https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.6

[mdboom]

This is really similar to my idea in #432, though they have obviously taken it much further. I'm intrigued.

[mdboom]

My thoughts after reading this paper:

The results are impressive, and having written a lot of Numpy-using code in the past, I'm not surprised that the type stability is so exploitable. As with most optimizations of the Python side of Numpy, this benefits most when the data is small, and decreases as the data gets larger. Still, seems like it could be a way for the Faster CPython work to have more of an impact on numeric computing. There is of course a small penalty for the extra work in the non-specialized instructions to make this work, even for those who never load an optimization-aware C extension. I would want to run this against some pure Python benchmarks, such as those in pyperformance, to better understand what that overhead is -- and maybe there are clever ways to negate it when we know it won't be needed.

I agree with the authors that Numpy is an important and interesting use case. It's not immediately clear how well it generalizes, but maybe within the stdlib, it could improve the performance of decimal and fraction (though maybe their work planning/type dispatch overhead is already so much lower than Numpy's that it doesn't matter as much).

There is mention of using the inline cache to store the subscript of the expression:

array[1:, 2:]

which is syntactic sugar for:

array[(slice(1, None, None), slice(2, None, None))]

Would the constant propagation work/plans we have already handle this case? (@Fidget-Spinner?) If so, at least for this somewhat common Numpy idiom, that optimization might be handled by the interpreter optimizer itself in the near future.

For reference the code from the paper:

• Changes to Numpy: https://github.com/fberlakovich/cmq-numpy-ae
• Changes to CPython: https://github.com/fberlakovich/cmq-ae

@fberlakovich, @sbrunthaler: Thanks for the great paper!

[Fidget-Spinner]

Would the constant propagation work/plans we have already handle this case?

If @brandtbucher 's work on constant pools for Tier 2 is merged, yeah we can do constant evaluation of slices in tier 2 in the future with the partial evaluation pass.

[brandtbucher]

If @brandtbucher 's work on constant pools for Tier 2 is merged, yeah we can do constant evaluation of slices in tier 2 in the future with the partial evaluation pass.

Not merged yet, but I'll open a PR soon.

[mdboom]

If @brandtbucher 's work on constant pools for Tier 2 is merged, yeah we can do constant evaluation of slices in tier 2 in the future with the partial evaluation pass.

Not merged yet, but I'll open a PR soon.

That may reduce the need for the "extension-delimited superinstructions" (specializing a range of instructions with a single instruction) mentioned in the paper, and avoid that complexity.

[mdboom]

The authors' patch seems to have a performance penalty of about 3% on pyperformance. Though let me stress this shouldn't be an argument against it because I doubt they specifically optimized for low impact when the optimization isn't in use. This is more just for information as I start to look at and understand the patches.

EDIT: I think the base commit was selected incorrectly (it's an unusual case because it's on the 3.12 branch, not main). I'm going to rerun the correct base and recreate the results.

[mdboom]

The author's patch has a performance penalty below the noise threshold. This is for benchmarks that don't take advantage of the added CMQ APIs, of course.

[iritkatriel]

Some thoughts after experimenting with this idea in python/cpython#133396 (which was reverted):

We stored, in the instruction's cache entry, a pointer to a struct describing the specialisation. This struct has pointers to the BINARY_OP oparg, the guard function, the action/calculation function and a cleanup function (called on deopt or deallocation of the code object). The extension allocates and deallocates this extra data (as only it knows whether it is static so that different instructions can share the same one, or each code location needs its own instance).

This was reverted because there was a memory leak (which is solvable). However, there is a complication that we need to think through: If the cache contains dynamic data belonging to the application, the assumption in the PR is that we should, as soon as we deopt, call the cleanup function, NULL out the cache, and replace the BINARY_OP_EXTEND opcode by BINARY_OP, so that we won't try to access the cache again without re-specializing.

We could, I guess, not NULL out the cache (leave a dangling pointer on the assumption that it won't be accessed). We could probably delay calling the cleanup function until this instruction is specialised again or the code object is destroyed.
But I think we do need to change the opcode upon DEOPT (which other specialisations don't need to do). So we are introducing a new behaviour to the specialisation mechanism.