The Rust programming language compiles fast software slowly.<\/p>\n
In this series we explore Rust’s compile times within the context of TiKV, the key-value store behind the TiDB<\/a> database.<\/p>\n In the previous post in the series<\/a> we covered Rust’s early development history, and how it led to a series of decisions that resulted in a high-performance language that compiles slowly. Over the next few we’ll describe in more detail some of the designs in Rust that make compile time slow.<\/p>\n This time, we’re talking about monomorphization.<\/p>\n After the previous<\/a> episode of this series, people made a lot of great comments on HackerNews, Reddit, and Lobste.rs.<\/p>\n Some common comments:<\/p>\n Some subjects I hadn’t considered:<\/p>\n It’s tempting to talk about “compile-time” broadly, without any further clarification, but there are many types of “compile-time”, some that matter more or less to different people. The four main compile-time scenarios in Rust are:<\/p>\n The “development profile” entails compiler settings designed for fast compile times, slow run times, and maximum debuggability. The “release profile” entails compiler settings designed for fast run times, slow compile times, and, usually, minimum debuggability. In Rust, these are invoked with A full rebuild is building the entire project from scratch, and a partial rebuild happens after modifying code in a previously built project. Partial rebuilds can notably benefit from incremental compilation<\/a>.<\/p>\n In addition to those there are also<\/p>\n These are mostly similar to development mode and release mode respectively, though the interactions in cargo between development \/ test and release \/ bench can be subtle and surprising. There may be other profiles (TiKV has more), but those are the obvious ones for Rust, as built-in to cargo. Beyond that there are other scenarios, like typechecking only ( Compile time is also affected by human perception \u2014 it’s possible for compile time to feel bad when it’s actually decent, and to feel decent when it’s actually not so great. This is one of the premises behind the Rust Language Server<\/a> (RLS) and rust-analyzer<\/a> \u2014 if developers are getting constant, real-time feedback in their IDE then it doesn’t matter as much how long a full compile takes.<\/p>\n So it’s important to keep in mind through this series that there is a spectrum of tunable possibilities from “fast compile \/ slow run” to “fast run \/ slow compile”, there are different scenarios that affect compile time in different ways, and in which compile time affects perception in different ways.<\/p>\n It happens that for TiKV we’ve identified that the scenario we care most about with respect to compile time is “release profile \/ partial rebuilds”. More about that in future installments.<\/p>\n The rest of this post details some of the major designs in Rust that cause slow compile time. I describe them as “tradeoffs”, as there are good reasons Rust is the way it is, and language design is full of awkward tradeoffs.<\/p>\n Rust’s approach to generics is the most obvious language feature to blame on bad compile times, and understanding how Rust translates generic functions to machine code is important to understanding the Rust compile-time\/run-time tradeoff.<\/p>\n Generics generally are a complex topic, and Rust generics come in a number of forms. Rust has generic functions and generic types, and they can be expressed in multiple ways. Here I’m mostly going to talk about how Rust calls generic functions, but there are further compile-time considerations for generic type translations. I ignore other forms of generics (like As a simple example for this section, consider the following The way a compiler translates these calls to When a generic function is called with a particular set of type parameters it is said to be instantiated<\/em> with those types.<\/p>\n In general, for programming languages, there are two ways to translate a generic function:<\/p>\n The first results in static<\/em> method dispatch, the second in dynamic<\/em> (or “virtual”) method dispatch. The first is sometimes called “monomorphization”, particularly in the context of C++ and Rust, a confusingly complex word for a simple idea.<\/p>\n The previous example uses Rust’s type parameters ( Static (playground link<\/a>):<\/p>\n Dynamic (playground link<\/a>):<\/p>\n Notice that the only difference between these two cases is that the first In Rust Note that in these examples we have to use Below is an extremely simplified and sanitized version of the assembly And the dynamic case:<\/p>\n The important thing to note here is the duplication of functions or lack These two strategies represent a notoriously difficult tradeoff: the first creates lots of machine instruction duplication, forcing the compiler to spend time generating those instructions, and putting pressure on the instruction cache, but \u2014 crucially \u2014 dispatching all the trait method calls statically instead of through a function pointer. The second saves lots of machine instructions and takes less work for the compiler to translate to machine code, but every trait method call is an indirect call through a function pointer, which is generally slower because the CPU can’t know what instruction it is going jump to until the pointer is loaded.<\/p>\n It is often thought that the static dispatch strategy results in faster machine code, though I have not seen any research into the matter (we’ll do an experiment on this subject in a future edition of this series). Intuitively, it makes sense \u2014 if the CPU knows the address of all the functions it is calling it should be able to call them faster than if it has to first load the address of the function, then load the instruction code into the instruction cache. There are though factors that make this intuition suspect:<\/p>\n C++ and Rust both strongly encourage monomorphization, both generate some of the fastest machine code of any programming language, and both have problems with code bloat. This seems to be evidence that the monomorphization strategy is indeed the faster of the two. There is though a curious counter-example: C. C has no generics at all, and C programs are often both the slimmest and<\/em> fastest in their class. Reproducing the monomorphization strategy in C requires using ugly C macro preprocessor techniques, and modern object-orientation patterns in C are often vtable-based.<\/p>\n Takeaway: it is a broadly thought by compiler engineers that monomorphiation results in somewhat faster generic code while taking somewhat longer to compile.<\/em><\/p>\n Note that the monomorphization-compile-time problem is compounded in Rust because Rust translates generic functions in every crate (generally, “compilation unit”) that instantiates them. That means that if, given our <\/span>Rust Compile-time Adventures with TiKV: Episode 2<\/span><\/h2>\n
<\/span>Comments on the last episode<\/span><\/h2>\n
\n
\nC++.<\/li>\n
\nexperience most in their build-test cycle.<\/li>\n<\/ul>\n\n
\n(quadratic). Rust depends on data flow analysis. I don’t know how this
\nimpacts Rust compile times, but it’s good to be aware of.<\/li>\n
\nand that LLD may be faster than the system linker eventually.<\/li>\n<\/ul>\n<\/span>A brief aside about compile-time scenarios<\/span><\/h2>\n
\n
cargo build<\/code> and cargo build --release<\/code> respectively, and are indicative of the compile-time\/run-time tradeoff.<\/p>\n\n
cargo check<\/code>), building just a single project (cargo build -p<\/code>), single-core vs. multi-core, local vs. distributed, local vs. CI.<\/p>\n<\/span>Monomorphized generics<\/span><\/h2>\n
impl Trait<\/code>), as either they have similar compile-time impact, or I just don’t know enough about them.<\/p>\nToString<\/code> trait and the generic function print<\/code>:<\/p>\nuse std::string::ToString;\n\nfn print<T: ToString>(v: T) {\n println!(\"{}\", v.to_string());\n}\n<\/code><\/pre>\nprint<\/code> will print to the console anything that can be converted to a String<\/code> type. We say that “print<\/code> is generic over type T<\/code>, where T<\/code> implements Stringify<\/code>“. Thus I can call print<\/code> with different types:<\/p>\nfn main() {\n print(\"hello, world\");\n print(101);\n}\n<\/code><\/pre>\nprint<\/code> to machine code has a huge impact on both the compile-time and run-time characteristics of the language.<\/p>\n\n
An example in Rust<\/h3>\n
<T: ToString><\/code>) to define a
\nstatically-dispatched print<\/code> function. In this section we present two more Rust
\nexamples, the first with static dispatch, using references to impl<\/code> trait
\ninstances, and the second with dynamic dispatch, with references to dyn<\/code> trait
\ninstances.<\/p>\nuse std::string::ToString;\n\n#[inline(never)]\nfn print(v: &impl ToString) {\n println!(\"{}\", v.to_string());\n}\n\nfn main() {\n print(&\"hello, world\");\n print(&101);\n}\n\n<\/code><\/pre>\nuse std::string::ToString;\n\n#[inline(never)]\nfn print(v: &dyn ToString) {\n println!(\"{}\", v.to_string());\n}\n\nfn main() {\n print(&\"hello, world\");\n print(&101);\n}\n<\/code><\/pre>\n
\nprint<\/code>‘s argument is type &impl ToString<\/code>, and the second’s is &dyn ToString<\/code>. The first is using static dispatch, and the second dynamic.<\/p>\n&impl ToString<\/code> is essentially shorthand for a type parameter argument
\nthat is only used once, like in the earlier example fn print<T: ToString>(v: T)<\/code>.<\/p>\ninline(never)<\/code> to defeat the
\noptimizer. Without this it would turn these simple examples into the exact same
\nmachine code. I’ll explore this phenomenon further in a future episode of this
\nseries.<\/p>\n
\nfor these two examples. If you want to see the real thing, the playground
\nlinks above can generate them by clicking the buttons labeled ... -> ASM<\/code>.<\/p>\nprint::hffa7359fe88f0de2:\n ...\n callq *::core::fmt::write::h01edf6dd68a42c9c(%rip)\n ...\n\nprint::ha0649f845bb59b0c:\n ...\n callq *::core::fmt::write::h01edf6dd68a42c9c(%rip)\n ...\n\nmain::h6b41e7a408fe6876:\n ...\n callq print::hffa7359fe88f0de2\n ...\n callq print::ha0649f845bb59b0c\n<\/code><\/pre>\nprint::h796a2cdf500a8987:\n ...\n callq *::core::fmt::write::h01edf6dd68a42c9c(%rip)\n ...\n\nmain::h6b41e7a408fe6876:\n ...\n callq print::h796a2cdf500a8987\n ...\n callq print::h796a2cdf500a8987\n<\/code><\/pre>\n
\nthereof, depending on the strategy. In the static case there are two print<\/code>
\nfunctions, distinguished by a hash value in their names, and main<\/code> calls both
\nof them. In the dynamic case, there is a single print<\/code> function that main<\/code>
\ncalls twice. The details of how these two strategies actually handle their
\narguments at the machine level are too intricate to go into here.<\/p>\nMore about the tradeoff<\/h3>\n
\n
\nif a function pointer has been called recently it will likely be predicted
\ncorrectly the next time and called quickly;<\/li>\n
\nphenomenon commonly referred to as “code bloat”, which could put great
\npressure on the CPU’s instruction cache;<\/li>\n
\ninto the code can sometimes turn virtual calls into static calls.<\/li>\n<\/ul>\nprint<\/code> example, crate a<\/code> calls print(\"hello, world\")<\/code>, and crate b<\/code> also calls print(\"hello, world, or whatever\")<\/code>, then both crate a<\/code> and b<\/code> will contain the monomorphized print_str<\/code> function \u2014 the compiler does all the type-checking and translation work twice. This is partially mitigated today at lower optimization levels by shared generics<\/a>, though there are still duplicated generics in sibling dependencies<\/a>,
\nand at higher optimization levels.<\/p>\n