# Copy-and-Patch Binary Code Generation

**Authors:** Haoran Xu, Fredrik Kjolstad  
**arXiv:** [2011.13127](https://arxiv.org/abs/2011.13127)  
**Date:** 2020-11-26  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2011.13127v1/

## Key points

- Authors Haoran Xu and Fredrik Kjolstad discuss the trend of runtime compilation for runtime-constructed code in applications like libraries, DSLs, and database management systems.
- Traditional compilation methods are costly, leading to a need for more efficient alternatives.
- The novel code generation technique involves converting an Abstract Syntax Tree (AST) into binary code using a library of binary AST node implementations known as stencils.
- The copy-and-patch technique efficiently generates optimized binary code by piecing together code snippets from the stencil library.
- This method results in a highly efficient code generator with minimal overhead that can produce executable code faster than constructing the AST itself.
- Compared to LLVM, the copy-and-patch technique significantly speeds up the compilation process and outperforms various optimization levels, including -O0 optimizations.
- The resulting binary code executes approximately ten times faster than interpretation and even surpasses LLVM -O0 optimizations.

## Summary

In their paper "Copy-and-Patch Binary Code Generation," authors Haoran Xu and Fredrik Kjolstad discuss the increasing trend of runtime compilation for runtime-constructed code in various applications such as libraries, DSLs, and database management systems. This approach is driven by the high cost associated with traditional compilation methods. For systems that are sensitive to compile times, like relational database query compilers, compiling only hot code while interpreting the rest using a slower interpreter has been a common practice. However, Xu and Kjolstad introduce a novel code generation technique that offers a more efficient alternative. Their method involves converting an Abstract Syntax Tree (AST) into binary code by piecing together code snippets from a vast library of binary AST node implementations known as stencils. These stencils contain placeholders where values need to be inserted during the code generation process. By creating and utilizing such a stencil library, they present the copy-and-patch technique which efficiently generates optimized binary code. The result is a highly efficient code generator with minimal overhead that can produce executable code from an AST in less time than it takes to construct the AST itself. Compared to LLVM, this technique significantly speeds up the compilation process - being two orders of magnitude quicker than -O0 optimization level and three orders of magnitude faster than higher optimization levels. The resulting binary code executes approximately ten times faster than interpretation and even outperforms LLVM -O0 optimizations. Overall, the copy-and-patch method proves to be a game-changer in compile-time sensitive applications by effectively replacing interpreters and lower-level LLVM optimizations. This advancement enhances the efficiency of code generation processes in scenarios where rapid compilation is crucial for performance optimization.