Writing a Fast Compiler - Marc Kerbiquet

Writing a Fast Compiler

2024-02-04

I'm going to describe the various tricks I used to write fast compilers for my programming languages. By fast compilation, I mean compiling at least 500.000 lines of code per second (excluding blank lines and comments) on a single CPU core.

Does it Matter?

You may argue that compilation time is not important. After all, once released, who cares that a program took hours to build; as users, we only want it to work and to work fast. It's like complaining that the last Pixar movie took days for the final rendering.

However it can severely affect the development cycle and make developers angry. It's 2024 and I can see that the most common complaint for Rust is still its compilation time.

The speed also affects the design of the compiler: when my biggest program is less than 100K SLOC and I can compile 500K SLOC per second I don't really have to worry about separate compilation since a complete build takes less than 200ms. And this is good since separate compilation can be tricky with genericity.

Designing a Language for Fast Compilation

If you're writing a compiler for an existing language, e.g. C++, you have no control here, you'll have to deal with an LL(k) grammar, a preprocessor and a terrible module system. Conversely, if you're writing a compiler for your own programming language, careful design choices can help a lot.

I've always used a context free grammar that can be easily parsed with a simple recursive descent parser. If a syntax is easy to parse by the computer it will be also easy to parse by a human.

A simple syntax will also make the development of independent tools easier (static analyzer, formating tools, refactoring, syntax highlighting, ...).

General Rules

Minimizing Code and Memory Access

Less code to execute and less memory access usually means faster execution. While modern architectures don't make this principle strictly true, it is still a good rule to follow.

I avoid copying data as much as possible. Many languages use zero-terminated strings. I prefer to use a pair of (start_pointer, size) or (start_pointer, end_pointer) instead: it allows for instance to refer to any sub-string directly from the input buffer without having to do a copy.

Reducing Memory Usage

The less memory I use, the more it will fit in cache.

Ordering variables in structs carefully can significantly reduce the size of these structs, especially in 64 bits because of alignment constaints.

Combining multiple flags in an integer saves memory but it also allows to perform multiple tests at once just by using a mask. C bitfields are useful here.

Using bytes or bitfields for enums.

Optimizing the Common Path

A lot of work in the compiler is to check for errors but a program has usually no error or very few ones. Therefore the code must be optimized considering that errors are exceptionals.

If an error requires two conditions to be met, I evaluate the fastest one first so the second one will never be evaluated.

I don't compute something needed only for an error reporting until an actual error is detected.

Memory Management: Using Memory Regions

A memory region is a contiguous block of memory where parts can be allocated but not de-allocated (the entire region must be de-allocated). The allocation consists just in advancing a pointer, and eventually creating a new region when the region is full. It makes allocations extremely fast. The de-allocation is also extremely fast since all objects of a region are freed at once.

This kind of memory management fits very well with a compiler: a single region can be used for a compilation unit. In practice I use 3 regions:

one to store the AST,

one to store the program objects and

one for the code generation so I can get rid of the AST during code generation.

However when compiling functions, there are lot of temporary objects created, mainly dictionary of names for each lexical scope. To handle this I create pools of regions: instead of creating and destroying regions I pick one from a pool and put it back to the pool when finished.

Resizable arrays and open addressing hashtables are not suitable data structures for memory regions since they need a lot of de-allocations and re-allocations.

To store lists of elements, when possible I count the elements first and then I allocate a fixed size array, when it's not possible I just use a link-list.

To handle hash tables which are heavily used for names, I use separate chaining instead of open-addressing. It eliminates re-allocation of arrays but it requires to carefully choose the size of the hash: the global namespace will need a bigger hash table than the inner scope of a function.

Lexical Analyzer: Identifiers as Numbers

CPUs are not designed to work with strings, they are designed to work with fixed size integers.

Comparing two strings needs additional access to two memory regions.

Hashing a string is slow.

An important...