6 ms·
Exploring PGO for the Rust Compiler
- ibraheemdev 6y agoTLDR -- PGO reduces build times by 10-16% but is not straightforward to realize in CI.
- The_rationalist 6y agoWhy isn't it straightforward, isn't autofdo automating the process?
- ibraheemdev 6y ago> Unfortunately, bringing these improvements to end users is not as simple as adding a few compiler flags to our dist builds. PGO is different from most other optimizations in that it: - requires a different, extended build workflow due to the additional instrumentation and data collection phases, and - it incurs a sustained build time cost (a trait it shares with other automated optimizations like LTO).
- The_rationalist 6y agoAutofdo if automatically called by the rust toolchain should alleviate the first point https://github.com/google/autofdo https://github.com/google/autofdo (though it only work on Linux) How much percent slower is the build time with PGO on average?
- oscardssmith 6y agoIt depends. The thing that makes pgo good is that it bases it's compile off of analysis of runtime behavior. For that to work, you have to run the problem long enough to get a representative sample. For some programs, that can be a big speed decrease.
- Ar-Curunir 6y agoI think it would be a massive boost to the ecosystem to have at least stable and beta use PGO; 16% speed ups are amazing at this point in Rust’s lifetime!
- chrismorgan 6y agoIf stable and beta used PGO and nightly didn’t and was consequently 10–20% slower, then there would suddenly be an actual reason to not use nightly! I’m not sure whether that would be good or bad.
- fluffything 6y agoI would just use beta instead and "turn it" into a nightly compiler with RUSTC_BOOTSTRAP=1.
- dodobirdlord 6y agoThat flag does more than just enable unstable features in the stable compiler, and it should be avoided unless you are actually compiling rustc.
- est31 6y agoThere are multiple reasons to avoid nightly. One of them is that you don't have to constantly rebuild the entire graph when you want to stay up to date because stable is "only" updated every 6 weeks. Another being that you are less subject to regression bugs hitting you.
- gpm 6y agoYou can "only"update nightly every 6 weeks as well, or every 6 months. Nothing says you have to stay up to date. In practice I update when there is something I want in a more recent release. This happens more often with nightly because there are more bugs to be fixed and feature changes, but it isn't that often.
- The_rationalist 6y agoI hope that the rust compiler team is considering to integrate BOLT by default too https://github.com/facebookincubator/BOLT https://github.com/facebookincubator/BOLT (I'm aware it's being integrated into llvm but rust could integrate the external BOLT in it's toolchain in the meantime, free performance gain for everyone is nice to have right now)
- ibraheemdev 6y agoThis was discussed here [1]. The conversation died off around a year ago. Not sure why... Although, it is pretty clear that BOLT's optimizations are not "free". For example: > BOLT uses enormous amount of memory (about 6GB). > Perf needs to be ran with LBR support; this is almost always unsupported with VMs (which means you don't want to run the measurement inside CI). [1] https://github.com/rust-lang/rust/issues/50655 https://github.com/rust-lang/rust/issues/50655
- The_rationalist 6y agoInteresting, would be nice for rustc to have a special flag that enable "maximum performance" at any compile time/ram price
- the8472 6y agoAt any price? You could throw something like souper at the problem[0]. It makes compilation about 20 times slower in some benchmarks in their paper. This is on the IR level, iirc similar optimizers exist for assembly generation, so you can throw that in as another pass. [0] https://github.com/google/souper https://github.com/google/souper
- MaxBarraclough 6y ago> At any price? Seems to me that raising the ceiling on optimisation is good to have, even if the computational cost is very high. If it works reliably, it wouldn't be necessary to do optimised release builds very often, and they could be offloaded onto a heavyweight build server, perhaps on the cloud.
- ibraheemdev 6y agoHow do Rust build times compare to Scala?
- nindalf 6y agoIt’s hard to compare across languages. Too many independent variables to consider. Take the example of grep vs Ripgrep. Is it fair to compare the compile times of grep written in C with ripgrep? I can see arguments both ways. What I can say with confidence is that Rust build times have improved continuously in the last 2 years. It’s now 30-50% faster on common programs. The future is bright too, a new debug back end out in 2021 promises a further 50% improvement.
- ibraheemdev 6y agoDo you have a reference for that "new debug back end"?
- estebank 6y agohttps://hacks.mozilla.org/2020/10/a-new-backend-for-cranelift-part-1-instruction-selection/ https://hacks.mozilla.org/2020/10/a-new-backend-for-cranelif... https://github.com/bjorn3/rustc_codegen_cranelift https://github.com/bjorn3/rustc_codegen_cranelift
- ComputerGuru 6y agoProject Cranelift
- deleted 6y ago[deleted]
- dmit 6y agoOne of the reasons why it's hard to compare the two is that the standard metric is time/loc, and it varies hugely depending on which language features are used. Both languages have features that can blow up compile times by a factor of 1000 or more.
- 6y ago
- StreamBright 6y agoIs this about https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization?
- ibraheemdev 6y agoYup.
- crb002 6y agoMakes sense at this point to work with Sylvestre Ledru who maintains the Debian llvm-toolchain and rust packages.
- ncmncm 6y agoMy experiments with profile-guided optimization have been thus far disappointing. Formulations I have encountered fail to respond to density of branch prediction failures, which can easily make a 2x difference in performance, as it does in one program I have. If the profile were to log branch prediction failures, it might be able to favor conditional moves over branches in cases where it is found that the result of the condition is not predictable, or the reverse. I have another (in this case, Rust) program that demonstrates 2x performance difference based on the order in which exactly two instructions are emitted. Profile-guided optimization always chose the slower version. In that case, putting the instructions in the correct order enabled fusing two pairs of instructions and looping in one cycle. In the chosen order, the instructions did not fuse, and the loop took two cycles. That loop dominated execution time, for an almost 2x overall result. To choose correctly depends on the compiler knowing a great deal more about the target microarchitecture than can reasonably be expected of a compiler. (I know that it chose wrongly only because I had an exact C++ translation of the program, and the C++ compiler was sometimes persuaded to choose correctly.) The point I make here is that the choices that optimizers make in response to profile information typically amount to much less than 10% of runtime, so are easily overwhelmed by effects of random microarchitectural details that are not practical for a production compiler to act on. What seems to the optimizer like a better choice may be, instead, radically worse. That they achieve any positive result, on average, with or without profile guidance, is impressive: a dancing bear. The fact also means that we generally don't know how fast a program ought to run, or whether 2x gains from trivial choices remain to be discovered. This is fallout from the deal we have made with the Devil by relying so heavily on very complex runtime optimization mechanisms whose consequences we poorly understand. Our programs run much faster with such hardware acceleration gimcrackery, but we can no longer reason about the effect of a prospective change, and must resort to measuring. Measuring, we don't know what effects are or are not in play in different runs. We don't even know all the choices available, as microarchitectures are always very sketchily documented. They will only ever become less predictable: what is faster on skylake may be persistently slower on mudlake.
- scottlamb 6y ago> I have another (in this case, Rust) program that demonstrates 2x performance difference based on the order in which exactly two instructions are emitted. ... That loop dominated execution time, for an almost 2x overall result. I think a program like this—where two instructions in one loop is almost the entire execution time—isn't the right one to expect profile-guided optimization to greatly improve. I think instead it's complex programs where there's too much hot stuff to reasonably put human attention into it all. On programs like this, I really have gotten 15% improvements from an AutoFDO pipeline. Honestly I don't know exactly how it achieves that. I can make some guesses but will probably be wrong. Eg I was surprised when the "machine function splitter" was introduced recently that it wasn't already doing that. But generally speaking, I'd expect skilled human optimization to make the most difference at the smallest scales: less hot code, changing infrequently, targeting fewer critical (micro)architectures. I'd expect compiler optimization to make the most difference elsewhere. I don't think profile-guided optimization is an exception to this general rule. > To choose correctly depends on the compiler knowing a great deal more about the target microarchitecture than can reasonably be expected of a compiler. fwiw, it doesn't seem crazy to me to expect the compiler to know what operations can be fused.
- hansjorg 6y agoIs the profile data or the resulting PGOed binary useful for identifying spots that could be improved manually?
- pabs3 6y agoDoes PGO mean the build products are non-deterministic? ie if you build the Rust compiler twice you get different bits.
- todd8 6y agoIt's not clear from the article, but PGO isn't a new technique. In 1989, my Decstation 3100 running a Berkley kernel based Unix on a MIPS processor had a compiler option that used a profile to guide its C compiler optimizer. I don't recall how well it worked. At that level of optimization I tended to use it very little since I was spending most of my time trying to architect, develop and debug a new distributed system.
- Arcuru 6y agoInstead of wall time, the cycle counts should be a little less noisy as they will actually account for the threads getting switched out. In this case they show a relatively similar reduction from a quick glance. > One plausible explanation would be that PGO improves instruction cache utilization, something which makes a difference for execution time but would not be reflected in the amount of instructions executed. Yes, this is a big reason why PGO is useful. It places the hot code together for improved ICache performance, while keeping the colder basic blocks separate (though there are likely some strategies here I don't know about). You could show the ICache miss counter and prove that this is the case. > I also don't know how branch mispredictions factor into instruction counts -- branch prediction being another aspect explicitly targeted by PGO. Branch mispredictions won't show up directly in the instruction counts, but they will show up indirectly through lower CPI or you can explicitly look at the counters for branch misses and compare between the two runs. If you were asking about whether speculative instructions from the missed branch are counted, they are not. Instructions are only counted once they are retired. (Intels counter for this is specifically named "Instructions Retired" to clarify that distinction). > In order to make the collected data as useful as possible, we should try to exercise all the common code paths within the compiler. I typically use the "standard" rustc-perf benchmark suite for this purpose This is not correct, though maybe just misstated. You need to exercise the code with inputs that are representative of the code you want to optimize for. Mozilla does this with the Firefox build (presumably) by using the Firefox build itself as an input since it is small enough. That's a perfect 1:1, so their performance gains are as good as possible. This post does the same thing, using the same Benchmark suite as training data and for testing, but the goal is to use this optimized rustc to compile other Rust programs. It would probably be better to show the results on a separate set of benchmarks to see how well PGO does for the general use case of "compiling Rust code" instead of "compiling the training data". Source: Did a lot of performance analysis (with a heavy use of counters) at my last job at Microsoft. They were very useful when we needed to do detailed analysis between x86 and ARM, among other things. I didn't work on PGO but a sibling team did, it was used extensively for the Windows builds. It was an interesting job, but unfortunately moving further up the stack to be a low level code monkey working on boring backend development at a colorful cloud company pays significantly better.
- 6y ago