[HN Gopher] Copy-and-Patch: Fast compilation for high-level lang...
___________________________________________________________________
Copy-and-Patch: Fast compilation for high-level languages and
bytecode (2020)
Author : tosh
Score : 130 points
Date : 2024-06-02 12:07 UTC (10 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| lumpa wrote:
| Is this the technique they are using in Python's new JIT?
| Qem wrote:
| Yes. 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
| djoldman wrote:
| (2020)
| thrtythreeforty wrote:
| I love this approach. Has any independent toolkit evolved to help
| do this? Or have all projects rolled their own?
| Iwan-Zotow wrote:
| Cpython in beta
| thrtythreeforty wrote:
| Sure 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 wrote:
| There's Deegen, which is being used to build a LuaJIT
| successor. 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 wrote:
| I 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 wrote:
| It 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.
| fiddlerwoaroof wrote:
| I 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 wrote:
| This 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
| pompino wrote:
| If you post a link, we all can read it :)
| alserio wrote:
| Link 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
| foota wrote:
| There's some related discussion here:
| https://news.ycombinator.com/item?id=40406194
| dang wrote:
| Thanks! Also related:
|
| _A copy-and-patch JIT compiler for CPython_ -
| 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 -
| Sept 2021 (7 comments)
| philzook wrote:
| We 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://github.com/purseclab/Patcherex2/pull/31 A pull request
| to the PatcherEx2 library
| boywitharupee wrote:
| > 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 wrote:
| The 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.
| vlovich123 wrote:
| It'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 wrote:
| Rust'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 wrote:
| I 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 wrote:
| If 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".
| bjourne wrote:
| Afaik, this technique is called threading
| (https://en.wikipedia.org/wiki/Threaded_code) and has been used
| in most bootstrap compilers for decades.
| mrugiero wrote:
| I 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
___________________________________________________________________
(page generated 2024-06-02 23:00 UTC)