Repository navigation
A new tail-calling interpreter for significantly better interpreter performance #128563
Description
Feature 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?
Links to previous discussion of this feature:
No response
Linked PRs
- gh-128563: A new tail-calling interpreter #128718
- GH-128563: Add new frame owner type for interpreter entry frames #129078
- gh-128563: Move labels in ceval.c to bytecodes.c #129112
- gh-128563: Move lltrace into the frame struct #129113
- gh-128563: Move GO_TO_INSTRUCTION and PREDICT to cases generator #129115
- GH-128563: Don't leave frame->lltrace uninitialized #129417
- GH-128563: Simplify recursion check in _PyEval_EvalFrameDefault #129481
- GH-128563: (Re)move some labels, to simplify implementing tailcalling interpeter. #129525
- GH-128563: Generate opcode = ... in instructions that need opcode #129608
- gh-128563: Document the tail-calling interpreter #129728
- gh-129737: Fix help message for tail calling interpreter configuration #129754
- gh-128563: Move assignment of opcode into ifdef #129803
- gh-128563: Clarify tail calling interpreter is not TCO #129809
- gh-128563: Clarify clarificatory tail calling wording in What's New #129812
- gh-128563: Add correction note to tail call in whats new #130908
- gh-128563: Clarify wording in Whats new for Tail call #130911
Activity
pitrou 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?
Fidget-Spinner commented on Jan 7, 2025
Mark gives a pretty good example here faster-cpython/ideas#642 (comment)
pitrou commented on Jan 7, 2025
Neat, thank you!
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
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.
diegorusso commented on Jan 7, 2025
Anyway I pinged the GCC team at Arm and a ticket has been created to implement preserve_none in GCC https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118328
diegorusso commented on Jan 7, 2025
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
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:
Do I get it right?
42 remaining items
gh-128563: Move assignment of opcode into ifdef (GH-129803)
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!
gh-128563: Clarify tail calling interpreter is not TCO (#129809)
Fidget-Spinner commented on Feb 7, 2025
No regression either on the Microsoft machine https://github.com/faster-cpython/benchmarking-public/tree/main/results/bm-20250207-3.14.0a4+-a3d5aab .
gh-128563: Clarify clarificatory tail calling wording in What's New (#…
pablogsal commented on Feb 7, 2025
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
@chris-eibl I can confirm the lastest patch I made seems to have restored most of the performance on ancient compilers to within a 1% margin 🥳 . I think the rest is noise https://speed.python.org/changes/?tre=10&rev=a1417b211f0bb9582b00f7b82d0a43a3bcc9ed05&exe=12&env=1
pythongh-128563: A new tail-calling interpreter (pythonGH-128718)
r-barnes commented on Feb 12, 2025
@Fidget-Spinner : I see in the What's New posting
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)
gh-128563: Add correction note to tail call in whats new (#130908)
gh-128563: Clarify wording in Whats new for Tail call (#130911)
python314: add variants for experimental features
AlfieRichardsArm commented on Nov 7, 2025
Just to note AArch64 preserve_none support has now been added for the upcoming GCC 16 release.