4 ms·
Copy-and-Patch: Fast compilation for high-level languages and bytecode (2020)
- lumpa 2y agoIs this the technique they are using in Python's new JIT?
- Qem 2y agoYes. This is the algorithm chosen for the CPython JIT under development, scheduled for inclusion from 3.13 onwards. See https://m.youtube.com/watch?v=HxSHIpEQRjs https://m.youtube.com/watch?v=HxSHIpEQRjs
- deleted 2y ago[deleted]
- djoldman 2y ago(2020)
- thrtythreeforty 2y agoI love this approach. Has any independent toolkit evolved to help do this? Or have all projects rolled their own?
- Iwan-Zotow 2y agoCpython in beta
- thrtythreeforty 2y agoSure but from looking at the patches, it seems like theirs is tied into the CPython build and infrastructure. I am talking about a dedicated library which can be dropped into a variety of superprojects to help them implement a JIT.
- samatman 2y agoThere's Deegen, which is being used to build a LuaJIT successor. https://github.com/luajit-remake/luajit-remake https://github.com/luajit-remake/luajit-remake From what I gather, Deegen is independent of the VM in that repo, but lives there afaik.
- mrugiero 2y agoI mailed the authors a few months ago and indeed, it lives there but is independent-ish. They don't consider it ready to use for anything else other than experiments, though.
- samatman 2y agoIt is utterly baffling that people are downvoting this comment. The repo I link to here is by Haoran Xu, one of the authors of the paper. Y'all need to chill out.
- ec109685 2y agoBlog post about the approach here: https://sillycross.github.io/2023/05/12/2023-05-12/ https://sillycross.github.io/2023/05/12/2023-05-12/
- fiddlerwoaroof 2y agoI think libgccjit uses this technique or can use it: it reminds me of things I read about the elisp JIT in newer versions of emacs
- sambeau 2y agoThis is interesting. I came up with a very similar idea in the late 1990s to JIT a lazy functional language. The idea was to only compile the code that you needed to execute next, so you could run lazy code without needing to compile it (recursing across infinite lists, etc). It had templates with holes (for things like cons etc.) I stuck my paper on it under Prof Phil Wadler's office door and ran away. I have no idea if he ever read it :D
- alserio 2y agoLink to the HTML version for those who need it and to help spread the knowledge of the wonderful arxiv ar5iv tool: https://ar5iv.labs.arxiv.org/html/2011.13127 https://ar5iv.labs.arxiv.org/html/2011.13127
- deleted 2y ago[deleted]
- foota 2y agoThere's some related discussion here: https://news.ycombinator.com/item?id=40406194 https://news.ycombinator.com/item?id=40406194
- dang 2y agoThanks! Also related: A copy-and-patch JIT compiler for CPython - https://news.ycombinator.com/item?id=38769874 https://news.ycombinator.com/item?id=38769874 - Dec 2023 (68 comments) Copy-and-Patch: Fast JIT Compilation for SQL, WebAssembly, and Others - https://news.ycombinator.com/item?id=28547057 https://news.ycombinator.com/item?id=28547057 - Sept 2021 (7 comments)
- philzook 2y agoWe found these ideas very useful for doing micropatches, post hoc intrafunction binary patches, using off the shelf compilers. At the least, a voice of support that these kinds of calling convention control is useful. - Copy and Micropatch: Writing Binary Patches in C with Clang preserve_none https://www.philipzucker.com/permutation_compile/ https://www.philipzucker.com/permutation_compile/ - https://github.com/purseclab/Patcherex2/pull/31 https://github.com/purseclab/Patcherex2/pull/31 A pull request to the PatcherEx2 library
- boywitharupee 2y ago> At runtime, C&P generates executable code by copying the object code and patching the holes with runtime known values. how would this work on OSs under hardened runtime rules?
- mrugiero 2y agoThe same as with any other JIT runtime: you do your transformations first, and then you do the `mprotect` call that turns write permissions off and execution permissions on. The only caveats I can think of (`pledge`d not to use `mprotect`, marked most of the address space with `mimmutable`) apply to all other JITs too. The gist is that you operate on a copy of code, and that copy is in a writable page until it's ready to run, so you never violate the W^X rule.
- IAmLiterallyAB 2y agoOr you do what V8 does with WebAssembly and just use WX pages because doing it correctly is "too hard" to do without losing performance.
- mrugiero 2y agoDoes that even work in W^X platforms? Context for my response has that assumption, we can't simply throw it out the window, right? I think I read somewhere about making two mappings to the same physical page (one W, one X), are you referring to that? (I'd still need to know how that works as it kinda defeats the protection, the OS should prohibit that, right?)
- IAmLiterallyAB 2y agoOh, for sure what I said wouldn't work on a W^X system. I was just pointing out that one of the most widely used JIT software uses WX pages. What OSes prohibit that? Linux doesn't (well, I think it can with SeLinux maybe?). OpenBSD might?
- 2y ago
- vlovich123 2y agoIt’s kind of annoying how static compilers insist on figuring out everything from scratch. Even in an LTO build, the amount of code that changes between two consecutive commits is typically minimal - rather than the very coarse ccache-style, it would be nice if compilers had nicer ways to cache state across execution so that unchanged code constructs could just emit the same assembly as last time without needing to do anything else.
- JoshTriplett 2y agoRust's incremental compilation does this. Unfortunately, it doesn't help with linking, but it speeds up compilation by reusing everything that didn't change.
- vlovich123 2y agoI could be wrong but I think Rust’s incremental compilation is still pretty coarse. LLVM is where this would need to be implemented and that’s a tall ask (i.e. skipping expensive computation when the AST is the same or close enough to a previously computed result). And Rust’s incremental compilation doesn’t apply to LTO. There’s only so much you can do from outside the compiler toolchain.
- saagarjha 2y agoIf you’re going for very fast codegen, sure. But in a production build typically you have problems like “this shifted by one instruction so every non-relative branch beyond it needs to be patched”.
- vlovich123 2y agoHmm... if only there were some scholarly article about how to patch binary snippets in a fast way?
- astromaniak 2y ago[dead]
- 2y ago
- bjourne 2y agoAfaik, this technique is called threading (https://en.wikipedia.org/wiki/Threaded_code https://en.wikipedia.org/wiki/Threaded_code) and has been used in most bootstrap compilers for decades.
- mrugiero 2y agoI don't think this counts as threading, though it makes use of it. Threading mostly removes the dispatch overhead, but you still have a general function per instruction, a function call, and an inability to inline constants. Copy and patch could be thought of as a generalization of threading in the sense that you still precompile code for your instructions, but instead of calling that code you poke holes in it to replace constants you only know at runtime, then make a single callable program out of those instead of jumping around for every instruction. There is a prior, very similar approach in GNU Jitter, but it uses only the compiler and some magic rather than the linker for marking spots to replace. I read about it by mention of moonchild in a thread[0] linked by foota here. [0]: https://news.ycombinator.com/item?id=40410420 https://news.ycombinator.com/item?id=40410420
- sitkack 2y agoThey are both super close in the latent space. I think you could design for threading, but then copy into place and NOP out what you don't need, or wire in the right constants, etc.
- mrugiero 2y agoThat's true. But it's still a stretch to say they are the same thing. That's why I said it can be seen as generalizing the approach.
- MaxBarraclough 2y agoThreading doesn't necessarily mean following the full function-call convention on every transition. A switch/case approach is one way, but it's also possible to jump intra-function without following the calling convention, i.e. a goto with a pointer-based target. I say possible in the sense that hardware supports it. The standard C language doesn't support this, but GCC's GNU C does support it as one of its extensions. The GNU Jitter author wrote about this, see page 48, referred to as page '17', of this PDF: https://ageinghacker.net/talks/jitter-slides--saiu--ghm2017--2017-08-25.pdf https://ageinghacker.net/talks/jitter-slides--saiu--ghm2017-... See also Gforth writing about the same technique: https://gforth.org/manual/Threading.html https://gforth.org/manual/Threading.html
- rurban 2y agoI would still call this a traditional template jit. The new things have nothing to do with copy&paste, but with using continuations and TCE (tail-call elimination), which I haven't seen in a simple template jit (or sometimes called method jit) before. Plus the register variants, to avoid moving them too much, but this is also very pedestrian, low tech. Low tech is good!
- mrugiero 2y agoDo you have any links to the traditional ones for those interested (i.e. me)? I only found out about the approach due to the author's articles a few months ago.
- PoignardAzur 2y agoI wonder if the comparisons with Cranelift would still show the same build-time/run-time gap four years later. From what I understand, Cranelift's current instruction selector is very close to copy-and-patch conceptually (it maps patterns of bytecode instructions to sequences of machine instructions), and the pass Cranelift spends the most time in, register allocation, still has to happen in copy-and-patch. So if copy-and-patch still has a meaningful advantage over Cranelift, I'm very curious to know where it comes from.
- naasking 2y agoAren't you just better off using GNU Lightning? It's basically a set of binary stencils defined by C macros, except because they're macros, your interpreter/compiler will only embed the stencils you actually use.