LWN.net needs you!
Without subscribers, LWN would simply not exist. Please consider
signing up for a subscription and helping
to keep LWN publishing.
By Daroc Alden
December 3, 2024
The traditional structure of a compiler forms a pipeline — parsing,
type-checking, optimization, and code-generation, usually in that order. But
modern programming languages have requirements that are ill-suited to such a
design. Increasingly, compilers are moving toward other designs in
order to support incremental compilation and low-latency responses for uses
like integration into IDEs. Rust has, for the last eight years, been pursuing a
particularly unusual design; in that time
compile times have
substantially improved, but there’s still more work to be done.
In a traditional compiler, normally each step of the pipeline needs to complete before
the next is started. For example, optimization must complete before the
compiler can begin emitting machine code. There are ways to improve this —
working on translation units in parallel, caching some kinds of analysis, etc. — but, at a
certain point, the architectures of the compilers themselves make it difficult to
make the code support incremental compilation.
Language design can influence how much of a problem this is in practice. For
example, while the GCC developers did
look into making the compiler incremental, the fact that C defines each file
as a stand-alone translation unit makes it easier to add incrementalism at the
level of the build system. Many modern languages don’t observe the same
separation between files, however. In Rust, an entire crate is a single
translation unit; cargo, Rust’s build system, handles only recompiling changed
crates, but adding incrementalism within a crate requires special support from
the compiler.
So, in response to wishes for faster compile times,
Rust has been exploring an alternative to the
traditional structure of a compiler by switching to a query-based model:
instead of having a fixed pipeline, the compiler has a set of queries
for different properties of the program.
Each query can either retrieve the answer from a persistent compilation
database, or, if the answer has not yet
been cached, calculate it from scratch by making other queries and combining
their results. For example, the compiler uses the
type_of() query to infer the types of local bindings. The query takes
the ID of a local definition, and then calls other queries to determine whether
it is an impl Trait type, what the abstract syntax tree of the
definition is, what the types of the variables it refers to are, and so on.
Suppose that the programmer changes the type of a constant in their crate. When
they run the compiler, it will evaluate a top-level query to produce an output
binary. That query will in turn query for the final versions of each function in
the crate (after type-checking and optimization). Most of those will not have
changed, so the answers are provided from the on-disk compilation database. The
queries for functions that depend on the changed constant, however, will get
re-run — and will, themselves, call other queries until the whole process ends
up at the query corresponding to the parsed representation of the
single changed definition. Only the minimum
amount of analysis and compilation needed to accommodate that change is performed.
This approach is reminiscent of a build system — and that’s deliberate. Build
systems, while not always perfect, usually do a good job of tracking the
dependencies between components and correctly caching partial results. A
compiler that has the architecture of a build system can take advantage of the
research that has been done on build systems to do the same.
Rust’s approach
The Rust project began the process of rewriting its compiler to
support
incremental compilation
in 2016. While that redesign is not yet fully complete, large portions of
the compiler now use a query-based approach. LWN
recently covered Sparrow Li’s
talk that discussed what remains to be done.
The Rust compiler organizes queries using a structure called
TyCtxt. When the compiler starts up, the various modules all
register functions called “providers” that implement each query. Then,
depending on how the compiler was invoked, it parses the code (because the
parser has not yet been integrated into the query system) and runs a set of top-level queries to
compile an artifact, format the code, produce warnings, or whatever else was
requested.
Providers need to be
pure functions, since
the compiler may not always need to run them, so the programmer
can’t depend on any side effects. This also has the effect of forcing those
parts of the compiler that have been converted to the query system to avoid
global state. The results of queries could in theory be any type, but in
practice the compiler requires that they be values that can be cheaply copied, in order
to simplify the ownership of cached values. Not every query is saved
to disk, but most queries return types that can be serialized and hashed, so
that they can be.
There are some important differences in structure between Rust’s queries and
static build systems like
Make, not just in the form that their results take.
In Rust’s implementation, the relationship
between queries is implicit. Queries are always invoked via a TyCtxt;
that structure can track the dependencies between queries by seeing which
queries are invoked while another is executing. Also, unlike some build systems,
the compiler tracks the order in which dependencies are invoked. This
is important because the results of one query can change which other queries get
executed — therefore, the order impacts the calculation of which queries need to
be rerun when doing incremental compilation. For example, this query depends on
different things depending on the result of subquery1():
fn example_query<'tcx>(tcx: TyCtxt<'tcx>) -> SomeType {
if tcx.subquery1() {
tcx.subquery2()
} else {
tcx.subquery3()
}
}
During the initial run of the compiler, when there are no saved results, the
program collects the graph of which queries refer to each other. When the
compiler is rerun, it checks that graph to see which queries need to be rerun
because of changed inputs. As an additional optimization, if the inputs to a
query have changed, but the result of the query has not, the compiler can detect
that and cut off the process of recalculating queries early.
The process of figuring out whether an intermediate result has changed
is complicated by the fact that any information
about the incremental build needs to be shared between runs of the compiler by
saving it to disk. The compiler uses a lot of internal ID numbers to organize
different components that differ from run to run, and serializing
every intermediate result in the compiler would be expensive. So actually
saving the results of cached queries is more complex.
In order to work around the problem of changing internal IDs, structures that
are saved to disk are given “stable” forms of each ID. For example, function and
type definitions are identified by path (e.g.
std::collections::HashMap) instead of by internal ID. In order to avoid
the overhead of deserializing intermediate results to detect changes,
the compiler calculates and stores hashes for each item. Hashes are much more
compact, and don’t require complex deserialization, so this is a substantial
performance improvement. The downside is that computing so many hashes actually
causes significant overhead. The compiler’s
internal documentation calls it
“the main reason why incremental compilation can be slower than
”
non-incremental compilation.
These performance improvements introduce their own complications, of course. For
example, if a result is never loaded from disk, the compiler won’t necessarily
be able to include it in the incremental-compilation database for the
next run of the program. So, after generating results, the compiler
does another pass through the query graph to fetch and update the results that
it skipped earlier, in order to make sure that the size of the cache doesn’t
unnecessarily shrink. This increases the compiler’s overall runtime — but what
users usually care about is the time it takes to produce warnings and errors,
not how long it takes the compiler to do cleanup before exiting.
There are various other optimizations and tweaks applied
to the largest queries to make the overall system more performant. The Rust
Compiler Development Guide’s
section on the query system has more details.
Overall, the query-based approach introduces a lot of complexity compared to a
simple pipeline-based approach. But any large, performance-sensitive codebase
accumulates complexity over time — and having a single, well-understood system
for incremental compilation may well win out over gradually introducing ad-hoc
improvements to a pipeline-based system. In any case, Rust’s incremental
compilation has been stable enough to become the default for development builds.
Release builds still avoid incremental compilation by default, however, out of
an abundance of caution. Whether
the query-based compiler design will ultimately be adopted by other languages
remains to be seen.
