Reflections on 2 years of CPython's JIT Compiler

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.

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.

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

> 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.

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.

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.

> 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.