3 ms·
My experiments with profile-guided optimization have been thus far disappointing. Formulations I have encountered fail to respond to density of branch predicti
by ncmncm 6y ago
My 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.
- ncmncm 6y agoI explained the point in the very next paragraph, starting "The point I make...". Sometimes the compiler can guess what operations can be fused, if it knows what hardware the program will run on, and the vendor has revealed those details, and the compiler has incorporated all of them. But almost all programs are built for an ancient target, using a compiler version older than the actual target. When you really care about performance of a program, you compile it yourself, if you can, and add as much "-march=", "-lto", etc. hackery as you trust, and measure what difference all the different combinations (which interact!) make, and make sure they didn't introduce bugs (which they often do). But, as I noted, even after that there are lots of 2x effects the compiler doesn't understand. Many programs don't spend all their time in one loop, but almost all spend all their time in loops.
- scottlamb 6y agoRight, everything you've said is consistent with my "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". In other situations, many folks (including me) get 15% improvements from PGO, and it's hard to take seriously any argument that suggests that can't happen.