How I made Rustdoc 25% faster in one week

I’m a member of the Rustdoc team and recently made a series of PRs to Rustdoc that resulted in an average wall-time improvement of 25%, with up to 40% on some real-world crates like hyper and bitmaps, and up to 60% on microbenchmarks like helloworld. This blog post gets pretty into the details of how I went about discovering and implementing these performance improvements. I think it’ll be interesting if you want to learn more about what it’s like to work on Rust itself, including, in this case, Rustdoc. But if you want to just skip to the pretty chart at the end showing the final results, feel free!

The Bug

Last month, Rust release team member @theemathas posted on the Rustdoc Zulip about a strange regression in our latest beta. In case you’re not familiar with it, Rustdoc is the tool behind cargo doc. If you’ve ever opened the standard library docs or the docs for a crate on docs.rs, you’re looking at Rustdoc’s output. Anyway, before each stable version of Rust is published, the release team runs a tool called Crater that tests the new version across the public Rust ecosystem. Crater found Rustdoc to be newly erroring on a crate called indented-blocks, with code like this:

#![recursion_limit = "8"]

On a crate containing just this code, Rustdoc failed with a “reached the configured maximum number of stack frames” error while analyzing an internal-facing trait in core::fmt. In contrast, Rustc successfully finished compilation. This recursion_limit attribute allows users to control Rustc’s own recursion, since many language features can trigger excessive recursion at compile-time.¹ Users will sometimes have to raise the recursion limit above its default value if, for example, they use deeply nested macros or complex trait logic. The number of stack frames Rustc uses is not part of our stability guarantees, so this regression was not necessarily a problem.

However, it immediately raised alarm bells for me. Much of Rustdoc revolves around invoking Rustc APIs and then organizing and presenting the resulting information to users. So if Rustc was successfully compiling this code, it was concerning that Rustdoc failed on it. We do have cross-crate features like inlining documentation for items that your crate re-exports: std::vec::Vec is actually alloc::vec::Vec, but it looks seamless in the docs. We also show which impls across your workspace apply to types in your crate. But I couldn’t think of any reason why a random trait from core::fmt should have its documentation inlined into a nearly empty crate!

Sure enough, though, Rustdoc’s logs showed that it was trying to inline documentation for this trait:

DEBUG rustdoc::clean::inline record_extern_trait: DefId(2:13427 ~ core[195b]::fmt::num_buffer::NumBufferTrait)
DEBUG rustdoc::clean trait_ref=Binder { value: <Self as core::fmt::num_buffer::NumBufferTrait>, bound_vars: [] }

When I opened the file, collect_trait_impls.rs, that is responsible for inlining external impls, I found this code:

// in a pass called "build_extern_trait_impls"
for &cnum in tcx.crates(()) {
    for &impl_def_id in tcx.trait_impls_in_crate(cnum) {
        cx.with_param_env(impl_def_id, |cx| {
            inline::build_impl(cx, impl_def_id, None, &mut new_items_external);
        });
    }
}

For every dependency of the current crate, this code iterates through each trait impl defined there and constructs a representation of the impl suitable for display in docs. Thus, the algorithm’s complexity is linear in the number of trait impls throughout your entire dependency graph, with a large constant factor since build_impl is a rather involved function. That’s expensive!

Of course, Rustdoc doesn’t actually display all (or even most) of these impls in the docs, because it performs filtering later in the file, after impl collection. This is when I had a lightbulb moment: What if we performed the filtering first and only called build_impl for the impls we actually needed? I guessed no one had tried this before because the filtering code assumed it was receiving an already processed representation, plus there was some gnarly logic in the middle that followed chains of Deref impls. But I thought, what the hell, let’s just try it.

Filter First

I started by adapting an overly permissive version of the filtering logic to work on Rustc’s raw rustc_middle::ty data structures, then placed it as a guard before each build_impl call. I ran the main Rustdoc testsuite and… it passed. Wow. This was super encouraging.

I deleted the post-collection filter now that it was redundant. The testsuite still passed, even though my new filtering rules were too loose. In fact, I realized it should always be fine to keep unneeded impls. They only actually show up in doc pages where they are relevant, for example, if the page is for their self type or their trait. So, extra impls just slow Rustdoc down but don’t affect correctness.

It was time to face the scary code that followed chains of Deref impls. I was feeling bold. What if I just deleted it? This is actually something I often try to see how much behavior depends on a piece of code that I’m trying to improve. I waited for a wall of red tests that never came. Then I ran the extended testsuite that uses Puppeteer to test live GUI behavior. Just one test failed, and strangely it had nothing to do with Deref; rather, it was a test of #[doc(notable_trait)].

OK, a quick digression to give some background: Rustdoc has an unstable feature called “notable traits” where traits marked with a special attribute trigger little annotations wherever types that implement them are returned from a function. To see why this is useful, consider Iterator::map(). It returns a type called Map, which isn’t particularly meaningful to me as a user. However, Iterator is marked as a notable trait, so there is a little information icon ⓘ next to Map that tells me it is itself an Iterator.

It turned out that our trait impl inlining code never considered notable-trait status when making its decisions. So our GUI test for that tooltip passed by accident. It tested that a function returning Vec<u8> showed a notable trait tooltip for Write. Through the generic Vec<T> to &[T] deref impl, Vec<u8> derefs to &[u8], which in turn implements Write, thus causing the Write impl to be loaded into Rustdoc’s context and made available to the notable-trait popup!

After adding the necessary consideration of #[doc(notable_trait)], the GUI test passed, but a snapshot test needed to be updated because the notable trait popup was suddenly appearing in a lot of places where it was previously missing. It’s always nice when cleaning up code ends up inadvertently fixing a latent bug!

But, of course, the most exciting part of this PR was the perf results. The benchmarks showed an average wall-time improvement of 20%. Maximum resident-set size (a measure of peak memory usage) also decreased by 12%. The impact of this change was so large because the build_extern_trait_impls pass accounts for a significant proportion of Rustdoc runtime, as visualized by this flamegraph from before my change:

I think this performance win really shows the power of combining empirical profiling data with a willingness to question existing code. Excited from this success, I decided to push things further.

Primitive and Synthetic Impls

My next two PRs improved performance with smarter handling of primitive and synthetic impls. Rustdoc has special support for documenting primitive types like usize, str, and [T] that are not defined anywhere in library code but rather are built-in to the compiler. Although the types themselves are built-in, the standard library defines impls on them. Think of str::as_bytes, for example. To facilitate the display of these docs, the standard library uses special #[rustc_doc_primitive] attributes so that Rustdoc has a place to put them. I noticed that the logic in collect_trait_impls.rs to inline impls for primitive types ran in every crate, even if that crate did not declare any primitives (as nearly all crates do not). For complex technical reasons, this pass is expensive, so it added a meaningful amount to Rustdoc’s runtime. By making it only run on local primitives (and thus be skipped for most crates), I improved Rustdoc’s wall time by 12% and max RSS by 6%, on average.

The other PR was for synthetic impls. This is our name inside the Rustdoc codebase for the impls we synthesize on doc pages for auto traits and blanket impls. Let me explain what these terms mean. Send and Sync are examples of auto traits. Their implementations are determined on the fly by the compiler for types that meet their requirements, so the impls are not defined in your code. Rustdoc, however, constructs representations of these impls so that it can display them in docs as if they were normal impls.

Blanket impls are a little bit different but similar in spirit. They do have a definition in user code, but they are implemented for a generic type. For example, every type T is subject to the blanket impl<T> ToOwned for T, if T: Clone. So we copy these impls onto the pages of each type to which they apply.

Synthesizing all these auto and blanket impls is expensive since it requires iterating over every type defined in a crate and then checking each auto trait and each blanket impl against it. I noticed that Rustdoc was doing this analysis even for types that never appeared in the final documentation, for example, for private types. Adding a filter to analyze only documented types reduced wall time by 6% on average and up to 13% on some real-world crates like hyper.

Self Types

My final PR in this series was driven by examining flamegraphs for Rustdoc that were collected after my previous changes. I noticed that Rustc’s param_env query was accounting for a remarkable 50% of the time taken by the build_extern_trait_impls pass:

This query essentially just computes and normalizes the where clauses on an item (in our case, an impl), including those it inherits from its parent. While this operation isn’t cheap, it’s not particularly expensive either. The reason it took so much of the time is that it was being invoked on every single impl in the crate’s dependency graph---better than actually inlining every impl, like before, but still not great. To decide impl inlining, we need to examine the impl’s self type to see if that type is inlined. Computing Rustdoc’s version of this type requires the parameter environment since we may need to normalize it. Normalization just means simplifying a type down as much as possible given our knowledge about it. For example, if know that MyIter: Iterator<Item = MyStruct>, then we can normalize <MyIter as Iterator>::Item to MyStruct.

However, what I realized is that we can avoid computing a full Rustdoc version of the type in most cases. We only need to examine the head of the self type. By “head”, I mean the most essential part of the type that determines which documentation page it refers to---the Vec in Vec<i32>, or the String in &'a mut String. And we only need to call param_env if the self type’s head is something like <MyIter as Iterator>::Item that we have to normalize.² Changing Rustdoc according to these principles yielded an average 18% wall-time speedup across the benchmark suite, including real-world crates like clap_derive. I validated that the improvement was due to avoiding param_env invocations for non-inlined impls using another flamegraph from after this change:

Notice that param_env’s share of runtime is significantly smaller, leaving build_impl as the dominant contributor. Now, the pass’s runtime is dominated by performing work for impls that we actually want to inline, rather than for ones we end up skipping.

Final Results

After all these changes, where do they leave Rustdoc? I think the following graph of Rustdoc wall-time across our benchmark suite shows it best.³

Each of these four dips corresponds to one of my PRs. Rustdoc is now 25% faster on average! This improvement is present on nightly already and will land on stable in Rust 1.99.

The impact is noticeable on flamegraphs, too. Observe the share of runtime taken by build_extern_trait_impls for hyper, one of the most improved benchmarks, before…

…and after my changes…

Bye for Now

I hope you’ve enjoyed reading this peek into my recent work on Rustdoc. More than any technical detail, the learnings I most want you to take away are to trust your instincts and to question assumptions. Just because a piece of code (or anything, not just code!) has been a certain way for a long time doesn’t mean that it’s optimal or even correct. If your intuition tells you something, listen to it and dig in to see what you find. You might just stumble upon a major improvement waiting to be discovered.

P.S. Thanks to my Rust teammates for making this project a joy to be a part of.