In my last post I introduced the Compiler performance roadmap for 2022. Let’s see how things are progressing. Normally in these posts I mostly write about my own work, but there is enough interesting stuff going on that I will mention work done by other people as well.
Declarative macro expansion
One item on the roadmap is declarative macro expansion. It had (surprisingly) been found to dominate compile times of numerous crates, and is under-represented in the benchmark suite. We made progress on this within the compiler and elsewhere.
The part of the compiler that does declarative macro matching is quite old. Much of the code predated Rust 1.0, and it was the kind of code that people do their best to avoid touching. Time for some Type 2 fun.
I made a lot of PRs to improve this code. There were some good performance wins, combined with many basic refactorings to make the code nicer and easier to understand. Things like:
- improving formatting;
- moving code into separate functions;
- reordering code;
- renaming things;
- adding assertions to make invariants explicit;
- improving and simplifying types;
- improving consistency;
- removing redundant data;
- and generally simplifying things whenever possible.
In the rest of this section, performance improvements are for instructions
check full builds, which is rustc-perf’s name for “a
build with incremental compilation disabled”. This is a good baseline for
changes affecting the compiler front-end. The wins I mention are not just on
the usual rustc-perf benchmarks, but also a selection of crates that use
declarative macros heavily.
Here are the PRs.
- #94547 (5 commits, filed March 3): Basic refactorings.
- #94693 (2 commits, filed March 7): This PR inlines some hot parser functions called from the macro expansion code, for up to 4% wins.
- #94798 (6 commits, filed March 10): Basic refactorings.
- #95067 (6 commits, filed March 18): Basic refactorings.
- #95159 (7 commits, filed March 21): Basic refactorings, plus an improvement in an important data structure that gave up to 11% wins.
- #95259 (4 commits, filed March 24): More data representation tweaks, giving up to 7% wins.
- #95301 (1 commit, filed
March 25). A refactoring that simplified the
- #95425 (6 commits, filed March 29): Basic refactorings, plus a big overhaul of how metavariable matches are represented, giving up to 17% wins.
- #95509 (5 commits, filed March 31): More refactorings and simplifications, for some sub-1% wins.
- #95555 (2 commits, filed April 1): A new matcher representation that makes the code simpler, more concise, and gave up to 10% wins. Yay! This one felt really good.
- #95669 (3 commits, filed Apr 5): A change to compute the new matcher representation once per macro rule rather than once per macro rule invocation, giving up to 2% wins.
- #95715 (1 commit, filed
April 6): Shrank
Nonterminalfor some small memory usage wins.
- #95797 (1 commit, filed April 8): Reverted a representation change from #95159 that was no longer necessary after #95555.
- #95794 (3 commits, filed April 8): Basic refactorings.
- #95928 (5 commits, filed April 11): Avoided some cloning, giving up to 3% wins.
Phew! Many thanks to @petrochenkov for reviewing all these PRs.
Here are the improvements across the macro-heavy crates.
There are a few additional measurements I’m particularly happy with.
MatcherPostype is at the heart of macro matching. Before I started, it had two lifetime parameters, 10 fields and took up 192 bytes. It now has zero lifetime parameters, two fields and takes up 16 bytes.
- When doing a
check fullbuild of
async-std-1.10.0, the compiler used to do 23.9 million heap allocations. It now does 2.5 million, and most of them are unrelated to macro expansion. Three cheers for DHAT!
- The file
macro_parser.rsused to have 766 lines. It now has 718 lines.
Although the compiler improvements are nice, some declarative macros remain expensive, and rewriting or removing them altogether from third-party crates is worthwhile.
async-std was #1 on the list of macro-heavy crates.
#1005: In this PR I
extension_trait! macro within this crate by removing some
unused rules and moving push-down accumulator state to the end of rules.
#1006: I then learned that
extension_trait! macro could be removed altogether, which I did in this
These two changes had roughly equal performance effects, and combined they
check full build time of this crate by more than 50%. They are
present in the 1.11.0 release. Thanks to
@yoshuawuyts for his help on these changes.
time-macros was #2 on the list of macro-heavy crates.
#453: In this PR I sped up the
quote_internal! macro within this crate by moving its accumulator to the end,
which avoids lots of wasted matching when a rule fails. This halved the time
check full builds.
yansi was #3 on the list of macro-heavy crates.
#36: In this PR I removed the
docify! macro from
check full times by 60%.
This change is present in the 0.5.1 release, which is also the first new release in three years! Thanks to @SergioBenitez for his help on these changes.
quote is a widely used crate. Of the 26 crates from the
analysis most affected by
macro expansion, 18 of them were due to use of
quote::quote!. So this macro
is worth optimizing as much as possible.
#209: In this PR I reordered the
many rules in the
quote_token_spanned! macros so the most
commonly used ones were first, for up to 6% wins across those 18 crates.
#210: In this PR
@lqd reordered arguments within rules in the
quote_token_spanned! macros so that less work was done on
rules that failed to match, for up to 2% wins across those same crates.
quote! uses an advanced
and non-obvious technique that makes it act like a TT muncher but with better
worst-case performance and no need to modify the
recursion_limit. In this PR
I documented the code to explain how it works. Some people will run screaming,
but for those who like tricky macros this
will be of great interest.
#217: In this PR I added rules to
optimize the cases where
quote! is passed only one or two token trees, for
up to 12% wins across those same crates.
These changes are present in the 1.0.18 release of
quote. Thanks to
@dtolnay for his help on these changes.
Here are the improvements across the aforementioned crates that use
Note that these are in addition to the improvements from the earlier table.
ctor-0.1.21 will get an 8% reduction from compiler improvements, and an
additional 12% reduction from
The Little Book of Rust Macros is an excellent guide to Rust macros. I read it when I first started looking at declarative macro expansion and learned a lot.
#58: In this PR I added advice about all the performance pitfalls of declarative macros I learned while doing this work. In particular, the fact that TT munchers and push-down accumulation macros are inherently quadratic! This is something that I didn’t know until recently, and I suspect many other people also don’t know.
#1290: In this PR I added
a new benchmark called
tt-muncher to rustc-perf. This benchmark is
representative of many crates that use declarative macros heavily.
I have now reached the end of this work on macro expansion. I got a lot done in
six weeks, which is pleasing, and I know it looks impressive when written down
in a big list. But I want to emphasise that it mostly didn’t feel this like
that while I was doing it. I didn’t set out to rewrite 75% of
macro_parser.rs, even though that’s what happened in the end.
If you look closely at the PRs for the compiler, they were slow to start with, and the early ones were all basic refactorings. My first performance win in the macro expansion code wasn’t until March 18, nineteen days after I started looking at the macro expansion code. (And note that I work full-time on the compiler.) I spent plenty of time in the first three weeks just staring at the code, taking notes, and trying things, many of which didn’t work, or did work but were unsatisfactory for one reason or another. Progress didn’t speed up until the second half of the six weeks.
In fact, during those first three weeks there were times when I thought I wouldn’t get any macro expansion performance wins in the compiler. That’s why I switched to working on some of the third-party crates, just to get some wins there. After that I switched back to working on the compiler, mostly because my spidey senses were still tingling about both the readability and the performance of the code. In particular, DHAT profiles showed that the code was doing huge numbers of heap allocations, which is a pet peeve of mine.
Along the way I had to undo some optimizations I had added to this code a
couple of years ago. Those optimizations turned out to be useful for one kind
of expensive macro (with many rules but no metavariables) present in the
html5ever benchmark. But such macros aren’t common in practice, and these
optimizations were unhelpful for more typical expensive macros, which are
recursive, have fewer rules, and use metavariables. This shows the value of a
good benchmark suite.
I made some missteps, too. Most notably, I caused a P-critical
bug when I removed a code path
that I mistakenly thought was impossible, which briefly prevented
ring from compiling with Nightly. (Apologies
to everyone who was affected!) Interestingly, my mistake unintentionally
exposed a possible bug: the compiler currently ignores doc comments in a
matcher, which is arguably the wrong thing to
But enough real code depends on this behaviour that it can’t be changed without
One lesson: never underestimate the impact of many small improvements. Also, never underestimate the usefulness of refactorings for learning how code works, and for enabling bigger improvements. Any time I want to dive deep into a new piece of code, I start by doing refactorings. For this code I made over 50 commits, and around 90% of them were refactorings that didn’t improve performance. But I couldn’t have made the 10% that did improve performance without the other 90%. These changes don’t just help me. Other people will find this code easier to read and modify now.
Finally, note that for all this effort, I’ve only improved the constant factors for declarative macro expansion. Many recursive macros are still inherently quadratic. It would be nice to find a way to eliminate this by doing something smarter to avoid reparsing token streams that are repeatedly captured by macro metavariables. If anyone wants to work on this, I’m happy to provide pointers on where to start.
Alright, enough about macros. Time for something else.
An entire section of the roadmap is about better benchmarks in rustc-perf, and good progress has been made there.
#1181: Not all the benchmarks in the benchmark suite are equally important. In particular, many are synthetic stress tests that are useful for detecting regressions, but are not as important as popular, real-world crates. In this PR, new contributor @Kobzol split the benchmarks into “primary” and “secondary” categories, which required changes to the benchmark harness, the database, and the website for viewing results. This makes looking at performance results much nicer, which is great for those of us who do that a lot.
Once the primary/secondary split was done, we were able to undertake the large
task of updating all the real-world crates in the benchmark suite to the
latest versions. This is a good thing, because many of the versions were four
or five years old. (To give you one example, we upgraded the
syn crate from
v0.11.11 to v1.0.89!) This task was
shared by me, @Kobzol, @lqd,
and @rylev. And thanks to
@jdm for making a new
html5ever release to help
For those who care about data continuity, never fear: the handful of “stable” benchmarks used for the perf dashboard have been kept, though they are no longer run on every commit. This means our longest ongoing record of compiler performance will continue, albeit on benchmarks that are now quite dated.
Finally, @rylev, @Kobzol, and new contributor @miwig have made many improvements to the results website and automated reports that are posted to GitHub PRs after CI runs. These are not of general interest to Rust users, but are useful to those of us working on compiler performance.
#94704, #95724: In these PRs @Kobzol twice updated the the benchmarks used for profile-guided optimization of rustc releases, for wins across numerous benchmarks of up to 5% in the first PR and 2% in the second PR. Importantly, most of these improvements were on debug and release builds of the largest real-world benchmarks.
#95473: In this PR, @lqd started adding some machinery for tracking proc macro executions when doing self-profiling. This will hopefully be the start of some useful performance diagnosis tooling.
#2770: In this PR @lqd modified
the build configuration of the popular
hyper crate so that the Rust compiler
could pipeline its compilation. The following image, generated with
--timings, demonstrates the benefit. The top half shows how the
used to build serially. The bottom half shows how it now parallelizes nicely,
shaving about 10 seconds off the build time for this example.
Finally, people love reading about failed optimization attempts, so here is one. The compiler currently uses LEB128 compression when writing integers to metadata. I looked into some alternative schemes for compressing integers, but was not able to do anything useful. These schemes are generally designed for sequences of integers that are all the same size, but Rust metadata interleaves integers of varying sizes, preventing their use.
For the period 2022-02-25 to
it’s hard to do my usual progress report. This is because every primary
helloworld was upgraded since last time and thus lacks a
comparison for this period.
Among the secondary benchmarks, the largest changes are improvements, but there
are more regressions than improvements. A lot of the larger regressions are for
doc builds due to the recently merged
#95515. These should be fixed
Because of all that, I won’t draw any firm conclusions. This is unsatisfying, but we’ll have much better data next time around with the new benchmarks. Plus the scope of the work over the past two months has been broader than usual, with many real improvements that fall outside the scope of what’s measured by rustc-perf. This is not a bad thing! rustc-perf is important, but it’s never going to measure everything, and it shouldn’t be the only focus.
Having finished with declarative macros for now, I’m planning to do a deep dive into the compile time performance of procedural macros. Let me know if you have any insights or data points relating to this.
More generally, if anyone is interested in helping out with Rust compiler
performance, check out this Zulip
t-compiler/performance stream, which identifies small tasks that are
suitable for new contributors. Questions are welcome.
Thanks for reading! That was a long one. Everyone who made it this far gets a gold star: ⭐