GeezerVison is showing github.com — A new tail-calling interpreter for significantly better interpreter performance · Issue #128563 · python/cpython
A new tail-calling interpreter for significantly better interpreter performance #128563DescriptionFeature or enhancement
Proposal
Prior discussion at: faster-cpython/ideas#642
I propose adding a tail-calling interpreter to CPython for significantly better performance on compilers that support it.
This idea is not new, and has been implemented by:
- Protobuf https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html
- Lua (Deegen) https://sillycross.github.io/2022/11/22/2022-11-22/
CPython currently has a few interpreters:
- A switch-case interpreter (MSVC)
- A computed goto interpreter (Clang, GCC)
- An uop interpreter. (Everything)
The tail-calling interpreter will be the 4th that coexists with the rest. This means no compatibility concerns.
Performance
Preliminary benchmarks by me suggest excellent performance improvements --- 10% geometric mean speedup in pyperformance, with up to 40% speedup in Python-heavy benchmarks: https://gist.github.com/Fidget-Spinner/497c664eef389622d146d632990b0d21. These benchmarks were performed with clang-19 on both main and my branch, with ThinLTO and PGO, on AMD64 Ubuntu 22.04. PGO seems especially crucial for the speedups based on my testing. For those outside of CPython development: a 10% speedup is roughly equal to 2 minor CPython releases worth of improvements. For example, CPython 3.12 roughly sped up by 5%.
The speedup is so significant that if accepted, the new interpreter will be faster than the current JIT compiler.
CORRECTION NOTICE: We've since found a compiler bug in LLVM 19 that artificially boosted the new interpreter's numbers. The numbers are closer to geomean 3-5% speedup. I apologize for reporting incorrect figures previously due to the compiler bug.
Drawbacks
- Maintainability (this will introduce more code)
- Portability
I will address maintainability by using the interpreter generator that was introduced as part of CPython 3.12. This generator will allow us to automatically generate most of the infrastructure needed for this change. Preliminary estimates suggest the generator will be only 200 lines of Python code, most of which is shared/copied/same conceptually as the other generators.
For portability, this will fix itself (see the next section).
Portability and Precedent
At the moment, this is only supported by clang-19 for AArch64 and AMD64, with partial support on clang-18 and gcc-next, but likely bad performance on those. The reason is that we need both the __attribute__((musttail)) and __attribute__((preserve_none)) attributes for good performance. GCC only has gnu::musttail but not preserve_none.
There has been prior precedence on adding compiler-specific optimizations for CPython. See for example the original computed goto issue by Antoine Pitrou https://bugs.python.org/issue4753. At the time, it was a new feature only on GCC and not on Clang, but we still added it anyways. Eventually a few years later, Clang also introduced the feature. The key point gcc will likely eventually catch up and add these features.
EDIT: Added that it's only a likely case to have bad perf on GCC. Reading https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118328, I have not tested on GCC trunk. This is pure speculation that perf is bad. I can try with GCC eventually after the PR lands and we can test it from there. However, testing with clang with just musttail and no preserve_none, the performance was quite bad.
Implementation plan
- Parse error labels in
_PyEval_EvalFrameDefault.
- Implement the rest.
- Add likely/unlikely attributes to
DEOPT_IF/EXIT_IF.
- Support GCC 15.0 if we determine the performance is good.
- Add option to Windows build script.
- Mention in Whats New. (Note: We NEED PGO, otherwise the perf is not very good on clang)
- Open new issue to add it as option on Windows build script.
- Open new issue to set it as auto detect on
--enable-optimizations on configure.
- Open new issue on improving the code quality, by moving some parameters into other places to free up registers.
Worries about new bugs
Computed goto is well-tested, so worrying about the new interpreter being buggy is fair.
I doubt logic bugs will be the primary one, as we are using the interpreter generator. This means we share common code between the base interpreter and the new one. If the new one has logic bugs, it is likely the base interpreter has it too.
The other one is compiler bugs. However to allay such fears, I point out that the GHC calling convention (the thing behind preserve_none has been around for 5 years1, and musttail has been around for almost 4 years2.
cc @pitrou as the original implementer of computed gotos, and @markshannon
Future Use
Kumar Aditya pointed out this could be used in regex and pickle as well. Likewise, Neil Schemenauer pointed out marshal and pickle might benefit from this for faster Python startup.
Has this already been discussed elsewhere?
https://discuss.python.org/t/a-new-tail-calling-interpreter-for-significantly-better-interpreter-performance/76315
Links to previous discussion of this feature:
No response
Linked PRs
Reacted by fruitoiz, Augusto Manaro, Виталий Дмитриев, EXHades, chai3, Alejandro Saucedo, bashirmindee, ניר, Ricardo Fernández Serrata and George V. Reilly Reacted by Dave Burkholder, Shantanu, Adam Turner, Tomas R., Donghee Na, Peter Bierma, hidaris, Chris Liu, Zen, Quentin Pradet and 35 more Reacted by Maxim Martynov, Donghee Na, Pieter Eendebak, Peter Bierma, hidaris, Michael H, Thanos, Quentin Pradet, Hugo van Kemenade, Kenneth Nielsen and 47 more Reacted by mborgerson, Alejandro Saucedo, Ricardo Fernández Serrata and ben Activitypitrou commented on Jan 7, 2025 Can you show what a typical tail-calling sequence looks like? Does it combine tail-calling with a computed goto as in this example from the protobuf blog post?
MUSTTAIL return op_table[op](ARGS); Fidget-Spinner commented on Jan 7, 2025 pitrou commented on Jan 7, 2025 diegorusso commented on Jan 7, 2025 How much performance is attributed to __attribute__((preserve_none)) alone? Fidget-Spinner commented on Jan 7, 2025 @diegorusso I did some experiments on WASI and esmcriptem (which do not support preserve_none). No speedup at all on those platforms which do not support (in fact, up to a 2x slowdown). So this is a negative without it. WolframAlph commented on Jan 7, 2025 FYI from Clang docs
preserve_none’s ABI is still unstable, and may be changed in the future.
Fidget-Spinner commented on Jan 7, 2025 @WolframAlph I think that doesn't matter because we're only using this on _PyEval_EvalFrameDefault's opcode handlers which are not external-facing. This is an internal implementation detail. Reacted by Antoine Pitrou diegorusso commented on Jan 7, 2025 Reacted by Jason Fried Reacted by Ken Jin, nitishxp, Erlend E. Aasland, Ilya Siamionau, taffey, vavanade and Ricardo Fernández Serrata diegorusso commented on Jan 7, 2025
@diegorusso I did some experiments on WASI and esmcriptem (which do not support preserve_none). No speedup at all on those platforms which do not support (in fact, up to a 2x slowdown). So this is a negative without it.
This is what I was expecting. The tail call by itself is not enough (actually I was expecting similar performance to computed goto) and you need preserve_none (like for the JIT) to make the difference.
Have you tested it on AArch64 as well? Fidget-Spinner commented on Jan 7, 2025
Have you tested it on AArch64 as well?
Not yet. I want to test it on the Faster CPython build bot for macOS (that has clang-19, so it's a fair comparison), but I do not have access to it. If you could run some benchmarks for this I would be really grateful! If you want a quick-and-dirty check that it's working, try just running the pystones benchmark. I got a 25% speedup with tail calls and LTO and PGO on (make sure you enable those, because it contributes like half the perf win for some reason). https://gist.github.com/Fidget-Spinner/e7bf204bf605680b0fc1540fe3777acf
And pass CC=clang-19 and all that. WolframAlph commented on Jan 7, 2025 @Fidget-Spinner If I understand correctly, the whole trick is:
musttail guarantees to jump to the next subroutine (if their signatures are the same), thus getting rid of call overhead (prologue, epilogue, stack space reservation, etc..).preserve_none puts burden of preserving registers on the caller. But every subsequent tail call is performed to the function with preserve_none attribute, therefore none of the opcode handlers spill registers (because we instructed so and because it won't need them anymore because of tail call) and just forward function arguments in registers through whole chain of calls.
Do I get it right? Fidget-Spinner commented on Feb 7, 2025 @chris-eibl I think a I merged a fix. Please report back if you find anything strange again. Thanks! Fidget-Spinner commented on Feb 7, 2025 added a commit that references this issue on Feb 7, 2025gh-128563: Clarify clarificatory tail calling wording in What's New (#… pablogsal commented on Feb 7, 2025
arm-neoverse-n1 is an Ubuntu 22.04 with gcc 11.4.0. In theory the 2 machines should have the same software stack. Tagging @pablogsal as I think he maintains that machine.
We have historically only upgrade the machine in very limited circumstances because that renders comparing benchmarks before the upgrade to the ones afterwards unreliable and confusing and that has caused many headaches so the policy so far has been not touch anything unless is required.
That was discussed two years ago so maybe we can explore this again Fidget-Spinner commented on Feb 8, 2025 Reacted by Chris Eibl, Nadeshiko Manju and John Hagen r-barnes commented on Feb 12, 2025 @Fidget-Spinner : I see in the What's New posting
This interpreter currently only works with Clang 19 and newer on x86-64 and AArch64 architectures. However, we expect that a future release of GCC will support this as well.
How does the architectural limitation arise?
Does the compiler refuse to apply preserve_none to other architectures because it hasn't been taught how? Or do other architectures possess limitations that prevent the compiler from generating the code preserve_none would require?
(Also: thanks for the great work! This is really cool.) Fidget-Spinner commented on Feb 13, 2025 @r-barnes the limitation arises because no one has implemented that in clang. I don't think it's architectural (apart for WASM) AlfieRichardsArm commented on Nov 7, 2025 Reacted by Diego Russo, Sergey Miryanov, Ken Jin, Chris Eibl and Richard Barnes Reacted by Diego Russo, Ken Jin, Chris Eibl and Richard Barnes
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|