How I made Rustdoc 33% faster in one week

The Rustdoc team, led by the reporter, made several changes to Rustdoc that resulted in a 33% speedup, with up to 40% improvements on certain crates like hyper and bitmaps, and up to 60% on microbenchmarks such as helloworld. The improvements were discovered and implemented within a week.

Last month, Rust release team member @theemathas reported a regression in Rustdoc after a new stable Rust version was released. The regression caused Rustdoc to fail in analyzing an internal-facing trait in core::fmt, leading to a "reached the configured maximum number of stack frames" error. Although Rustc successfully compiled the code, this regression was alarming since Rustdoc's performance was crucial for its functionality.

The reporter started investigating by examining the Rustdoc logs, which revealed that the tool was attempting to inline documentation for the trait mentioned above. This led the reporter to look at the collect_trait_impls.rs file, which is responsible for inlining external implementation details.

The reporter noticed that the algorithm's complexity was linear in the number of trait implementations throughout the entire dependency graph, leading to a large constant factor due to the build_impl function being rather involved. This made the entire process expensive. The reporter's idea was to perform filtering first, calling build_impl only for the necessary implementations.

To test this idea, the reporter adapted filtering logic to work on Rustc's raw rustc_middle::ty data structures and placed it as a guard before each build_impl call. After running the main Rustdoc testsuite, the changes passed. The reporter then removed redundant post-collection filters, and the testsuite still passed.

The reporter then tackled the problem of following chains of Deref impls, which they decided to delete. This change was initially met with skepticism, as they wanted to see if much of the behavior depended on this code. However, the tests ran without issues, and the extended testsuite using Puppeteer to test live GUI behavior also passed, except for one test unrelated to Deref.