{"id":3213,"date":"2019-10-11T10:01:52","date_gmt":"2019-10-10T23:01:52","guid":{"rendered":"http:\/\/blog.mozilla.org\/nnethercote\/?p=3213"},"modified":"2019-10-11T10:01:52","modified_gmt":"2019-10-10T23:01:52","slug":"how-to-speed-up-the-rust-compiler-some-more-in-2019","status":"publish","type":"post","link":"https:\/\/blog.mozilla.org\/nnethercote\/2019\/10\/11\/how-to-speed-up-the-rust-compiler-some-more-in-2019\/","title":{"rendered":"How to speed up the Rust compiler some more in 2019"},"content":{"rendered":"

In July I wrote about my efforts to speed up the Rust compiler in 2019<\/a>. I also described how the Rust compiler has gotten faster in 2019<\/a>, with compile time reductions of 20-50% on most benchmarks. Now that Q3 is finished it’s a good time to see how things have changed since then.<\/p>\n

Speed improvements in Q3 2019<\/h3>\n

The following image shows changes in time taken to compile many of the standard benchmarks<\/a> used on the Rust performance tracker<\/a>. It compares a revision of the the compiler from 2019-07-23 with a revision of the compiler from 2019-10-09.<\/p>\n

\"Screenshot<\/a><\/p>\n

These are the wall-time<\/a> results. There are three different build kinds measured for each one: a debug build, an optimized build, and a check build (which detects errors but doesn\u2019t generate code). For each build kind there is a mix of incremental and non-incremental runs done. The numbers for the individual runs aren\u2019t shown here but you can see them if you view the results directly on the site<\/a> and click around. (Note that the site has had some reliability issues lately. Apologies if you have difficulty with that link.) The \u201cavg\u201d column shows the average change for those runs. The \u201cmin\u201d and \u201cmax\u201d columns show the minimum and maximum changes among those same runs.<\/p>\n

There are a few regressions, mostly notably for the ctfe-stress-2<\/code> benchmark, which is an artificial stress test of compile-time function evaluation and so isn’t too much of a concern. But there are many more improvements, including double-digit improvements for clap-rs<\/code>, inflate<\/code>, unicode_normalization<\/code>, keccak, wg-grammar<\/code>, serde<\/code>, deep-vector<\/code>, script-servo<\/code>, and style-servo<\/code>. There have been many interesting things going on.<\/p>\n

memcpy<\/h3>\n

For a long time, profilers like Cachegrind and Callgrind have shown that 2-6% of the instructions executed by the Rust compiler occur in calls to memcpy<\/code>. This seems high<\/a>! Curious about this, I modified DHAT to track calls to memcpy<\/code>, much in the way it normally tracks calls to malloc<\/code>.<\/p>\n

The results showed that most of the memcpy<\/code> calls come from a relatively small number of code locations. Also, all the memcpy<\/code> calls involved values that exceed 128 bytes. It turns out that LLVM will use inline code for copies of values that are 128 bytes or smaller<\/a>. (Inline code will generally be faster, but memcpy<\/code> calls will be more compact above a certain copy size.)<\/p>\n

I was able to eliminate some of these memcpy<\/code> calls in the following PRs.<\/p>\n

#64302<\/a>: This PR shrank the ObligationCauseCode<\/code> type from 56 bytes to 32 bytes by boxing two of its variants, speeding up many benchmarks by up to 2.6%. The benefit mostly came because the PredicateObligation<\/code> type (which contains an ObligationCauseCode<\/code>) shrank from 136 bytes to 112 bytes, which dropped it below the 128 byte memcpy<\/code> threshold. I also tried reducing the size of ObligationCauseCode<\/code> to 24 bytes by boxing two additional variants, but this had worse performance because more allocations were required.<\/p>\n

#64374<\/a>: The compiler’s parser has this type:<\/p>\n

pub type PResult<'a, T> = Result<T, DiagnosticBuilder<'a><\/pre>\n
It’s used as the return type for a lot of parsing functions. The T<\/code> value is always small, but DiagnosticBuilder<\/code> was 176 bytes, so PResult<\/code> had a minimum size of\u00a0 184 bytes. And DiagnosticBuilder<\/code> is only needed when there is a parsing error, so this was egregiously inefficient. This PR boxed DiagnosticBuilder<\/code> so that PResult<\/code> has a minimum size of 16 bytes, speeding up a number of benchmarks by up to 2.6%.<\/p>\n
#64394<\/a>: This PR reduced the size of the SubregionOrigin<\/code> type from 120 bytes to 32 bytes by boxing its largest variant, which sped up many benchmarks slightly (by less than 1%). If you are wondering why this type caused memcpy<\/code> calls despite being less than 128 bytes, it’s because it is used in a BTreeMap<\/code> and the tree nodes exceeded 128 bytes.<\/p>\n
ObligationForest<\/h3>\n
One of the biggest causes of memcpy<\/code> calls is within a data structure called ObligationForest<\/code>, which represents a bunch of constraints (relating to type checking and trait resolution, I think) that take the form of a collection of N-ary trees. ObligationForest<\/code> uses a single vector to store the tree nodes, and links between nodes are represented as numeric indices into that vector.<\/p>\n
Nodes are regularly removed from this vector by a function called ObligationForest::compress<\/code>. This operation is challenging to implement efficiently because the vector can contain thousands of nodes and nodes are removed only a few at a time, and order must be preserved, so there is a lot of node shuffling that occurs. (The numeric indices of all remaining nodes must be updated appropriately afterwards, which further constrains things.) The shuffling requires lots of\u00a0 swap<\/code> calls, and each one of those does three memcpy<\/code> calls (let tmp = a; a = b; b = tmp<\/code>, more or less). And each node is 176 bytes! While trying to get rid of these memcpy<\/code> calls, I got very deep into ObligationForest<\/code> and made the following PRs that aren’t related to the copying.<\/p>\n
#64420<\/a>: This PR inlined a hot function, speeding up a few benchmarks by up to 2.8%. The function in question is indirectly recursive, and LLVM will normally refuse to inline such functions. But I was able to work around this by using a trick: creating two variants of the function, one marked with #[inline(always)]<\/code> (for the hot call sites) and one marked with #[inline(never)]<\/code> (for the cold call sites).<\/p>\n
#64500<\/a>: This PR did a bunch of code clean-ups, some of which helped performance to the tune of up to 1.7%. The improvements came from factoring out some repeated expressions, and using iterators and retain<\/code> instead of while loops in some places.<\/p>\n
#64545<\/a>: This PR did various things, improving performance by up to 13.8%. The performance wins came from: combining a split parent\/descendants representation to avoid frequent chaining of iterators (chained iterators are inherently slower than non-chained iterators); adding a variant of the shallow_resolve<\/code> function specialized for the calling pattern at a hot call site; and using explicit iteration instead of Iterator::all<\/code>. (More about that last one below.)<\/p>\n
#64627<\/a>: This PR also did various things, improving performance by up to 18.4%. The biggest improvements came from: changing some code that dealt with a vector to special-case the 0-element and 1-element cases, which dominated; and inlining an extremely hot function (using a variant of the abovementioned #[inline(always)]<\/code> +\u00a0#[inline(never)]<\/code> trick).<\/p>\n
These PRs account for most of the improvements to the following benchmarks: inflate<\/code>,\u00a0keccak<\/code>, cranelift-codegen<\/code>, and serde<\/code>. Parts of the ObligationForest<\/code> code was so hot for these benchmarks (especially inflate<\/code> and keccak<\/code>) that it was worth micro-optimizing them to the nth degree. When I find hot code like this, there are always two approaches: (a) try to speed it up, or (b) try to avoid calling it. In this case I did (a), but I do wonder if the users of ObligationForest<\/code> could be more efficient in how they use it.<\/p>\n
The above PRs are a nice success story, but I should also mention that I tried a ton of other micro-optimizations that didn’t work.<\/p>\n