Reflections on 2 years of CPython's JIT Compiler

More importantly, there's nothing like locals[] or __getattribute__.

Python is also choosing to play with one hand behind its back; e.g., the “no extension API changes” rule which means any hope of a faster value representation (one of the most important factors in making a dynamic language fast!) goes out the window, refusing to change the iterator API (which means that throwing and handling exceptions is something that needs to be handled by the fast path of basically everything), and so on.

Google has been pouring huge amounts of effort into making their JS interpreter fast for many years at this point. They have a lot more resources than the Python foundation.

What are examples of those semantics? I'm guessing rebindable functions (and a single function/variable namespace), eval(), and object members available as a dict.

I'm sort of surprised I'm not seeing any modernized dynamic scripting languages coming out lately, despite the general trend towards static languages. A fast dynamic language, with a day-one concurrency story, and some other key feature that pushes it ahead seems possible to me. (I dunno, maybe a nice story for binding to Rust instead of binding to C at this point could be enough to lift a language off?) I don't see any reason why dynamic scripting languages as a category couldn't do that. The ones we have now don't, not because the category makes it impossible, but because by the time that was desirable they just had too much baggage, and are all still struggling with it even a decade after they started.

And profile-guided optimization (PGO) for static languages turned out to be pretty good at revealing those “only apparent at runtime” optimizations.

That's like the joke that dynamic languages are static languages, but with only one type: hash table.

Javascript and common lisp don't have object models that are as anathema to optimization as python does. Well, CLOS is pretty bad, but at least the badness is typically isolated.

You missed the part where Android moved into caching JIT code with a mix AOT mode compilation, since Android 7 thus avoiding those issues. Latest version is Android 16, many other optimization happened since then.

Also that Android followed up on Windows Phone model, their mistake was making the AOT compilation on the phone instead of on the store like Windows Phone was doing.

JITs are very capable, provided people also design with them in mind.

The clever Apple with AOT failed against this now famous benchmark, against tracing GC languages, using a JIT.

https://github.com/ixy-languages/ixy-languages

Probably the methods they use as well.

I may not be completely accurate on this because there's not a whole lot of information on how Python is doing their thing so...

The way (I believe) Python is doing it is to take code templates and stitching them together (copy & patch compilation) to create an executable chunk of code. If, for example, one were to take the py-bytecode and just stitch all the code chunks together all you can realistically expect to save is the instruction dispatch operations, which the compiler should make really fast anyway, which leaves you at parity with the interpreter since each code chunk is inherently independent so the compiler can't do its magic on the entire code chunk. Basically this is just inlining the bytecode operations.

To make a JIT compiler really excel you'd need to do something like take all the individual operations of each individual opcode and lower that to an IR and then optimize over the entire method using all the bells and whistles of modern compilers. As you can imagine this is a lot more work than 'hacking' the compiler into producing code fragments which can be patched together. Modern compilers are really good at these sorts of things and people have been trying to make the Python interpreter loop as efficient as possible for a long time so there's a big hurdle to overcome here.

I've (or more accurately, Claude) has been writing a bytecode VM and the dispatch loop is basically just a pointer dereference and a function call which is about as fast as you can get. Ok, theoretically, this is how it works as there's also a check to make sure the opcode is within range as the compiler part is still being worked on and it's good for debugging but foundationally this is how it works.

From what I've gleaned from the literature the real key to making something like copy & patch work is super-instructions. You take common patterns, like MULT+ADD, and mash them together so the C compiler can do its magic. This was maybe mentioned in the copy & patch paper or, perhaps, they only talked about specialization based on types, don't actually remember.

So, yeah, if you were just competing against a basic tree-walking interpreter then copy & patch would blow it out of the water but C compilers and the Python interpreter have both had million of people hours put into them so that's really tough competition.

> Python has made many breaking changes after 2->3 as well.

Aside from the `async` keyword (experience with which seems like it may have driven the design of "soft keywords" for `match` etc.), what do you have in mind that's a language feature as opposed to a standard library deprecation or removal?

Yes, the bytecode changes with every minor version, but that's part of their attempts to improve performance, not a hindrance.

Having had no experience in JIT development but having followed the faster cpython JIT progress on a weekly basis, I do find their JIT strategy a bit weird. The entire decision seemed to revolve around not wanting to embebed an external JIT/compiler with all that entails...

At first I thought their solution was really elegant. I have an appreciation for their approach, and I could have been captivated myself to choose it. But at this point I think this is a sunk cost fallacy. The JIT is not close to providing significant improvements and no one in the faster cpython community seems to be able to call the shot that the foundational approach may not be able to give optimal results.

I either hope to be wrong or hope that faster cpython managment has a better vision for the JIT than I do.

Thanks for the response Maxime, your work on YJIT is astounding. The speedup from YJIT was a huge improvement over cRuby or MJIT, and the work was done relatively quickly compared to Python which seems to always be talking about this JIT but we are never seeing a comparable release.

Hey Maxime!

> whereas AFAIK the Python JIT project was lead by a student.

I am definitely not leading the team! I am frankly unqualified to do so lol. The team is mostly led by Mark Shannon, who has 10+ years of compiler/static analysis experience as well. The only thing I initially led was the optimizer implementation for the JIT. The overall design to choose tracing, to use copy and patch, etc. were other people.

> However they decided to ignore my advice and go with their own unproven approach.

Your advice was very much appreciated and I definitely didn't ignore your advice. I just don't have much say over the initial architectural choices we make. We're slowly changing the JIT based on data, but it is an uphill battle like you said. If you're interested, it's slowly becoming more like lazy basic block versioning https://github.com/python/cpython/issues/128939

You did great work on YJIT, and I am quite thankful for that.

> I confess that somewhat surprises me, as I would expect getting machine code generated would be a main source of speed up for a JIT?

My understanding is that the basic copy-and-patch approach without any other optimizations doesn’t actually give that much. The difference between an interpreter running opcodes A,B,C and a JIT emitting machine code for opcode sequence A,B,C is very little - the CPU running the code will execute roughly the same instructions for both, the only difference is that the jit avoids doing an op dispatch between each op - but that’s already not that expensive due to jump threading in the interpreter. Meanwhile the JIT adds an extra possible cost of more work if you ever need to jump from JIT back to fallback interpreter.

But what the JIT allows is to codegen machine code corresponding to more specialized ops that wouldn’t be that beneficial in the interpreter (as more and smaller ops make it much worse for icaches and branch predictors). For example standard CPython interpreter ops do very frequent refcount updates, while the JIT can relatively easily remove some sequences of refcount increments followed by immediate decrements in the next op.

Or maybe I misunderstood the question, then in other words: in principle copy-and-patch’s code generation is quite simple, and the true benefits come from the optimized opcode stream that you feed it that wouldn’t have been as good for the interpreter.

A byte code interpreter is, very approximately, a lookup table of byte code instructions that dispatches each instruction to highly optimized assembly.

This will almost certainly outperform a straight translation to poorly optimized machine code.

Compilers are structured in conceptual (and sometimes distinct) layers. In a classic statically-typed language will only compile-time optimizations, the compiler front-end will parse the language into a abstract syntax tree (AST) via a parse tree or directly, and then convert the AST into the first of what may be several intermediate representations (IRs). This is where a lot of optimization is done.

Finally the last IR is lowered to assembly, which includes register allocation and some other (peephole) optimization techniques. This is separate from the IT manipulation so you don’t have to write separate optimizers for different architectures.

There are aspects of a tracing JIT compiler that are quite different, but it will still use IR layers to optimize and have architecture-dependent layers for generating machine code.

The way I understand it, the machine code generator emits machine code for some particular piece of bytecode (or whatever the JIT IR is). This is almost like an assembler and probably has templates that it expands. It is important for this machine code to be fast, but it each template is at a pretty low level, and lacks the context for structural optimizations. The optimizer works at a higher level of abstraction, and can make these structural optimizations. You can get very large speed-ups when you can remove code that isn't necessary, or emit equivalent code that has a lower complexity or memory overhead. Typical examples of things optimizers do are * use registers instead of memory for function arguments * constant folding * function inlining * loop unrolling

I don't know if that's exactly how it works for this particular effort, but that would be my expectation.