Exploring PGO for the Rust Compiler

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.

> 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.