Exploring PGO for the Rust compiler

[michaelwoerister]

This issue is a landing place for discussion of whether and how to apply profile-guided optimization to rustc. There is some preliminary investigation of the topic in the Exploring PGO for the Rust compiler post on the Inside Rust blog. The gist of it is that the performance gains offered by PGO look very promising but we need to

• confirm the results on different machines and platforms,
• make sure that there are no reasons to not do PGO on the compiler, and
• find a feasible way to implement this on CI (or find a less ambitious alternative).

Let's start with the first point.

Confirming the results

The blog post contains a step by step description of how to obtain a PGOed compiler -- but it is rather time consuming to actually do that. In order to make things easier I could provide a branch of the compiler that has all the changes already applied and, more importantly, a pre-recorded, checked-in .profdata file for both LLVM and rustc. Alternatively, I could just put up the final toolchain for download somewhere. Even better would be to make it available via rustup somehow. Please comment below on how to best approach this.

Reasons not to do PGO?

Concerns raised so far are:

• This makes rustc builds non-reproducible -- something which I don't think is true. With a fixed .profdata file, both rustc and Clang should always generate the same output. That is -Cprofile-use and -fprofile-use do not introduce any source of randomness, as far as I can tell. So if the .profdata file being used is tracked by version control, we should be fine. It would be good to get some kind of further confirmation of that though.

• If we apply PGO just to stable and beta releases, we don't get enough testing for PGO-specific toolchain bugs.

• It is too much effort to continuously monitor the effect of PGO (e.g. via perf.rlo) because we would need PGOed nightlies in addition to non-PGOed nightlies (the latter of which serve as a baseline).

• Doing PGO might be risky in that it adds another opportunity for LLVM bugs to introduce miscompilations.

• It makes CI more complicated.

• It increases cycle times for the compiler.

The last two points can definitely be true. Finding out whether they have to be is the point of the next section:

Find a feasible way of using PGO for rustc

There are several ways we can bring PGO to rustc:

1. Provide rustbuild support for easily building your own fully PGOed compiler.
2. Provide PGOed builds only for stable and beta releases, where the additional cycle time is offset by the lower build frequency.
3. Provide a kind of "best-effort" PGO which uses out-dated (but regularly updated) profiling data, in the hope that it is accurate enough to still give most of the gains.

Let's go through the points in more detail:

1. Easy DIY PGO via rustbuild - I think we should definitely do this. There is quite a bit of design space on how to structure the concrete build options (@luser has posted some relevant thoughts in a related topic). But overall it should not be too much work, and since it is completely opt-in, there's also little risk involved. In addition, it is also a necessary intermediate step for the other two options.

2. PGO for beta and stable releases only - The feasibility of option (2) depends on a few things:

• Is it acceptable from a testing point of view to build stable and beta artifacts with different settings than regular CI builds? Arguably beta releases get quite a bit of testing because they are used for building the compiler itself. On the other hand, building the compiler is a quite sensitive task.

• Is it technically actually possible to do the long, three-phase compilation process on CI, or would we run into time limits set by the infrastructure? We might be more flexible in this respect now than we have been in the past.

• How do we handle cross-compiled toolchains where profile data collection and compilation cannot run on the same system? A simple answer there is: don't do PGO for these targets. A possible better answer is to use profiling data collected on another system. This is even more relevant for the "best-effort" approach as described below.

Personally I'm on the fence whether I find this approach acceptable or not -- especially given that there is a third option that is potentially quite a bit better.

3. Do PGO on a best-effort - After @pnkfelix asked a few questions in this direction, I've been looking into the LLVM profile data format a bit and it looks like it's actually quite robust:

• Every function entry contains a hash value of the function's control flow graph. This gives LLVM the ability to check if a given entry is safe to use for a given function and, if not, it can just ignore the data and compile the function normally. That would be great news because it would mean that we can use profile data collected from a different version of the compiler and still get PGO for most functions. As a consequence, we could have a .profdata file in version control and always use it. An asynchronous automated task could then regularly do data collection and check it into the repository.

• PGO works at the LLVM IR level, so everything is still rather platform independent. My guess is that the majority of functions has the same CFG on different platforms, meaning that the profile data can be collected on one platform and then be used on all other platforms. That might massively decrease the amount of complexity for bringing PGO to CI. It would also be great news for targets like macOS where the build hardware is too weak to do the whole 3-phase build.

• Function entries are keyed by symbol name, so if the symbol name is the same across platforms (which it should be the case with the new symbol mangling scheme), LLVM should have no trouble finding the entry for a given function in a .profdata file collected on a different platform.

Overall I came to like this approach quite a bit. Once we have a .profdata file being just another file in the git repository things become quite simple. If it is enough for that file to be "eventually consistent" we can just always use PGO without thinking about it twice. Profile data collection becomes nicely decoupled from the rest of the build process.

I think the next step is to check whether the various assumptions made above actually hold, leading to the following concrete tasks:

• Confirm that PGO is actually worth the trouble, i.e. independently replicate the results from the Exploring PGO for the Rust compiler blog post on different systems. (Done. See Exploring PGO for the Rust compiler #79442 (comment))
• Verify that the LLVM profdata format is as robust as described above:
  • Try to find documentation or ask LLVM folks if support for partially out-of-date profdata is well supported and an actual design goal (see Exploring PGO for the Rust compiler #79442 (comment))
  • Try to find documentation or ask LLVM folks if platform independence is well supported and an actual design goal.
  • Ask people who have experience using this in production.
  • Try it out: Compile various test programs with out-of-date data and data collected on another platform. See if that leads to any hard errors.
• Investigate how out-of-date profdata for rutsc typically is if it were collected only once a day (for example).
• Investigate how big the mismatch between different platforms is. Concretely:
  • How many hash mismatches do we get on x86-64 Windows and macOS when compiling with profdata collected on x86-64 Linux?
  • How many hash mismatches do we get on Aarch64 macOS when compiling with profdata collected on x86-64 Linux?
  • What about x86 vs x86-64?
• Investigate how much slower it is to build an instrumented compiler.
• Investigate if using profdata leads to a significant compile time increase, that is, make sure that it is feasible to always compile with -Cprofile-use.
• Double-check that PGO does not introduce a significant additional risk of running into LLVM miscompilation bugs. Ask production users for their experience.
• Check if Rust symbol names with the current (legacy) symbol mangling scheme are platform-dependent, or if we would need to switch the compiler to the new scheme if want to use profdata across platforms.
• Confirm that -fprofile-use and -Cprofile-use do not affect binary reproducibility (if used with a fixed .profdata file).

Once we know about all of the above we should be in a good position to decide whether to make an MCP to officially implement this.

Please post any feedback that you might have below!

[michaelwoerister]

One concern with the "best-effort" approach that I just became aware of is how it affects performance testing: Let's say you want to optimize some expensive function F in the compiler. You rewrite it to a more efficient version F', do a try-build, and a perf.rlo run to see if your optimizations had the desired effect. However, since F was compiled with PGO data available while F' is being compiled without PGO data, it will be an unfair comparison. F will have an advantage over F' and any performance improvement might not look as good as it actually is.

[jyn514]

One concern with the "best-effort" approach that I just became aware of is how it affects performance testing

This might be overcomplicating things, but what if the default was not to use PGO builds, and enable them only for nightly/beta/stable? Then F wouldn't have an unfair advantage, but we would still get most of the benefits of the "best effort" method.

The disadvantage is that nightlies will now require a second full build; it will no longer be possible to use the latest build artifacts from bors.

[andjo403]

a question that I think is missing is how storing .profdata in git is affecting the size of the repo. how big is the .profdata file and how mergeable is it.

[the8472]

A variation on approach3: Have stage1 gather PGO data while building stage2 for an auto-merge, then save that somewhere so it can be used during the next stage2 build of anything that has that merge as its nearest ancestor in the history.

[jhpratt]

@andjo403 While by no means a solution, git LFS may be helpful regarding the size of the repo.

[michaelwoerister]

a question that I think is missing is how storing .profdata in git is affecting the size of the repo. how big is the .profdata file and how mergeable is it.

That's a good point! .profdata files are in a binary format, I don't think they would be mergeable. They are rather big too. The .profdata files that I have for LLVM and rustc are 23 MB and 64 MB, respectively. On the other hand they compress rather well, to 3.1 MB and 9.4 MB for a .tar.xz in this case. That's still quite hefty if you add that kind of data to the repository once a day.

Using Git LFS sounds a bit problematic to me because of its reliance on external storage. Maybe the data could be stored in a separate repository that gets pulled in as a submodule? Then one would not have to pull the entire thing.

[michaelwoerister]

There seems to be a text-based profile data format that looks pretty mergeable:

_ZNK4llvm20MemorySSAWrapperPass14verifyAnalysisEv
# Func Hash:
22759827559
# Num Counters:
2
# Counter Values:
0
0

_ZN4llvm9DIBuilder17createNullPtrTypeEv
# Func Hash:
12884901887
# Num Counters:
1
# Counter Values:
0

_ZN4llvm15SmallVectorImplINS_26AArch64GenRegisterBankInfo17PartialMappingIdxEE6appendIPKS2_vEEvT_S7_
# Func Hash:
37713126052
# Num Counters:
3
# Counter Values:
0
0
0
# Num Value Kinds:
1
# ValueKind = IPVK_MemOPSize:
1
# NumValueSites:
1
0

I don't know how well supported it is. Surprisingly it seems to be slightly more compact than the binary format (20 MB vs 23 MB and 57 MB vs 64 MB). It also compresses better than the binary format. But it would have to be stored in the repository uncompressed in order to be diffable, right? Or does git have any tricks up its sleeve that allow it to store compressed diffs?