> We have implemented an SQL database query compiler on top of this metaprogramming system and show that on TPC-H database benchmarks, copy-and-patch generates code two orders of magnitude faster than LLVM -O0 and three orders of magnitude faster than higher optimization levels. The generated code runs an order of magnitude faster than interpretation and 14% faster than LLVM -O0.

Unless I misunderstand, its mechanism is a caching system on top of clang+llvm: it recognises AST patterns and their corresponding bytecode – copying the "stencils" and patching in variables.

I'd be very eager to see the CPython benchmarks!

[0] https://dl.acm.org/doi/10.1145/3485513

Code generation as a process of generating code is orders of magnitude faster, but not the generated code, result of code generation.

An order of magnitude faster than interpretation. That's the interesting part for Python, I'd think.

In the talk on youtube, the author mentions that it’s not faster than mainline CPython yet (it is slightly faster than experimental off-by-default microoperation support it’s built on top of, but it was already slower than mainline, so it cancels out at best). I think the idea is for it to be merged, but only enabled by default once it becomes worth it; and that’s why the perf numbers aren’t advertised yet.

Still, I wonder what the expected peak improvement is. Looking at the current generated assembly, there’s definitely room to improve, but there’s only so much one can do without touching the data model.

> enable JIT codegen without sacrificing too much performance

This is the part I don't buy. The main point of a JIT is performance, so by definition I don't see it being enabled unless it improves performance across the board.

What I wonder is if the current approach, stated as "copy-and-patch auto-generated code for each opcode", can ever reach that point without being replaced by a completely different design along the way. AFAIK, as is, the main difference between running the interpreter loop composed of normally compiled opcodes and JIT copy-and-patching these opcodes is lack of the opcode dispatch logic running between each op - which is good, but also countered by slightly worse quality of the copied code.

Of course this approach produces a worse code than a full compiler by definition---stencils would be too rigid to be further optimized. A stencil conceptually maps to a single opcode, so the only way to break out of this restriction is to add more opcodes. And there are only so many opcodes and stencils you can prefare. But I think you are thinking too much about a possibility to make Python as fast as, say, C for at least some cases. I believe that it won't happen at all, and the current approach clearly points why.

Let's consider a simple CPython opcode named `BINARY_ADD` which has a stack effect of `(a b -- sum)`. Ideally it should eventually be compiled down to a fully specialized machine code something like `add rax, r12`, plus some guards. But the actual implementation (`PyNumber_Add` [1]) is far more complex: it may call at most 3 "slot" calls that may add or concatenate arguments, some of them may call back to a Python code.

So let's assume that we have done type specialization and arguments are known to be integers. That will result in a single slot call to `PyLong_Add` [2], which again is still complex because CPython has two integer representations. Even when they are both "compact", i.e. at most 31/63 bits long, it may still have to switch to another representation when the resulting sum is no longer compact. So a fully specialized machine code would be only possible when both arguments are known to be integers and compact and have one more spare bit to prevent an overflow. That sounds way more restrictive.

[1] https://github.com/python/cpython/blob/36adc79041f4d2764e1da...

[2] https://github.com/python/cpython/blob/36adc79041f4d2764e1da...

An uncomfortable truth is that all these explanations also almost perfectly apply to JavaScript---the slot resolution would be the `[[ToNumber]]` internal function and multiple representations will be something like V8's Smi. Modern JS engines do exploit most of them, but at the expense of extremely large codebase with tons of potential attack surfaces. It is really expensive to maintain, and people don't really realize that no performant JS engine was ever developed by a small group of developers. You have to cut some corners.

In comparison, CPython's approach is essentially inside out. Any JIT implementation will require you to split all those subtasks into small bits that can be either optimized out or baked into a generated machine code. So what if we start with subtasks without thinking about JIT in the first place? This is what a specializing adaptive interpreter [3] did. The current CPython already has two tiers of interpreters, and micro-opcodes can only appear in the second tier. With them we can split larger opcodes into smaller ones, possibly with optimizations, but its performance is limited by the dispatch logic. The copy-and-patch JIT is not as powerful, but it does eliminate the dispatch logic without large design changes and it's a good choice for this purpose.

In the best scenario, it will eventually hit the limit of what's possible with copy-and-patch and a full compiler will be required at that point. But until that point (which may never come as well), this approach allows for a long time of incremental improvements without disruption.

[3] https://peps.python.org/pep-0659/

> Of course this approach produces a worse code than a full compiler by definition---stencils would be too rigid to be further optimized.

Yeah, but that's not what I meant by "worse code". I just meant that even being aware this is a naive copy-and-patch JIT, my first impression was that the code was slightly worse than I expected. I don't expect the compiler to do any magic on a small code slice; I only claimed that there's "room to improve" in the currently generated code, though I may be totally wrong on whether it's actually possible to achieve by "just convincing clang" and without manually messing with the asm.

> But I think you are thinking too much about a possibility to make Python as fast as, say, C for at least some cases.

I never said this about CPython, quite the opposite.

> I believe that it won't happen at all

(FWIW, if we're talking long-term and about Python in general, it already did happen, PyPy (and modern JS runtimes) are good examples of this being possible in principle. But being able to make a language orders of magnitude faster (with some major asterisks too) doesn't mean I expect the same from the CPython implementation.)

As for your example with integer adding, I totally agree with all you said, and that's exactly what I meant by "there’s only so much one can do without touching the data model".

> In the best scenario, it will eventually hit the limit of what's possible with copy-and-patch and a full compiler will be required at that point. But until that point (which may never come as well), this approach allows for a long time of incremental improvements without disruption.

That's why in my initial message I said I wonder about expected peak improvement. I won't be surprised if it (together with theorized uop optimizations) barely exceeds single-digit percent perf gains, which would of course be still totally worth it. And even it's more, well, even better :) And in the worst case - which I hope won't happen - the point you mentioned is today, and copy-and-patch would never be worth enabling by itself.

Ah, so you meant that even all of them including specializing interpreter and copy-and-patch JIT may not give a reasonable speedup. But I think you have missed the fact that specializing interpreter has already landed on 3.11 and provided 10--60% speedup. So specialization really works, and copy-and-patch JIT should allow finer-grained uops which can have an enormous impact on performance.

On the other hand, it is possible that copy-and-patch JIT itself turns out to be useless even after all the work. In this case there is no other known viable way to enable JIT without disruption, so JIT shouldn't be added to CPython. I should have stressed this point more, but "incremental" improvements are really important---it was a primary reason that CPython didn't even try to implement JIT compilation for decades after all. CPython can give them up, but then there is one less reason to use (C)Python, so CPython never did so. (GIL is the same story by the way, and the current nogil effort is not possible without other performance improvements that outweigh a potential overhead in the single-threaded setting.)

> As for your example with integer adding, I totally agree with all you said, and that's exactly what I meant by "there’s only so much one can do without touching the data model".

If the data model refers to the publicly visible portion of the interface, I don't think so. Even JS runtimes didn't require any change to the public interface, and CPython itself already caches lots of the data model for the sake of performance. I'm not aware of attempts like shape optimizations, but it might be possible to extend the current `__slots__` implementation to allow the adaptive memory layout.

It seems like the copy and patch approach is sort of somewhere inbetween an interpreter and a traditional JIT, and the authors of the original copy and patch paper seem to be trying to use it to replace things like the baseline compiler in the two-tier baseline/optimizing compiler strategy used for things like webassembly.

Because of this, is it really necessary to add tracing and try use a two tier interpeter/copy-and-patch JIT approach for this python JIT? Wouldn't it make more sense to try to get it to be fast enough that the JIT can be used alone?

https://arxiv.org/abs/2011.13127

I wrote a simple toy JIT for a Javascript-like language in jitcompiler.c. It might be useful for others to learn from (I'm a beginner too!) because it's so simply written and not complicated. It's about ~2400 lines of C: frontend and backend. I do lazy patching of callsites, I haven't got anywhere near as advanced as tracing or copy-and-patching. Much of the code I wrote for this JIT was written in Python and ported to C such as register allocation, graph colouring, precolouring and "A Normal Form". The Java Virtual Machine has a template interpreter which is interesting to research.

I haven't got around to encoding amd64 x86_64 instructions as bitmasks yet, so I've hardcoded it which is another ~2000 lines of code :-)

[1]: https://github.com/samsquire/compiler see jitcompiler.c

I don't want to spoil anything, but please read the PR description. You won't regret it (or your money back!).

You get downvoted on Hacker News if you don't use English?

https://youtu.be/HxSHIpEQRjs

i'm skeptical of this line

> The patching step rewrites pre-determined places in the binary code, which are operands of machine instructions, including jump addresses and values of constants (stack offsets and literal values). Despite patching binary code, however, the system does not need any knowledge of platform-specific machine instruction encoding and is thus portable.

like, i think if that were possible then we wouldn't need new linker relocation types for risc-v? how are you going to patch an auipc or st instruction to have the right stack offsets and memory addresses without knowing about the weird platform-specific details like how you have to increment the auipc immediate field to compensate for the sign-extension of the associated addi or jump field in the case where its high bit is set?

two of the most influential systems using this stencil technique, as i understand it, include bellard's qemu (02005) https://www.usenix.org/legacy/event/usenix05/tech/freenix/fu... (cited in xu and kjolstad's bibliography) and massalin's synthesis (01992) https://dl.acm.org/doi/10.5555/143219 (not cited)

synthesis's quaject object system was notable for generating code at object instantiation time, so that dynamic method dispatch was implemented by branching to a subroutine at a given offset from the receiver's address, instance variables could be located in immediate operands of instructions, and the program counter served as the receiver pointer (instance variable accesses could be pc-relative). unfortunately massalin never published synthesis itself, just papers about it

That knowledge is encoded into the relocation type (e.g. R_X86_64_64) for given ABI. So the system does know about relocations, and some relocation types will be specific to a single architecture (R_RISCV_CALL_PLT in this example, I think?). But that's all you need to know about those architectures.

usually, and certainly to get the performance numbers they claim, things like scrambling the immediate bits and putting 20 bits of the immediate in one instruction and 12 bits in another are also considered platform-specific machine-instruction encoding, but you could imagine a system which supports sticking arbitrary bitfields in arbitrary places

If there is such an architecture, yeah the system may have to support them, or more accurately: relocations would be defined for them which have to be implemented by the system. But that's still a tiny portion of the actual instruction coding. I believe most people including authors would imagine something like an assembler or disassembler as a comparison, so pedantry aside, the claim is almost true.

i don't think the distinction is pedantic between a compiler that needs custom code for each new machine instruction encoding and one which can support a new architecture just by giving it a data file (for some reasonable set of new architectures, anyway). the paper claims that their system is the latter, and i don't believe it

Also, Conventional Commits are mostly pointless. Linux-style commit message conventions are enough.

And eh, conventional commits seem like pointless bureaucracy to me.

Or maybe it's another weird pun on 404 Not Found? I can't tell by now...

I don't code linearly like "first I need feature A, then I code feature B which is needed for feature C, and so on"

It's usually a bit all over the place and it's not clear what depends on what until I start reaching the end.

So to do this properly I'd need to spend a day or two rewriting or making a new branch that cleanly adds everything in order. Hopefully in a way that doesn't leave master in a broken state when reverting tail commits.

In addition, when doing multiple pull requests for a single high level feature, you might get some comments about pull request "C" that would require changes in pull request "A"

I normally go through every single individual commit when reviewing something and find the commit messages extremely helpful to understand what some change is supposed to do.

Yes, cleaning up your commits takes some time butt I don't see an alternative if you don't work alone and want your code to stay maintainable.

If the commit is wrong, it shouldn't be there. I expect every commit in a Pull Request to be functional on its own or I am not going to approve it in the first place. Git has tools to rewrite your commit history and you should use them.

The whole point is that I should be able to revert individual commits without code breaking. At least that is the ideal. A clean version history matters a lot of the people maintaining your code down the line.

I think what you say is definitely the goal for day-to-day contributions.

However, there are changes to a code base that are more "Manhattan project" in nature where not all changes can be neatly packaged into their own commits, OR the PR author kind of needs to re-do their coding on a clean room branch. Which is significant overhead.

Being able to undo a commit is a means to an end, not the ultimative goal.

That's what a DVCS like git makes easy to do, it's really worth learning.

Honestly, I frequently do this for my own personal projects since I'm lazy, but if I'm submitting something to a big open source project I always clean it up first.

Some truly awful standard for formatting commit messages, how to do something that has at best dubious value to begin with, is a fantastic way to give the appearance of work without the need for skill or ability or spending time trying to get useful work done, a true boon to incompetents and hangers on. It's also a great way to snipe someone's amazing work and put yourself in a position to critique them with 1/1000th of the effort of accomplishing something useful.

In particular, I had experience with Wine. Having useful commit messages allows you to do bisects and trace down regressions with more ease than cross-checking messages with some external ticket system, and when you have a lot of people contributing to a project it's easier to see what they're doing when they try to do a patch.

I also believe though, that it is good practice to help your colleagues when they do need to find an issue in a project where a lot of different people can work on.

Putting what im saying another way, in a project with pull requests, commit messages are redundant with the text typed into the pr and the comments on same. We should just carbon copy those onto the merge commit and forget per commit messages.

Seriously, please think of the poor soul having to maintain you legacy code when the JIRA is long gone or the external contractor who doesn't even get access to it in the first place.