9 ms·

How to speed up the Rust compiler

205 points by mfrw 3y ago

scns 3y ago
> This is a fun one. @Dragon-Hatcher created a very unusual Rust program: a chess engine that computes things at compile time only using Rust’s Turing-complete trait system. (They also have a TypeScript version of the same program.) This causes vast numbers of trait obligations to be generated for the compiler’s trait solver. In this PR I made some small changes to a de-duplication step that runs on collections of these obligations, which reduced both the compile time and peak memory usage of this crate by almost 7x! It also gave icount wins of up to 4% across a number of secondary benchmarks. Type System Acrobatics have their use.
- deleted 3y ago
  [deleted]
- deleted 3y ago
  [deleted]
ilSignorCarlo 3y ago
August is almost over. Is there a similar guide for September?
- SkiFire13 3y ago
  Yeah, just give the author a time machine so that they can post the same blog at the end of September. Jokes aside, this is not a guide on how to tweak your compiler settings or stuff like that, but rather it's about changes in the compiler source code that just make it faster for everyone. You just need to wait 6-12 weeks for them to come to stable though.
nindalf 3y ago
What I find most impressive is improving performance while other developers continue to land new features in the same code base.
- pornel 3y ago
  I’m impressed that this is the original code base dating back to the first lines of self-compiling Rust. They’ve managed to rearchitect and refactor it multiple times instead of rewriting it.
junon 3y ago
I guess I'm in the thought camp (a diminishingly small camp, if HN is any measure) that compile times don't matter. If you want short compile times, use interpreted languages. I appreciate the checks, validation, and optimization a compiler gives, and Rust's cuts down on total development time because of the extensive checks it performs. I remember a time where C++ projects took hours to build that today only take a few minutes. Perhaps that's an assist when 'dealing' with compilation times. I also don't think tests should be blazing fast. I'd rather correct tests than fast tests, just like I'd rather a thorough compilation over a fast one. Anecdotally, even with a project that has an upwards of 50 dependencies, many of them *-sys crates, I've never thought that compilation times were that bad. Speaking of interpreted languages, Javascript projects have historically taken exponentially longer to compile (looking at you, Meteor) and are rarely incremental. That's not to say "don't optimize things" of course but there are seemingly many people very upset or critical of Rust's compile times that I've never fully understood.
- Ygg2 3y ago
  I hear ya. But people are vocal about those. And thus Rust optimized those. Others (a game dev acquaintance) complains about debug performance being abysmal. At the end of the day, what people are vocal and more importantly willing to sink their time/money into will decide what happens.
- izacus 3y ago
  What's the biggest, oldest project you've ever worked on?
  - junon 3y ago
    A tie between the Linux kernel and LLVM (specifically Clang). Also making game engines gets pretty hefty quite quickly. That's just open source work though. I've worked on larger systems at some Big Tech that were unwieldy, too.
    - izacus 3y ago
      And at no point were you bothered by the timewaste C/C++ compiling (and especially, unavoidable linking!) brings to your work process, CI process and general ability to quickly debug and iterate on a hard problem?
stephc_int13 3y ago
The interesting point about this work is that this compiler is already close to its asymptotic speed. It unlikely will get much faster in the future.
- dralley 3y ago
  Nothing in this blog post says this, or even implies it. Just because expecting a 10x improvement is unrealistic doesn't mean that it's impossible for the Rust compiler to get "much" faster for a more reasonable definition of "much" (say, 2x). He does say that there likely won't be some step change, but rather the result of lots of small improvements over a long period of time.
  - stephc_int13 3y ago
    For any software, the optimization process tend to follow a curve, with diminishing returns over time, thus, the asymptote. What I am assuming is that the author is competent and is already doing a good job.
vlovich123 3y ago
> Anyone waiting for 10x improvements is likely to be disappointed. I don’t see that happening, except for the occasional unusual program (such as the chess engine case mentioned above). > The compiler is a large, mature project. It’s well over 10 years old, and hundreds of thousands of lines. Projects like that tend to not get quantum leaps in performance. Many small improvements is more typical. And > And it’s hard to radically change the data structures used in a mature compiler. As the author describes, the compiler is likely fairly well optimized for its existing way of doing things. 10x improvements would come from architectural changes and it sounds like the compiler is so big now that this is difficult. The other piece that makes it difficult is that LLVM is a separate also large project. An example of an architectural change I think hasn’t been investigated enough is in the space of PGO. While compilers use PGO to choose better heuristics, they don’t use that to control optimization levels applied to various code. Most programs have performance critical compute paths, but the rest of the program is no where near that. I feel like dropping expensive optimization passes for “cold” code would provide significant savings and Rust already lets you annotate cold/hot functions. Would be nice if it combined it with call flow analysis to build something like audio ABR but for optimization. Anyway, such things are difficult research projects to attempt on existing large codebases. I believe the author that further meaningful performance wins are unlikely without deeper architectural changes. This is very similar to comments that Lemire makes in [1] and is well understood to be the same (often misunderstood) critique as Knuth made many decades ago about premature optimization. Architecture trumps code tuning. [1] https://lemire.me/blog/2023/04/27/hotspot-performance-engineering-fails/ https://lemire.me/blog/2023/04/27/hotspot-performance-engine...
- glandium 3y ago
  > they don’t use that to control optimization levels applied to various code. GCC does. I think LLVM does to some extent too.
  - vlovich123 3y ago
    Where can I read up on this? AFAIK PGO is used in lieu of various heuristics within a pass, but is not used to remove optimization passes on “dead code”.
deleted 3y ago
[deleted]
Olreich 3y ago
> Compilers involve giant tree structures, with lots of allocations, pointer chasing, and data-dependent multi-way branches. Tree structures and data-dependent multi-way branches do seem inevitable to me, but pointer chasing and allocations don't seem inevitable at all. There are lots of ways to avoid allocations or make allocations practically free. Similarly there are lots of ways to make pointer chasing less prevalent, especially getting down to single-indirection. rustc may not be able to fix their allocation or pointer chasing problems, but this is not endemic to the problem of compiling.
- di4na 3y ago
  No but it is endemic to how we think about compilers up to now, and especially when the rust compiler arch was massively developed, more than 10 years ago. I recommend a watch of this for a recent take on trying to change how we think of these. It is an open research field https://m.youtube.com/watch?v=ZI198eFghJk https://m.youtube.com/watch?v=ZI198eFghJk
thraway3837 3y ago
The author is a member of the Rust team. https://nnethercote.github.io/about-me.html https://nnethercote.github.io/about-me.html Their blog posts are also posted multiple times on Hacker News by different identities. https://news.ycombinator.com/from?site=nnethercote.github.io https://news.ycombinator.com/from?site=nnethercote.github.io Seems odd that this wouldn’t go into an official Rust blog when you’re a member of the team and instead published on your personal domain and blog.
- kzrdude 3y ago
  Why is that odd? It's too specialized (and too many updates) to have his updates on the rust blog.
- nnethercote 3y ago
  I'm a member of Futurewei's Rust team, and I'm in the Compiler Contributors group. I started these posts back in 2016 when I wasn't a member of either. It's been a long-running series, and there's never been much reason for them to go on the official Rust blog, because they get enough attention on my personal blog. In the past I have posted links to Hacker News but usually they don't make the front page and get few if any comments, so I stopped bothering, but others sometimes do. I always post to /r/rust where the level of discussion tends to be higher-quality than HN, because there is a higher level of Rust knowledge.
meisel 3y ago
Why would they use SipHash at all? That’s a significantly slower hash algo than, say, wyhash, and any additional DOS protection SipHash might have (assuming it does) seems irrelevant for this use case
- loeg 3y ago
  Right? Jump straight to one of the modern, fast, non-cryptographic hashes.
jmmv 3y ago
How much is slow compilation caused by the compiler, and how much is it caused by the crates ecosystem and the many, many, many dependencies a project gains? I'm genuinely curious because a couple of projects I have written are not that large per se, but I don't like their compilation times too much. What I have observed is that I have ended with 100-200 (indirect) dependencies, and compilation slows down the closer it gets to the "leaf" of the process. In other words: by the time compilation reaches my own code, my code seems to take much longer to compile relative to the intermediate (larger) crates. And it's not link time (I've switched to mold).
- iknowstuff 3y ago
  Most of those are trivially paralllelized so it's not a problem. It gets slower towards the end because e.g. your crate needs all of its dependencies in place before it can be compiled.
- darksaints 3y ago
  This brings up a potentially huge optimization waiting to happen. When you have a Rust dependency, you compile the whole crate before you can even start compiling your code. But because of the depth of the ecosystem, there is a lot of code packaged into crates that may not need to be compiled...the crate might only used for a single function. There are probably dozens of ways to do this, but a quick parse and analysis of the target code could eliminate a large amount of dependency compilation.
  - epage 3y ago
    I do know there is vague / high-level interest in this kind of approach though I expect this would require a lot of work from the compiler, especially when it comes to figuring out what traits need to be compiled. Already, rust splits crate compilation into two passes where dependents are only blocked on the first pass and linking on the second. Maybe an intermediate is to do the first pass everywhere and then use that to decide what can be dropped from the second pass.
    - 3y ago
fulafel 3y ago
Would be interesting to hear more behind this: > Compilers involve giant tree structures, with lots of allocations, pointer chasing, and data-dependent multi-way branches. All the things that modern microarchitectures handle poorly. There is research into different designs that avoid these problems, but they involve data structures that can be highly non-ergonomic. A lot of graph algorithms are being expressed in matrix form. Like the current ML stuff.

205 points by mfrw 3y ago

scns 3y ago

> This is a fun one. @Dragon-Hatcher created a very unusual Rust program: a chess engine that computes things at compile time only using Rust’s Turing-complete trait system. (They also have a TypeScript version of the same program.) This causes vast numbers of trait obligations to be generated for the compiler’s trait solver. In this PR I made some small changes to a de-duplication step that runs on collections of these obligations, which reduced both the compile time and peak memory usage of this crate by almost 7x! It also gave icount wins of up to 4% across a number of secondary benchmarks. Type System Acrobatics have their use.

deleted 3y ago
[deleted]
deleted 3y ago
[deleted]

ilSignorCarlo 3y ago

August is almost over. Is there a similar guide for September?

SkiFire13 3y ago
Yeah, just give the author a time machine so that they can post the same blog at the end of September. Jokes aside, this is not a guide on how to tweak your compiler settings or stuff like that, but rather it's about changes in the compiler source code that just make it faster for everyone. You just need to wait 6-12 weeks for them to come to stable though.

nindalf 3y ago

What I find most impressive is improving performance while other developers continue to land new features in the same code base.

pornel 3y ago
I’m impressed that this is the original code base dating back to the first lines of self-compiling Rust. They’ve managed to rearchitect and refactor it multiple times instead of rewriting it.

junon 3y ago

I guess I'm in the thought camp (a diminishingly small camp, if HN is any measure) that compile times don't matter. If you want short compile times, use interpreted languages. I appreciate the checks, validation, and optimization a compiler gives, and Rust's cuts down on total development time because of the extensive checks it performs. I remember a time where C++ projects took hours to build that today only take a few minutes. Perhaps that's an assist when 'dealing' with compilation times. I also don't think tests should be blazing fast. I'd rather correct tests than fast tests, just like I'd rather a thorough compilation over a fast one. Anecdotally, even with a project that has an upwards of 50 dependencies, many of them *-sys crates, I've never thought that compilation times were that bad. Speaking of interpreted languages, Javascript projects have historically taken exponentially longer to compile (looking at you, Meteor) and are rarely incremental. That's not to say "don't optimize things" of course but there are seemingly many people very upset or critical of Rust's compile times that I've never fully understood.

Ygg2 3y ago
I hear ya. But people are vocal about those. And thus Rust optimized those. Others (a game dev acquaintance) complains about debug performance being abysmal. At the end of the day, what people are vocal and more importantly willing to sink their time/money into will decide what happens.
izacus 3y ago
What's the biggest, oldest project you've ever worked on?
- junon 3y ago
  A tie between the Linux kernel and LLVM (specifically Clang). Also making game engines gets pretty hefty quite quickly. That's just open source work though. I've worked on larger systems at some Big Tech that were unwieldy, too.
  - izacus 3y ago
    And at no point were you bothered by the timewaste C/C++ compiling (and especially, unavoidable linking!) brings to your work process, CI process and general ability to quickly debug and iterate on a hard problem?

stephc_int13 3y ago

The interesting point about this work is that this compiler is already close to its asymptotic speed. It unlikely will get much faster in the future.

dralley 3y ago
Nothing in this blog post says this, or even implies it. Just because expecting a 10x improvement is unrealistic doesn't mean that it's impossible for the Rust compiler to get "much" faster for a more reasonable definition of "much" (say, 2x). He does say that there likely won't be some step change, but rather the result of lots of small improvements over a long period of time.
- stephc_int13 3y ago
  For any software, the optimization process tend to follow a curve, with diminishing returns over time, thus, the asymptote. What I am assuming is that the author is competent and is already doing a good job.

vlovich123 3y ago

> Anyone waiting for 10x improvements is likely to be disappointed. I don’t see that happening, except for the occasional unusual program (such as the chess engine case mentioned above). > The compiler is a large, mature project. It’s well over 10 years old, and hundreds of thousands of lines. Projects like that tend to not get quantum leaps in performance. Many small improvements is more typical. And > And it’s hard to radically change the data structures used in a mature compiler. As the author describes, the compiler is likely fairly well optimized for its existing way of doing things. 10x improvements would come from architectural changes and it sounds like the compiler is so big now that this is difficult. The other piece that makes it difficult is that LLVM is a separate also large project. An example of an architectural change I think hasn’t been investigated enough is in the space of PGO. While compilers use PGO to choose better heuristics, they don’t use that to control optimization levels applied to various code. Most programs have performance critical compute paths, but the rest of the program is no where near that. I feel like dropping expensive optimization passes for “cold” code would provide significant savings and Rust already lets you annotate cold/hot functions. Would be nice if it combined it with call flow analysis to build something like audio ABR but for optimization. Anyway, such things are difficult research projects to attempt on existing large codebases. I believe the author that further meaningful performance wins are unlikely without deeper architectural changes. This is very similar to comments that Lemire makes in [1] and is well understood to be the same (often misunderstood) critique as Knuth made many decades ago about premature optimization. Architecture trumps code tuning. [1] https://lemire.me/blog/2023/04/27/hotspot-performance-engineering-fails/ https://lemire.me/blog/2023/04/27/hotspot-performance-engine...

glandium 3y ago
> they don’t use that to control optimization levels applied to various code. GCC does. I think LLVM does to some extent too.
- vlovich123 3y ago
  Where can I read up on this? AFAIK PGO is used in lieu of various heuristics within a pass, but is not used to remove optimization passes on “dead code”.

deleted 3y ago

[deleted]

Olreich 3y ago

> Compilers involve giant tree structures, with lots of allocations, pointer chasing, and data-dependent multi-way branches. Tree structures and data-dependent multi-way branches do seem inevitable to me, but pointer chasing and allocations don't seem inevitable at all. There are lots of ways to avoid allocations or make allocations practically free. Similarly there are lots of ways to make pointer chasing less prevalent, especially getting down to single-indirection. rustc may not be able to fix their allocation or pointer chasing problems, but this is not endemic to the problem of compiling.

di4na 3y ago
No but it is endemic to how we think about compilers up to now, and especially when the rust compiler arch was massively developed, more than 10 years ago. I recommend a watch of this for a recent take on trying to change how we think of these. It is an open research field https://m.youtube.com/watch?v=ZI198eFghJk https://m.youtube.com/watch?v=ZI198eFghJk

thraway3837 3y ago

The author is a member of the Rust team. https://nnethercote.github.io/about-me.html https://nnethercote.github.io/about-me.html Their blog posts are also posted multiple times on Hacker News by different identities. https://news.ycombinator.com/from?site=nnethercote.github.io https://news.ycombinator.com/from?site=nnethercote.github.io Seems odd that this wouldn’t go into an official Rust blog when you’re a member of the team and instead published on your personal domain and blog.

kzrdude 3y ago
Why is that odd? It's too specialized (and too many updates) to have his updates on the rust blog.
nnethercote 3y ago
I'm a member of Futurewei's Rust team, and I'm in the Compiler Contributors group. I started these posts back in 2016 when I wasn't a member of either. It's been a long-running series, and there's never been much reason for them to go on the official Rust blog, because they get enough attention on my personal blog. In the past I have posted links to Hacker News but usually they don't make the front page and get few if any comments, so I stopped bothering, but others sometimes do. I always post to /r/rust where the level of discussion tends to be higher-quality than HN, because there is a higher level of Rust knowledge.

meisel 3y ago

Why would they use SipHash at all? That’s a significantly slower hash algo than, say, wyhash, and any additional DOS protection SipHash might have (assuming it does) seems irrelevant for this use case

loeg 3y ago
Right? Jump straight to one of the modern, fast, non-cryptographic hashes.

jmmv 3y ago

How much is slow compilation caused by the compiler, and how much is it caused by the crates ecosystem and the many, many, many dependencies a project gains? I'm genuinely curious because a couple of projects I have written are not that large per se, but I don't like their compilation times too much. What I have observed is that I have ended with 100-200 (indirect) dependencies, and compilation slows down the closer it gets to the "leaf" of the process. In other words: by the time compilation reaches my own code, my code seems to take much longer to compile relative to the intermediate (larger) crates. And it's not link time (I've switched to mold).

iknowstuff 3y ago
Most of those are trivially paralllelized so it's not a problem. It gets slower towards the end because e.g. your crate needs all of its dependencies in place before it can be compiled.
darksaints 3y ago
This brings up a potentially huge optimization waiting to happen. When you have a Rust dependency, you compile the whole crate before you can even start compiling your code. But because of the depth of the ecosystem, there is a lot of code packaged into crates that may not need to be compiled...the crate might only used for a single function. There are probably dozens of ways to do this, but a quick parse and analysis of the target code could eliminate a large amount of dependency compilation.
- epage 3y ago
  I do know there is vague / high-level interest in this kind of approach though I expect this would require a lot of work from the compiler, especially when it comes to figuring out what traits need to be compiled. Already, rust splits crate compilation into two passes where dependents are only blocked on the first pass and linking on the second. Maybe an intermediate is to do the first pass everywhere and then use that to decide what can be dropped from the second pass.
  - 3y ago

fulafel 3y ago

Would be interesting to hear more behind this: > Compilers involve giant tree structures, with lots of allocations, pointer chasing, and data-dependent multi-way branches. All the things that modern microarchitectures handle poorly. There is research into different designs that avoid these problems, but they involve data structures that can be highly non-ergonomic. A lot of graph algorithms are being expressed in matrix form. Like the current ML stuff.