JIT Compiling Code in 5μs

Fast just-in-time (JIT) compilation was once considered an esoteric practice, requiring extensive assembly language knowledge. Today, advancements in artificial intelligence have made it easier to create JIT compilers that compile code in mere microseconds. This breakthrough allows new databases to achieve performance comparable to older alternatives.

Pgrust, a database project, successfully implemented a JIT compiler that compiles code in around 5 microseconds, enabling the JIT compilation of every SQL query. In this article, we will guide you through building your own fast JIT compiler. To illustrate, we'll create a simple regular expression engine as our example use case. JIT compilation is a technique that generates machine code at runtime, resulting in significant performance improvements, often ranging from 2 to over 5 times faster.

It is particularly useful in scenarios where runtime information drastically changes the program's behavior, such as in programming language interpreters and data parsing.

Let's start by building a toy regular expression engine that supports only literal strings and repetition (the regex *). We'll represent the regular expression as already-parsed Rust structures, allowing us to support strings like "but no alternation or lookbehind". In code, this is straightforward, with three types of nodes: literal string, repetition, and concatenation, which combines two nodes.

An interpreter for this regular expression engine is relatively simple, consisting of just under 20 lines of code. However, its performance is far from optimal. In fact, when benchmarked against hand-written code specifically designed for the regex, the interpreter was found to be 10-20 times slower.

To improve performance, let's utilize JIT compilation. The process involves two main steps: generating assembly code for the desired operations and packaging it into a callable function within your program. To generate the assembly code, we'll employ a technique called copy-and-patch. This method involves using pre-written assembly templates, or "stencils," for different operations.

By modifying these stencils based on the specifics of each operation, we can dynamically construct a program at runtime with performance comparable to hand-written code.

The generated assembly code for our example regular expression (b(an)*) will be broken down into individual parts. The code follows the ARM64 architecture, which is used by macOS systems. The program's state is managed by three registers, and input is provided through the stack.

In the generated assembly, the prologue initializes the program by setting the stack's top and bottom values. Next, the code checks for the literal character 'b'. If a different character is encountered, the program jumps to a fallback code block. Otherwise, it advances the position in the string.

Moving on, we handle the repetition (an)*. To manage backtracking, we store both the address of the instruction after the loop and the string position on the stack. The body of the repetition checks for 'a' and 'n', and if found, resets the string position for another iteration. Once the loop concludes, the program checks if it has reached the end of the string. If so, it returns 1 to indicate success; otherwise, it returns 0 to signify a failed match.