A copy-and-patch JIT compiler for CPython

https://github.com/python/cpython/pull/113465

by polyrand • 3 years ago

270 68 3 years ago

github.com

1f60c• 3 years ago

This is awesome.

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

Ringz• 3 years ago

I read it first and also wanted to post a corresponding note here. You were faster. It's really worth it. :•)

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

chc42• 3 years ago

Sweet! I tried playing around with implementing a copy-and-patch style JIT in Rust before, but unfortunately between the lack of `ghccc`-style register-heavy calling convention and (still!) having no way to guarantee tailcalls, rustc doesn't make it very easy and I gave up.

yunruse• 3 years ago

The linked paper [0] by Xu and Kjolstad on copy-and-patch JIT is delightfully intriguing! For its original "C-like language" implementation it promises:

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

chc42• 3 years ago

It doesn't cache ASTs or bytecode, or invoke clang/LLVM at runtime. It copies as bytes the assembly body of the compiled functions that act as stencils, using ELF relocations as locations of where to patch in values.

Retr0id• 3 years ago

My first impression is that this sounds clever but also quite fragile, because compilers love to change the minutiae how they emit their relocations between versions or compilation options.

adrian174• 3 years ago

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

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.

lifthrasiir9• 3 years ago

The goal is to enable JIT codegen without sacrificing too much performance and adding too much maintenance burden, and a functional JIT implementation needs a few more components other than that---most notably a facility to monitor and trace function calls for the eventual JIT compilation. Consider the OP to be one of intermediate goals, not the eventual goal.

adontz• 3 years ago

Their use of words is quite misleading.

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

e12e• 3 years ago

Thank you. I was trying to figure out why clang -O0 was faster than -O3...

zodiac• 3 years ago

I think there’s syntactic ambiguity whether “faster” modifies “generates” or “code”

rst• 3 years ago

... which, in a weird bit of back-to-the-future, is exactly how Grace Hopper's original "compilers" worked, compiling (hence the term) patched versions of hand-built stencils. (The first few, A-0 and immediate successors, had program text that named the stencils directly, like what we'd now call directives for a macroassembler; later, MATH-MATIC and FLOW-MATIC added what we'd now call front ends which used the stencil language as an internal intermediate code.)

nickpsecurity• 3 years ago

Arxiv version:

https://arxiv.org/abs/2011.13127

nialse• 3 years ago

I believe this is the talk about the python JIT by Brandt Bucher.

https://youtu.be/HxSHIpEQRjs

vidarh• 3 years ago

Their "binary stencils" reminds me of Michael Franz' "Code Generation on the Fly: A Key to Portable Software". Franz generated the templates at runtime by caching parameterized code fragments from doing code gen on a version of the AST effective encoded in an lzw like way, so that each partial AST node would just have code generated once, so it didn't go as far as this but the stencil/template approach was there.

sighansen• 3 years ago

The commit messages are terrible. In my opinion, conventional commit messages [0] should be used for a clean commit history.

[0] https://www.conventionalcommits.org/en/v1.0.0/

theyinwhy• 3 years ago

Something more descriptive than "Grrr" would be nice I guess.

Kwpolska2• 3 years ago

CPython seems to use squash merges, which means only one commit will end up on the main branch after merging this PR. The history on branches is irrelevant and can be completely messy, full of merges and other experiments; the main branch has one commit per actual feature/change.

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

hnfong• 3 years ago

With only +1,722 lines added, even if the commits were eventually squashed upon landing, I'd consider it good etiquette to tidy up changes to maybe a handful of logical commits instead of pushing 404 raw commits.

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

da39a3ee4• 3 years ago

Being honest though, the guy's commit messages influence my prior on how reliable and well-designed his code will be.

meowface• 3 years ago

Yes, but for such a significant contribution to a huge project it's good etiquette to squash on your own before submitting the PR. (Not that it means the PR shouldn't be reviewed and accepted.)

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.

ltbarcly33• 3 years ago

I question the value of commit messages at all. Sure, at some level you need a summary of what a change is trying to do, but we have that at 5 levels now and they are completely redundant. Generally there is a ticket in some system for tracking changes, whether it's Jira or Github itself or some other system. Then you have a PR/MR that is attached to a branch which you are trying to have merged. Then there are the commit messages themselves. These are all completely redundant to each other, and nobody in their right mind should want all of these at the same time. It's too many places to look for the same exact information, there's no reason to maintain it in more than one place.

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.

wavemode• 3 years ago

I think Jira messages are generally written from a product perspective ("here's what we want") whereas PR's are written from an implementation perspective ("here's how we did it"). And then the PR description ought to just become the squashed commit message (at least that's how my current company does it).

etra0• 3 years ago

I value the commit messages in the context where you develop a tool that has to be run widely.

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.

cardanome3• 3 years ago

Code tends to live longer than projects management tools like JIRA. The version history should always be understandable from itself without access to external software. Not to mention that JIRA tickets should be based on concrete user stories while commit messages describe implementation details, they are different layers of concern. As for individual commit messages, you need to so the poor soul reviewing your MR knows what the hell you are doing.

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.

seba_dos12• 3 years ago

They are really bad and I would feel bad if I presented something like that to someone for a review (not just messages - most of those commits shouldn't exist at all). That said, the MR in question is marked as a draft, so anything goes at that point.

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

samsquire• 3 years ago

Wow! Thank you for your hard work. I use python for all experimental work so this would speed up my scripting work, such as processing data from API calls or filesystem. Would be good if it could speed up Flask or Django applications.

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

kragen4• 3 years ago

xu and kjolstad's paper https://dl.acm.org/doi/pdf/10.1145/3485513 (cc-by) looks pretty worth reading; the abstract makes exciting claims

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

lifthrasiir9• 3 years ago

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?

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.

kragen4• 3 years ago

sure, you don't need to know the opcodes, just the encodings, but the claim in the paper seems to be stronger than that

mgaunard2• 3 years ago

PR is unreadable due to being redacted like a story with irrelevant details.

tecleandor• 3 years ago

It's all explained, including a 50 minutes talk, in the linked issue: https://github.com/python/cpython/issues/113464

mgaunard2• 3 years ago

A link to a video is not a good PR writeup.

It needs to be concise, precise, and to the point.

erlend_sh• 3 years ago

For another very recent implementation of copy-and-patch, written in Zig, see Cyber-lang: https://cyberscript.dev/0.3/index.html

A copy-and-patch JIT compiler for CPython

Related Stories