16 ms·

How to speed up the Rust compiler some more

170 points by nnethercote 10y ago

wyldfire 10y ago
Can rust capitalize on LTO/PGO? Even if that's not quite ready for primetime, if we're spending 50% or more time in the LLVM backend, that certainly can be built with LTO/PGO. Seems like it might be worth the trouble/bootstrapping challenge if it yields another ~5%.
- corndoge 10y ago
  we should just make computers faster, intel is failing, moores law
  - thecopy 10y ago
    We know how to make them faster. How to make faster CPUs viable & affordable to the public though, that's a hard problem to solve.
    - RX14 10y ago
      Intel essentially has a monopoly on the market for desktop cpus, which can't help.
      - thecopy 10y ago
        Affordable air-cooled x86-CPUs at > 4GHz will disrupt that very quickly.
        k__ 10y ago
        Is x86 still needed? I mean the ARM stuff is getting more traction and maybe it will run around x86 in the next years.
        wbl 10y ago
        POWER already did by sucking vast amounts of electricity and dumping heat. Getting a high IPC isn't easy and leads to lots of thermal dissapation. Odd arches might make a comeback but don't help much.
      - jabl 10y ago
        If we assume that the economic model of CPU manufacturing is essentially - very large upfront costs in R&D and improved fabs - The marginal cost for each additional CPU manufactured is, in fact, very low Then, isn't this pretty much the textbook example of a natural monopoly? I.e. in such a case, if the market was spread out over more suppliers, would the customer in the end pay more due to the vendors amortizing the R&D costs over fewer units sold? Vs. the current situation where customers are paying monopoly prices to the incumbent vendor.
    - jabl 10y ago
      > We know how to make them faster. Well... Seems the reason for the "multicore revolution" that started around 2005-ish(?) for desktop/x86 server CPU's was largely that CPU designers ran out of ways to make cpu's faster. Previously, there was always some micro-architectural feature waiting to be exploited (say, caches, pipelining, superscalar, OoOE, branch prediction, etc.) that enabled processor designers to utilize the transistors Moore's law gave us in order to increase single-threaded performance. However, it seems that at about the same time we ran into a triple whammy; 1) at about the same time that processor designers ran out of new tricks (with massive payoffs) to pull from their sleeves. 2) existing tricks ran far into diminishing returns 3) transistor scaling wasn't as good as before (the "power wall") tl;dr: We seem to know a lot of tricks that can increase performance a bit, albeit at a heavy cost in power consumption.
ronjouch 10y ago
The post goes directly from "heap allocations were frequent within rustc" to "effort to minimize heap allocations", and proceeds to detailing speedups. → Systems programming newbie question: why are heap allocations bad for performance? Is it the additional level of indirection? The cost of calling your memory allocator? Something else? My background, if that helps focusing answers: python/js programmer, did a tiny bit of C/C++, am ~approximately~ familiar with the stack (call frames, each with its context) vs. the heap (where to allocate memory for big/long-lived objects e.g. arrays and trees).
- unwind 10y ago
  I think it's mainly cache effects; things in heap memory tend to be more spread out, and that hurts spatial locality which is the basis of caching. The indirection is part of this too, since "jumping around" following pointers can pollute the cache which in turn can make subsequent accesses slower. Sure, the allocator itself can be expensive, and that's certainly important if you're doing "too many" allocations, but in general I think it's worse caching that matters the most.
  - twoodfin 10y ago
    This is important to keep in mind when looking at profiling reports: The cost of cache effects (both I and D!) can be spread throughout the critical path. Even if your profile shows your allocator being executed only in (say) 2% of the samples, if what it's doing during that time is pushing lots of useful instructions or data out of the fastest caches into which they otherwise would fit, the total cost of that allocation is likely much greater, but hard to pinpoint.
    - ronjouch 10y ago
      Thanks unwind/twoodfin! @twoodfin, can you precise what you mean by "cache effects (both I and D!)" ? (Indirect and Direct? By Indirect you mean Associative and by Direct you mean Direct Mapped as defined in http://www.ecs.umass.edu/ece/koren/architecture/Cache/tutorial.html http://www.ecs.umass.edu/ece/koren/architecture/Cache/tutori... ?). Also, googling "direct indirect cache" yielded the hilarious http://onlinelibrary.wiley.com/doi/10.1046/j.1439-0310.2003.00897.x/abstract http://onlinelibrary.wiley.com/doi/10.1046/j.1439-0310.2003.... To other programmers not so familiar with CPU caching, resharing two blurbs that helped me get a start of a grasp on it: - Why do CPUs have multiple cache levels? https://news.ycombinator.com/item?id=12245458 https://news.ycombinator.com/item?id=12245458 , https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-multiple-cache-levels/ https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-mu... - CppCon 2014 - Mike Acton: Data-oriented design and C++ , https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
stevedonovan 10y ago
Here's some thinking outside the box. Traditional compilers are focused on building an executable as fast as possible, throwing away an enormous amount of state each time. The new rustc incremental compilation attempts to re-use some of that computed state, although still early days. If however the compiler's state remains persistent (it is running as a daemon) then small code changes should usually be pretty fast - it's analogous to the code scanners of Eclipse. If the target of the compiler isn't a native executable, but a continuously updated image containing code, then the link gets pretty fast as well. The result will not be fast, but it will be _fast enough_ to test changes.
- amelius 10y ago
  Yes, and it would be even nicer if such techniques would be available outside the compiler community. In fact, it could perhaps even be a language feature.
  - deleted 10y ago
    [deleted]
  - pjmlp 10y ago
    You mean like Lisp, Smalltalk?
    - vanderZwan 10y ago
      The new kid on the Smalltalk block is Pharo: http://pharo.org/ http://pharo.org/
    - adamrezich 10y ago
      Also that language Jonathan Blow is working on https://www.youtube.com/watch?v=HLk4eiGUic8 https://www.youtube.com/watch?v=HLk4eiGUic8
- grokys 10y ago
  I think the Roslyn compiler does something similar to what you're suggesting. http://www.dotnetcurry.com/csharp/1258/dotnet-platform-compiler-roslyn-overview http://www.dotnetcurry.com/csharp/1258/dotnet-platform-compi... > Every time a developer changes a single character in any of the files, a new copy of all the data structures is created, leaving the previous version unchanged. This allows a high level of parallelism and concurrency in the Roslyn engine, as well as in its consumers, thereby preventing any race conditions to occur. Of course, in the interest of performance, these operations are highly optimized and reuse as much of the existing data structures as possible. Again, those being immutable makes this possible!
vanderZwan 10y ago
Nice article, although I would have liked to see a before/after summary bar chart of the benchmarks for all PRs as a whole; I'm curious how all these incremental improvements add up together.
- snovv_crash 10y ago
  You can find roughly that here, unfortunately mixed in with everything else though: http://perf.rust-lang.org/ http://perf.rust-lang.org/
- nnethercote 10y ago
  I too would like that! But lots of other changes have been landing concurrently, so it's hard to isolate the effect of my changes.
TazeTSchnitzel 10y ago
Is heap allocation actually unavoidable? PHP uses an arena allocator for its AST. I don't know how applicable that could be to Rust.
- hackcrafter 10y ago
  Not that applicable. Rust memory model around strong ownership and borrow-checking differs from the GC languages that can use generational strategies and lots of heap allocation re-use. All languages are doing allocations to the OS, rust just doesn't have a GC like PHP does to intermediate.
  - TazeTSchnitzel 10y ago
    PHP's compiler is written in C, and its AST isn't garbage-collected. I think we just throw out the entire arena, actually.
    - slededit 10y ago
      Technically its a very limited form of garbage collection... Then again with this definition so is just not free-ing anything and letting the OS cleanup after process exit.
      - TazeTSchnitzel 10y ago
        I believe it's manually freed.
- rkangel 10y ago
  There are plenty of things that could be used to speed up particular hotspots - arena allocators are one option. Better than that is to not allocate at all, which is the focus of the effort here. A step further down the line of optimisation may identify allocation hotspots and use custom allocation strategies rather than using the language default (the heap).
- Manishearth 10y ago

170 points by nnethercote 10y ago

Can rust capitalize on LTO/PGO? Even if that's not quite ready for primetime, if we're spending 50% or more time in the LLVM backend, that certainly can be built with LTO/PGO. Seems like it might be worth the trouble/bootstrapping challenge if it yields another ~5%.

corndoge 10y ago
we should just make computers faster, intel is failing, moores law
- thecopy 10y ago
  We know how to make them faster. How to make faster CPUs viable & affordable to the public though, that's a hard problem to solve.
  - RX14 10y ago
    Intel essentially has a monopoly on the market for desktop cpus, which can't help.
    - thecopy 10y ago
      Affordable air-cooled x86-CPUs at > 4GHz will disrupt that very quickly.
      - k__ 10y ago
        Is x86 still needed? I mean the ARM stuff is getting more traction and maybe it will run around x86 in the next years.
        wbl 10y ago
        POWER already did by sucking vast amounts of electricity and dumping heat. Getting a high IPC isn't easy and leads to lots of thermal dissapation. Odd arches might make a comeback but don't help much.
    - jabl 10y ago
      If we assume that the economic model of CPU manufacturing is essentially - very large upfront costs in R&D and improved fabs - The marginal cost for each additional CPU manufactured is, in fact, very low Then, isn't this pretty much the textbook example of a natural monopoly? I.e. in such a case, if the market was spread out over more suppliers, would the customer in the end pay more due to the vendors amortizing the R&D costs over fewer units sold? Vs. the current situation where customers are paying monopoly prices to the incumbent vendor.
  - jabl 10y ago
    > We know how to make them faster. Well... Seems the reason for the "multicore revolution" that started around 2005-ish(?) for desktop/x86 server CPU's was largely that CPU designers ran out of ways to make cpu's faster. Previously, there was always some micro-architectural feature waiting to be exploited (say, caches, pipelining, superscalar, OoOE, branch prediction, etc.) that enabled processor designers to utilize the transistors Moore's law gave us in order to increase single-threaded performance. However, it seems that at about the same time we ran into a triple whammy; 1) at about the same time that processor designers ran out of new tricks (with massive payoffs) to pull from their sleeves. 2) existing tricks ran far into diminishing returns 3) transistor scaling wasn't as good as before (the "power wall") tl;dr: We seem to know a lot of tricks that can increase performance a bit, albeit at a heavy cost in power consumption.

ronjouch 10y ago

The post goes directly from "heap allocations were frequent within rustc" to "effort to minimize heap allocations", and proceeds to detailing speedups. → Systems programming newbie question: why are heap allocations bad for performance? Is it the additional level of indirection? The cost of calling your memory allocator? Something else? My background, if that helps focusing answers: python/js programmer, did a tiny bit of C/C++, am ~approximately~ familiar with the stack (call frames, each with its context) vs. the heap (where to allocate memory for big/long-lived objects e.g. arrays and trees).

unwind 10y ago
I think it's mainly cache effects; things in heap memory tend to be more spread out, and that hurts spatial locality which is the basis of caching. The indirection is part of this too, since "jumping around" following pointers can pollute the cache which in turn can make subsequent accesses slower. Sure, the allocator itself can be expensive, and that's certainly important if you're doing "too many" allocations, but in general I think it's worse caching that matters the most.
- twoodfin 10y ago
  This is important to keep in mind when looking at profiling reports: The cost of cache effects (both I and D!) can be spread throughout the critical path. Even if your profile shows your allocator being executed only in (say) 2% of the samples, if what it's doing during that time is pushing lots of useful instructions or data out of the fastest caches into which they otherwise would fit, the total cost of that allocation is likely much greater, but hard to pinpoint.
  - ronjouch 10y ago
    Thanks unwind/twoodfin! @twoodfin, can you precise what you mean by "cache effects (both I and D!)" ? (Indirect and Direct? By Indirect you mean Associative and by Direct you mean Direct Mapped as defined in http://www.ecs.umass.edu/ece/koren/architecture/Cache/tutorial.html http://www.ecs.umass.edu/ece/koren/architecture/Cache/tutori... ?). Also, googling "direct indirect cache" yielded the hilarious http://onlinelibrary.wiley.com/doi/10.1046/j.1439-0310.2003.00897.x/abstract http://onlinelibrary.wiley.com/doi/10.1046/j.1439-0310.2003.... To other programmers not so familiar with CPU caching, resharing two blurbs that helped me get a start of a grasp on it: - Why do CPUs have multiple cache levels? https://news.ycombinator.com/item?id=12245458 https://news.ycombinator.com/item?id=12245458 , https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-multiple-cache-levels/ https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-mu... - CppCon 2014 - Mike Acton: Data-oriented design and C++ , https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc

stevedonovan 10y ago

Here's some thinking outside the box. Traditional compilers are focused on building an executable as fast as possible, throwing away an enormous amount of state each time. The new rustc incremental compilation attempts to re-use some of that computed state, although still early days. If however the compiler's state remains persistent (it is running as a daemon) then small code changes should usually be pretty fast - it's analogous to the code scanners of Eclipse. If the target of the compiler isn't a native executable, but a continuously updated image containing code, then the link gets pretty fast as well. The result will not be fast, but it will be _fast enough_ to test changes.

amelius 10y ago
Yes, and it would be even nicer if such techniques would be available outside the compiler community. In fact, it could perhaps even be a language feature.
- deleted 10y ago
  [deleted]
- pjmlp 10y ago
  You mean like Lisp, Smalltalk?
  - vanderZwan 10y ago
    The new kid on the Smalltalk block is Pharo: http://pharo.org/ http://pharo.org/
  - adamrezich 10y ago
    Also that language Jonathan Blow is working on https://www.youtube.com/watch?v=HLk4eiGUic8 https://www.youtube.com/watch?v=HLk4eiGUic8
grokys 10y ago
I think the Roslyn compiler does something similar to what you're suggesting. http://www.dotnetcurry.com/csharp/1258/dotnet-platform-compiler-roslyn-overview http://www.dotnetcurry.com/csharp/1258/dotnet-platform-compi... > Every time a developer changes a single character in any of the files, a new copy of all the data structures is created, leaving the previous version unchanged. This allows a high level of parallelism and concurrency in the Roslyn engine, as well as in its consumers, thereby preventing any race conditions to occur. Of course, in the interest of performance, these operations are highly optimized and reuse as much of the existing data structures as possible. Again, those being immutable makes this possible!

vanderZwan 10y ago

Nice article, although I would have liked to see a before/after summary bar chart of the benchmarks for all PRs as a whole; I'm curious how all these incremental improvements add up together.

snovv_crash 10y ago
You can find roughly that here, unfortunately mixed in with everything else though: http://perf.rust-lang.org/ http://perf.rust-lang.org/
nnethercote 10y ago
I too would like that! But lots of other changes have been landing concurrently, so it's hard to isolate the effect of my changes.

TazeTSchnitzel 10y ago

Is heap allocation actually unavoidable? PHP uses an arena allocator for its AST. I don't know how applicable that could be to Rust.

hackcrafter 10y ago
Not that applicable. Rust memory model around strong ownership and borrow-checking differs from the GC languages that can use generational strategies and lots of heap allocation re-use. All languages are doing allocations to the OS, rust just doesn't have a GC like PHP does to intermediate.
- TazeTSchnitzel 10y ago
  PHP's compiler is written in C, and its AST isn't garbage-collected. I think we just throw out the entire arena, actually.
  - slededit 10y ago
    Technically its a very limited form of garbage collection... Then again with this definition so is just not free-ing anything and letting the OS cleanup after process exit.
    - TazeTSchnitzel 10y ago
      I believe it's manually freed.
rkangel 10y ago
There are plenty of things that could be used to speed up particular hotspots - arena allocators are one option. Better than that is to not allocate at all, which is the focus of the effort here. A step further down the line of optimisation may identify allocation hotspots and use custom allocation strategies rather than using the language default (the heap).
Manishearth 10y ago