How I made Rustdoc 33% faster in one week

我是如何在一周内将 Rustdoc 的速度提升 33% 的

I’m a member of the Rustdoc team and recently made a series of PRs to Rustdoc that resulted in an average wall-time reduction of 25% (which is a 33% speedup), 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!

我是 Rustdoc 团队的一员，最近我向 Rustdoc 提交了一系列 PR，使平均运行时间减少了 25%（即速度提升了 33%）。在 hyper 和 bitmaps 等一些实际的 crate 上，性能提升高达 40%，而在 helloworld 等微基准测试中，提升甚至达到了 60%。这篇博文详细介绍了我是如何发现并实施这些性能改进的。如果你想了解参与 Rust 本身（在本例中是 Rustdoc）的开发是什么样的体验，这篇文章应该会让你感兴趣。当然，如果你只想直接跳到文末查看最终结果的精美图表，也完全没问题！

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.

上个月，Rust 发布团队成员 @theemathas 在 Rustdoc 的 Zulip 上发布了一条关于我们最新测试版中出现奇怪回归的消息。如果你还不熟悉，Rustdoc 就是 cargo doc 背后的工具。如果你曾经打开过标准库文档或 docs.rs 上的 crate 文档，你看到的其实就是 Rustdoc 的输出。总之，在每个稳定版 Rust 发布之前，发布团队都会运行一个名为 Crater 的工具，在整个公共 Rust 生态系统中测试新版本。Crater 发现 Rustdoc 在一个名为 indented-blocks 的 crate 上出现了新的错误，其代码如下：#![recursion_limit = "8"]。对于仅包含此代码的 crate，Rustdoc 在分析 core::fmt 中的一个内部 trait 时，因“达到配置的最大堆栈帧数”而报错。相比之下，Rustc 却能成功完成编译。

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.

recursion_limit 属性允许用户控制 Rustc 自身的递归，因为许多语言特性在编译时可能会触发过度的递归。如果用户使用了深度嵌套的宏或复杂的 trait 逻辑，有时必须将递归限制提高到默认值以上。Rustc 使用的堆栈帧数量并不在我们的稳定性保证范围内，因此这次回归并不一定是个问题。然而，这立刻引起了我的警觉。Rustdoc 的大部分工作围绕着调用 Rustc API，然后整理并将结果信息呈现给用户。因此，如果 Rustc 能够成功编译这段代码，那么 Rustdoc 在此失败就令人担忧了。

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: [] }

我们确实有一些跨 crate 的功能，例如为你的 crate 重新导出的项内联文档：std::vec::Vec 实际上是 alloc::vec::Vec，但在文档中看起来是无缝衔接的。我们还会显示工作区中哪些 impl 应用于你 crate 中的类型。但我实在想不出为什么一个来自 core::fmt 的随机 trait 的文档会被内联到一个几乎为空的 crate 中！然而，Rustdoc 的日志确实显示它正在尝试为该 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!

当我打开负责内联外部 impl 的文件 collect_trait_impls.rs 时，我发现了这段代码：

// 在名为 "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);
        });
    }
}

对于当前 crate 的每一个依赖项，这段代码都会遍历其中定义的每个 trait impl，并构建一个适合在文档中显示的 impl 表示。因此，该算法的复杂度与整个依赖图中 trait impl 的数量呈线性关系，且由于 build_impl 是一个相当复杂的函数，其常数因子很大。这非常耗费资源！

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.

当然，Rustdoc 实际上并不会在文档中显示所有（甚至大部分）这些 impl，因为它是在 impl 收集之后，在文件的后续部分执行过滤的。这时我灵光一现：如果我们先进行过滤，只为我们真正需要的 impl 调用 build_impl 会怎样？我猜之前没人尝试过这样做，因为过滤代码假设它接收的是已经处理过的表示，而且中间还有一些复杂的逻辑用于追踪 Deref impl 链。但我心想，管他呢，试一试吧。

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.

我首先调整了一个过于宽松的过滤逻辑版本，使其能够处理 Rustc 原始的 rustc_middle::ty 数据结构，然后将其作为守卫放在每个 build_impl 调用之前。我运行了主要的 Rustdoc 测试套件，结果……通过了。哇，这太令人振奋了。既然现在的后置过滤已经多余，我就把它删除了。即使我的新过滤规则过于宽松，测试套件依然通过了。事实上，我意识到保留不需要的 impl 总是没问题的。它们只会在相关的文档页面中显示，例如，如果页面是针对其自身类型或其 trait 的。因此，多余的 impl 只会拖慢 Rustdoc 的速度，而不会影响正确性。

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.

是时候面对那些追踪 Deref impl 链的复杂代码了。我胆子大了起来。如果我直接删掉它会怎样？这其实是我经常尝试的一种方法，用来观察我试图改进的代码片段到底承载了多少功能。我等待着测试失败的红潮，但它从未出现。接着，我运行了使用 Puppeteer 测试实时 GUI 行为的扩展测试套件。只有一个测试失败了，奇怪的是它与 Deref 无关；相反，它是关于 #[doc(notable_trait)] 的测试。好吧，简单插播一下背景：Rustdoc 有一个名为“notable traits”（显著 trait）的不稳定特性，当 trait 被标记上特殊属性时，任何返回实现该 trait 的类型的函数都会触发小小的注释。为了说明这为什么有用，考虑 Iterator::map()。它返回一个名为 Map 的类型，作为用户，这对我来说意义不大。然而，由于 Iterator 被标记为显著 trait，Map 旁边会有一个小小的信息图标 ⓘ，告诉我它本身就是一个 Iterator。结果发现，我们的 trait impl 内联代码在做决策时从未考虑过显著 trait 的状态。