The Rust programming language compiles fast software slowly.<\/p>\n\n\n\n
In this series we explore Rust’s compile times within the context of TiKV, the key-value store behind the \ud2f0DB<\/a> database.<\/p>\n\n\n\n Lately we’re exploring how Rust’s designs discourage fast compilation. In Generics and Compile-Time in Rust<\/a> we discussed the difficult compile-time tradeoffs required to implement generics.<\/p>\n\n\n\n This time we’re going to talk about compilation units.<\/p>\n\n\n\n A compilation unit<\/em> is the basic unit of work that a language’s compiler operates on. In C and C++ the compilation unit is a source file. In Java it is a source file. In Rust the compilation unit is a crate<\/em>, which is composed of many files.<\/p>\n\n\n\n The size of compilation units incur a number of tradeoffs. Larger compilation units take longer to analyze, translate, and optimize than smaller compilation units. And in general, when a change is made to a single compilation unit, the whole compilation unit must be recompiled.<\/p>\n\n\n\n More, smaller crates improve the perception<\/em> of compile time, if not the total compile time, because a single change may force less of the project to be recompiled. This benefits the “partial recompilation” use cases. A project with more crates though may do more work on a full recompile due to a variety of factors, which I will summarize at the end of this post.<\/p>\n\n\n\n Rust crates don’t have to be large, but there are a variety of factors that encourage them to be. The first is simply the relative complexity of adding new crates to a Rust project vs. adding a new module to a crate. New Rust projects tend to turn into monoliths unless given special attention to abstraction boundaries.<\/p>\n\n\n\n Within a crate, there are no fundamental restrictions on module interdependencies, though there are language features that allow some amount of information-hiding within a crate. The big advantage and risk of having modules coexist in the same crate is that they can be mutually dependent<\/em>, two modules both depending on names exported from the other. Here’s an example similar to many encountered in TiKV, in which Modules with mutual dependencies are useful for reducing cognitive complexity simply because they break up code into smaller units. As an abstraction boundary though they are deceptive: they are not truly independent, and cannot be trivially reduced further into separate crates.<\/p>\n\n\n\n And that is because dependencies between crates must form a directed acyclic graph (a DAG)<\/em>; they do not support mutual dependencies.<\/p>\n\n\n\n Rust crates being daggish are mostly due to fundamental reasons of type checking and architectural complexity. If crates allowed for mutual dependencies then they would no longer be self-contained compilation units.<\/p>\n\n\n\n In preparation for this blog I asked a few people if they could recall the reasons why Rust crates must form a DAG, and Graydon gave a typically thorough and authoritative answer:<\/p>\n\n\n\n graydon: Prohibits mutual recursion between definitions across crates, allowing both an obvious deterministic bottom-up build schedule without needing to do some fixpoint iteration or separate declarations from definitions graydon: (once you know you’ve seen all the cycles in a recursive type you can check it for finiteness and then stop expanding it at any boxed variants — even if they cross crates — and put a lazy \/ placeholder definition in those boxed edges; but you need to know those variants don’t cycle back!)<\/p>\n<\/blockquote>\n\n\n\n graydon: (I do not know if rustc does anything like this anymore)<\/p>\n<\/blockquote>\n\n\n\n graydon: cyclicality concerns are even worse with higher order modules, which I was spending quite a lot of time studying when working on the early design. most systems I’ve seen require you to paint some kind of a boundary around a group of mutually-recursive definitions to be able to resolve them, so the crate seemed like a natural unit for that.<\/p>\n<\/blockquote>\n\n\n\n graydon: then there is also the issue of versioning, which I think was pretty heavy in my mind (especially after the experience with monotone and git): a lot of versioning questions don’t really make sense without acyclic-by-construction references. Like if A 1.0 depends on B 1.0 which depends on A 2.0 you, again, need to do something weird and fixpointy and potentially quite arbitrary and hard to explain to anyone in order to resolve those dependencies.<\/p>\n<\/blockquote>\n\n\n\n graydon: also recall we wanted to be able to do hot code loading early on, which means that much like version-resolving, compiling or linking, your really in a much simpler place if there’s a natural topological order to which things you have to load or unload. you can decide whether a crate is still live just by reference-counting, no need to go figure out cyclical dependencies and break them in some random order, etc.<\/p>\n<\/blockquote>\n\n\n\n graydon: I’m not sure which if any of these was the dominant concern. If I had to guess I’d say avoiding problems with separate compilation of recursive definitions and managing code versioning. recall the language in the manual \/ the rationale for crates: “units of compilation and versioning”. Those were the consideration for their existence as separate from modules. Modules get to be recursive. Crates, no. Because of things to do with “compilation and versioning”.<\/p>\n<\/blockquote>\n\n\n\n graydon: I cannot make a simple argument about this because I’m still not smart enough about module systems \u2014 the full thing is laid out in dreyer’s thesis<\/a> and discussed in shorter slide-deck form here<\/a> \u2014 but suffice to say that recursive modules make it possible to see the “same” opaque type through two paths that should probably be considered equal but aren’t easily determined to be so, I think in part due to the mix of opacity that modules provide and the fact that you have to partly look through that opacity to resolve recursion. so anyway I decided this was probably getting into “research” and I should just avoid the problem space, go with acyclic modules.<\/p>\n<\/blockquote>\n\n\n\n Although driven by fundamental constraints, the hard daggishness of crates is useful for a number of reasons: it enforces careful abstractions, defines units of parallel<\/em> compilation, defines basically sensible codegen units, and dramatically reduces language and compiler complexity (even as the compiler likely moves toward whole-program, demand-driven, compilation in the future).<\/p>\n\n\n\n Note the emphasis on parallelism<\/em>. The crate DAG is the simplest source of compile-time parallelism Rust has access to. Cargo today will use the DAG to automatically divide work into parallel compilation jobs.<\/p>\n\n\n\n So it’s quite desirable for Rust code to be broken into crates that form a wide<\/em> DAG.<\/p>\n\n\n\n In my experience though projects tend to start in a single crate, without great attention to their internal dependency graph, and once compilation time becomes an issue, they have already created a spaghetti dependency graph that is difficult to refactor into smaller crates.<\/p>\n\n\n\n It happened to Servo, and it has also been my experience on TiKV, where I have made multiple aborted attempts to extract various modules from the main program, in long sequences of commits that untangle internal dependencies. I suspect that avoiding problematic monoliths is something that Rust devs learn with experience, but it is a repeating phenomenon in large Rust projects.<\/p>\n\n\n\n <\/p>\n\n\n\n<\/span>Rust Compile-time Adventures with TiKV: Episode 3<\/span><\/h2>\n\n\n\n
<\/span>Compilation units<\/span><\/h2>\n\n\n\n
<\/span>Dependency graphs and unstirring spaghetti<\/span><\/h2>\n\n\n\n
engine<\/code> imports (“uses”) network::Message<\/code> \uadf8\ub9ac\uace0 network<\/code> imports storage::Engine<\/code>.<\/p>\n\n\n\nmod storage {\n use network::Message;\n\n pub struct Engine;\n\n impl Engine {\n pub fn handle_message(&self, msg: Message) -> Result<()> { ... }\n }\n}\n\nmod network {\n use storage::Engine;\n\n pub enum Message { ... }\n\n struct Server {\n engine: Engine,\n }\n\n impl Server {\n fn handle_message(&self, msg: Message) -> Result<()> {\n ...\n\n self.engine.handle_message(msg)?;\n\n ...\n }\n }\n}\n<\/code><\/pre>\n\n\n\n\n
and enables phases that need to traverse a complete definition, like typechecking, to happen crate-at-a-time (enabling some<\/em> degree of incrementality \/ parallelism).<\/p>\n<\/blockquote>\n\n\n\n\n
\n
\n
\n
\n
\n
\n