I think Anton is replying to me in that LWN article IIRC. I personally didn't know C only had tail calls that late and learnt something new there!
On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.
A formal technical specification (TS) extension is already being drafted: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3582.pdf That's a step up from the usual proposals. I'm not sure what criteria is used to decide whether to first create a TS vs just incorporating a change into the working draft of the next standard.[1] _Defer also seems to be taking the TS route.[2]
Well, even if that lands on the official standard, that means C29 as probable release year for C2y, plus adoption of the exact form across compilers to be able to rely on it being available.
Woops, I meant to write tail call optimization not tail calls. Shouldn't have used the term interchangeably. Yeah I'm aware that C doesn't have proper tail calls. Thanks for the correction though.
I think Anton is wrong. Since C89 and before C23 calling an `int f();` function with arguments not matching the definition's actuals is UB. In C23 `int f();` became the same as `int f(void);`, so calling that function with any arguments is a compile-time error.
For variadic functions, if you use `va_start()`/`va_arg()`/`va_end()` to consume all the arguments, and leave no `va_list` alive, then the compiler can correctly generate a tail call from such functions.
This is an intuitive step and I kind of did something similar initially (I simplified the diagram a lot, but it was basically what you are suggesting). However, it slowed down the computed goto interpreter by 6% (though not the tail calling interpreter).
The other comment about interpreters being greatly affected by instruction cache is right. The other problem is that PGO in CPython's test suite could be improved and when you have the full thing as a switch-case and trigger the profiling mode, PGO then mistakenly thinks that the RECORD_INST_X section is hot (when it is clearly not). This causes a pessimization in the interpreter loop leading to the 6% slowdown.
Pablo is a great speaker and I love Tachyon! However, this is a different type of/target for profiling. Tachyon profiles the entire CPython interpreter, this blog post is just type profiling/recording and interpreter path profiling for the CPython core interpreter loop itself.
> I've never seen where the high level discussions were happening
Thanks for your interest. This is something we could improve on. We were supposed to document the JIT better in 3.15, but right now we're crunching for the 3.15 release. I'll try to get to updating the docs soon if there's enough interest. PEP 744 does not document the new frontend.
> does this mean each opcode is possibly split into two (or more?) stencils, with and without removed increfs/decrefs?
This is a great question, the answer is not exactly! The key is to expose the refcount ops in the intermediate representation (IR) as one single op. For example, BINARY_OP becomes BINARY_OP, POP_TOP (DECREF), POP_TOP (DECREF). That way, instead of optimizing for n operations, we just need to expose refcounting of n operations and optimize only 1 op (POP_TOP). Thus, we just need to refactor the IR to expose refcounting (which was the work I divided up among the community).
If you have any more questions, I'm happy to answer them either in public or email.
I also did some reading and experiments, so quickly talking about things I've found out re: refcount elimination:
Previously given an expression `c = a + b`, the compiler generated a sequence of two LOADs (that increment the inputs' refcounts), then BINARY_OP that adds the inputs and decrements the refcounts afterwards (possibly deallocating the inputs).
But if the optimizer can prove that the inputs definitely will have existing references after the addition finishes (like when `a` and `b` are local variables, or if they are immortals like `a+5`), then the entire incref/decref pair could be ignored. So in the new version, the DECREFs part of the BINARY_OP was split into separate uops, which are then possibly transformed into POP_TOP_NOP by the optimizer.
And I'm assuming that although normally splitting an op this much would usually cost some performance (as the compiler can't optimize them as well anymore), in this case it's usually worth it as the optimization almost always succeeds, and even if it doesn't, the uops are still generated in several variants for various TOS cache (which is basically registers) states so they still often codegen into just 1-2 opcodes on x86.
One thing I don't entirely understand, but that's super specific from my experiment, not sure if it's a bug or special case: I looked at tier2 traces for `for i in lst: (-i) + (-i)`, where `i` is an object of custom int-like class with overloaded methods (to control which optimizations happen). When its __neg__ returns a number, then I see a nice sequence of
_POP_TOP_INT_r32, _r21, _r10.
But when __neg__ returns a new instance of the int-like class, then it emits
_SPILL_OR_RELOAD_r31, _POP_TOP_r10, _SPILL_OR_RELOAD_r01, _POP_TOP_r10, etc.
Is there some specific reason why the "basic" pop is not specialized for TOS cache? Is it because it's the same opcode as in tier1, and it's just not worth it as it's optimized into specialized uops most of the time; or is it that it can't be optimized the same way because of the decref possibly calling user code?
I implemented most of the tracing JIT frontend in Python 3.15, with help from Mark to clean up and fix my code. I also coordinated some of the community JIT optimizer effort in Python 3.15 (note: NOT the code generator/DSL/infra, that's Mark, Diego, Brandt and Savannah). So I think I'm able to answer this.
I can't speak for everyone on the team, but I did try the lazy basic block versioning in YJIT in a fork of CPython. The main problem is that the copy-and-patch backend we currently have in CPython is not too amenable to self-modifying machine code. This makes inter-block jumps/fallthroughs very inefficient. It can be done, it's just a little strange. Also for security reasons, we tried not to have self-modifying code in the original JIT and we're hoping to stick to that. Everything has their tradeoffs---design is hard! It's not too difficult to go from tracing to lazy basic blocks. Conceptually they're somewhat similar, as the original paper points out. The main thing we lack is the compact per-block type information that something like YJIT/Higgs has.
I guess while I'm here I might as well make the distinction:
- Tracing is the JIT frontend (region selection).
- Copy and Patch is the JIT backend (code generation).
We currently use both. PyPy uses meta-tracing. It traces the runtime itself rather than the user's code in CPython's tracing case. I did take a look at PyPy's code, and a lot of ideas in the improved JIT are actually imported from PyPy directly. So I have to thank them for their great ideas. I also talk to some of the PyPy devs.
Ending off: the team is extremely lean right now. Only 2 people were generously employed by ARM to work on this full time (thanks a lot to ARM too!). The rest of us are mostly volunteers, or have some bosses that like open source contributions and allow some free time. As for me, I'm unemployed at the moment and this is basically my passion project. I'm just happy the JIT is finally working now after spending 2-3 years of my life on it :). If you go to Savannah's website [1], the JIT is around 100% faster for toy programs like Richards, and even for big programs like tomli parsing, it's 28% faster on macOS AArch64. The JIT is very much a community effort right now.
PS: If you want to see how the work has progressed, click "all time" in that website, it's pretty cool to see (lower is faster). I have a blog explaining how we made the JIT faster here https://fidget-spinner.github.io/posts/faster-jit-plan.html.
Thank you for your contributions to the Python ecosystem. It definitely is inspiring to see Python, the language to which I owe my career and interest in tech, grow into a performant language year by year. This would not have been possible without individuals like you.
Tier-ups for trace-based JITs have been explored before. You can find an example here https://dl.acm.org/doi/abs/10.1145/2398857.2384630 I know LBBV isn't technically tracing, but it's quite similar, so I think similar concepts apply.
These speedups have been verified by external projects. For example, a Python MLIR compiler that I follow has found a geometric mean 36% speedup moving from CPython 3.10 to 3.11 (page 49 of https://github.com/EdmundGoodman/masters-project-report)
Another academic benchmark here observed an around 1.8x speedup on their benchmark suite for 3.13 vs 3.10 https://youtu.be/03DswsNUBdQ?t=145
CPython 3.11 sped up enough that PyPy in comparison looks slightly slower. I don't know if anyone still remembers this: but back in the CPython 3.9 days, PyPy had over 4x speedup over CPython on the PyPy benchmark suite, now it's 2.8 on their website https://speed.pypy.org/ for 3.11.
Yes CPython is still slow, but it's getting faster :).
Disclaimer: I'm just a volunteer, not an employee of Microsoft, so I don't have a perf report to answer to. This is just my biased opinion.
As a data point, running a Python program I've been working on lately, which is near enough entirely Python code, with a bit of I/O: (a prototype for some code I'll ultimately be writing in a lower-level language)
(macOS Ventura, x64)
- System python 3.9.6: 26.80s user 0.27s system 99% cpu 27.285 total
- MacPorts python 3.9.25: 23.83s user 0.32s system 98% cpu 24.396 total
- MacPorts python 3.13.11: 15.17s user 0.28s system 98% cpu 15.675 total
- MacPorts python 3.14.2: 15.31s user 0.32s system 98% cpu 15.893 total
Wish I'd thought to try this test sooner now. (I generally haven't bothered with Python upgrades much, on the basis that the best version will be the one that's easiest to install, or, better yet, is there already. I'm quite used to the language and stdlib as the are, and I've just assumed the performance will still be as limited as it always has been...!)
I have a benchmark program I use, a solution to day 5 of the 2017 advent of code, which is all python and negligible I/O. It still runs 8.8x faster on pypy than on python 3.14:
$ hyperfine "mise exec python@pypy3.11 -- python e.py" "mise exec python@3.9 -- python e.py" "mise exec python@3.11 -- python e.py" "mise exec python@3.14 -- python e.py"
Benchmark 1: mise exec python@pypy3.11 -- python e.py
Time (mean ± σ): 148.1 ms ± 1.8 ms [User: 132.3 ms, System: 17.5 ms]
Range (min … max): 146.7 ms … 154.7 ms 19 runs
Benchmark 2: mise exec python@3.9 -- python e.py
Time (mean ± σ): 1.933 s ± 0.007 s [User: 1.913 s, System: 0.023 s]
Range (min … max): 1.925 s … 1.948 s 10 runs
Benchmark 3: mise exec python@3.11 -- python e.py
Time (mean ± σ): 1.375 s ± 0.011 s [User: 1.356 s, System: 0.022 s]
Range (min … max): 1.366 s … 1.403 s 10 runs
Benchmark 4: mise exec python@3.14 -- python e.py
Time (mean ± σ): 1.302 s ± 0.003 s [User: 1.284 s, System: 0.022 s]
Range (min … max): 1.298 s … 1.307 s 10 runs
Summary
mise exec python@pypy3.11 -- python e.py ran
8.79 ± 0.11 times faster than mise exec python@3.14 -- python e.py
9.28 ± 0.13 times faster than mise exec python@3.11 -- python e.py
13.05 ± 0.16 times faster than mise exec python@3.9 -- python e.py
And indeed that has proven the case. But my assumption was that Python had been so obviously designed with performance so very much not in mind, that it had ended up in some local minimum from which meaningful escape would be impossible. But I didn't overthink this opinion, and I've always liked Python well enough for small programs anyway, so I don't mind having it proven wrong.
On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.