Skip to content
The methodOpen data
Back to the collection

Copy-and-Patch Compilation: A fast compilation algorithm for high-level languages and bytecode

Haoran Xu, Fredrik Kjolstad

2020 · arXiv

Programming languagesDatabasesAlgorithms
Read the paper
HN score
2.5
Mentions
10
Readers
10
Months
9
What’s in a score?

From the abstract

Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers. We present copy-and-patch, an extremely fast compilation technique that also produces good quality code. It is capable of lowering both high-level languages and low-level bytecode programs to binary code, by stitching together code from a large library of binary implementation variants. We call these binary implementations stencils because they have holes where missing values must be inserted during code generation. We show how to construct a stencil library and describe the copy-and-patch algorithm that generates optimized binary code. We demonstrate two use cases of copy-and-patch: a compiler for a high-level C-like language intended for metaprogramming and a compiler for WebAssembly. Our high-level language compiler has negligible compilation cost: it produces code from an AST in less time than it takes to construct the AST. 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. Our WebAssembly compiler generates code 4.9X-6.5X faster than Liftoff, the WebAssembly baseline compiler in Google Chrome. The generated code also outperforms Liftoff's by 39%-63% on the Coremark and PolyBenchC WebAssembly benchmarks.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

10 selected excerpts · 10 total mentions

vanderZwan
Strong recommendation · rule
I think it's really cool that Haoran Xu and Fredrik Kjolstad's copy-and-patch technique[0] is catching on, I remember discovering it through Xu's blog posts about his LuaJIT remake project[1][2], where he intends to apply these techniques to Lua (and I probably found those through a post here). I was just blown away by how they "recycled" all these battle-tested techniques and technologies, and used it to synthesize something novel. I'm not a compiler writer but it felt really clever to me. I highly recommend the blog posts if you're into learning how languages are implemented, by the way. They're incredible deep dives, but he uses the details-element to keep the…
Read the full comment
metaphorical descents into Mariana Trench optional so it doesn't get too overwhelming. I even had the privilege of congratulating him the 1000th star of the GH repo[3], where he reassured me and others that he's still working on it despite the long pause after the last blog post, and that this mainly has to do with behind-the-scenes rewrites that make no sense to publish in part. [0] https://arxiv.org/abs/2011.13127 [1] https://sillycross.github.io/2022/11/22/2022-11-22/ [2] https://sillycross.github.io/2023/05/12/2023-05-12/ [3] https://github.com/luajit-remake/luajit-remake/issues/11
Original comment Python 3.13 Gets a JIT
kragen
Recommendation · rule
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…
Read the full comment
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
Original comment Parent story unavailable in snapshot
drob518
Neutral mention · rule
I was just reading a paper about compiling SQL queries (actually about a fast compilation technique that allows for full compilation to machine code that is suitable for SQL and WASM): https://dl.acm.org/doi/pdf/10.1145/3485513 Sounds like many DBs do some level of compilation for complex queries. I suspect this is because SQL has primitives that actually compute things (e.g. aggregations, sorts, etc.). But find does basically none of that. Find is completely IO-bound.
Original comment Parent story unavailable in snapshot
darkamaul
Neutral mention · rule
I think the _copy-and-patch_ approach [0] is probably the best compromise here. You get many of the guarantees of compiled code (strong correctness, reduced mismatch between interpreter vs JIT semantics, etc.), while still being very close to native performance. In fact, Python is already moving in that direction: the new bytecode-based copy-and-patch JIT in Python 3.13 shows correct results even before heavy performance tuning. So to me this seems like a very promising road: I wonder how practical this is if the base language is not C/C++ but Rust (or any kind of memory safe language). [0] https://arxiv.org/abs/2011.13127
Original comment Writing Memory Safe JIT Compilers
UncleEntity
Neutral mention · rule
I've been messing with Claude pretty heavily the last week or so and found if I guide it in the right direction it (mostly) does the right thing. I've been having it reproduce the lua peg parser thingie (plus utf-8 support)[0] from the paper they wrote about it while also using the 'musttail' interpreter pattern [1] just because that sounded like a good idea. Once I got over the fact that Claude is really bad at debugging and Deepseek, while much better at it, isn't very reliable due to 'server busy' timeouts things have been going swimmingly. While I don't do very much debugging once in a while they do get stuck trying the same things over and over so I have to step in…
Read the full comment
and every so often it'll go crazy and come up with some over complicated solution where I have to ask "that's nice and all but wouldn't it have been easier to just update the index variable instead of rewriting the whole thing?" Claude also seems to like duplicating code instead of generating a helper function but I haven't had that argument with it yet. So far we have a VM which passes all the tests (which was a battle), a Destination-Driven Code Generation (with additions and subtractions) based compiler implementing all the peg specific optimizations from the paper (which I haven't even starting debugging yet) and the start of a Python C-API module to tie it all together. Admittedly, the python module is all my doing because it's easier to use pybindgen than fight with the robots. So, yeah, I'm just having fun getting the robots to write code I'm too lazy to write myself on a subject which has interested me for at least a decade. Once I get this working I plan on seeing how well they do with Copy-and-Patch Compilation[2] but don't really have high hopes on that. [0] https://www.inf.puc-rio.br/~roberto/lpeg/ [1] https://blog.reverberate.org/2021/04/21/musttail-efficient-i... [2] https://arxiv.org/abs/2011.13127
Original comment Co-designing a sparse music codec with ChatGPT o3
yunruse
Neutral mention · rule
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
Original comment Parent story unavailable in snapshot
fsfod
Neutral mention · rule
The author also worked on the Copy-and-Patch Compilation paper[1], I wonder if they are going to use the same idea for ones of tiers of the JIT idk if it would beat LuaJIT's JIT for code compilation speed but the machine code could be faster. [1] https://arxiv.org/abs/2011.13127
Original comment Building the fastest Lua interpreter automatically
cfallin
Neutral mention · rule
The perf blogpost actually uses SpiderMonkey-compiled-to-Wasm as a benchmark rather than a comparison (peer) of Wasmtime. However, there are some good comparisons done by a third party in this paper: https://arxiv.org/pdf/2011.13127.pdf See Figs. 20-22 on page 19. They found Wasmtime to be quite competitive to V8 and others. (disclosure: I work on Wasmtime + Cranelift)
Original comment Wasmtime 1.0

Keep following the thread.

More in Programming languages

More from the same topics.

2017arXiv

The Case for Learned Index Structures

Tim Kraska, Alex Beutel, Ed H. Chi +2

Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not.

Databases
19 mentions14 months
5HN score