cmd/compile: feedback-guided optimization

[josharian]

This is an umbrella issue for supporting feedback-guided optimization. This has been discussed offhand in a few other contexts (inlining decisions: #17566, code layout decisions: #20356, language changes: #24204, stack growth: #18138).

It is not clear what the design for FGO/PGO support might look like. In particular, what do the feedback/profile files look like?

@aclements observed during conversation at GopherCon 2018 that in order to preserve reproducible builds and efficiency, the feedback file needs to be hashed by cmd/go along with all other inputs, which suggests that it ought to be committed to version control.

cc @randall77 @ianlancetaylor @aclements @crawshaw @bradfitz @CAFxX (and the list could go on, but I'm sure everyone will find it)

[seebs]

Oh, hey, I have a concrete example of a potentially-relevant case for this, which is a recurring thing that bites people with microbenchmarks, but may also affect real code:

In rare cases, trivial questions of code alignment can produce very large performance differences. I had a test case, at one point, where I had two functions which were getting roughly a 2x performance difference in benchmarking. (As in, one took twice as long as the other.) But the more I experimented, the more confused I became, because it turned out the functions were identical, and I could change which one was faster by reordering them in source.

The microbenchmark case probably doesn't matter, but there are real-world cases where a couple of likely-concurrent hot paths end up with some kind of problem which is entirely a function of the exact location of their code -- I'm guessing either "aligned or not aligned with cache line" or "in same cache-associativity group as other hot paths", but I don't have the expertise to dive into it far enough to be sure.

My guess is that there's some actual specialized code out there where inserting a handful of nops before some specific functions could produce a +/-20% performance change in the program as a whole. Figuring out which ones seems likely to be arbitrarily hard; you'd need some kind of framework for figuring out how to benchmark the functions, and how to benchmark different sets of functions in parallel, and so on.

This is the sort of thing which is a huge amount of work, and which doesn't provide any noticeable benefit until it does, and then it can be inordinately significant. (The big question is whether you end up perceiving it as "sometimes we get lucky and our code runs faster" or "sometimes we get unlucky and our code runs slower").

[dangit815]

More than two years have passed since the last discussion, is there any progress or plan on FGO recently?

[aclements]

I hadn't remembered we even had an open issue for this!

@cherrymui and @prattmic are actively doing prototype work right now to help us understand the potential wins from PGO/FGO/FDO and how to best integrate it into the build process. It's early stages, but we're tentatively hoping to have initial PGO optimizations available in 1.19.

[josharian]

Here's a related idea I've been kicking around.

Instead of doing running program -> profile -> compiler, add an extra intermediate step: running program -> profile -> optimization file -> compiler. The optimization file consists of optimization information and directives to the compiler.

There are a few advantages to this:

• the compiler can stay simpler
• being able to inspect and edit the optimizations file directly (or via a tool) will make it easier to understand what is happening, bisect, test, and minimize issues
• it opens the door for other mechanisms/tooling to add information and optimizations, such as: offline static analysis, offline human analysis, bespoke profiling techniques, or combining profiles taken across a fleet of machines

[josharian]

@cherrymui and @prattmic are actively doing prototype work right now to help us understand the potential wins from PGO/FGO/FDO and how to best integrate it into the build process

Though I am delighted to hear this, I feel compelled to say yet again: I wish we had a more predictable, repeatable mechanism to learn things like this than someone happening to ping a relevant issue.

[thepudds]

Though I am delighted to hear this, I feel compelled to say yet again: I wish we had a more predictable, repeatable mechanism to learn things like this than someone happening to ping a relevant issue.

Is this the type of thing that could get covered in the “Compiler and Runtime Meeting Notes“ tracking issue #43930 ?

That did seem useful, although I know it takes some work.

[prattmic]

Instead of doing running program -> profile -> compiler, add an extra intermediate step: running program -> profile -> optimization file -> compiler. The optimization file consists of optimization information and directives to the compiler.

I have received similar feedback in discussing this with one user: that they would like a way to manually specify optimizations that a PGO profile might indicate if capturing actual profiles is not possible/representative or via, as you say "offline human analysis". They specifically mentioned //go: directives, but I think a separate edit-able file would work as well.

[jeremyfaller]

Is this the type of thing that could get covered in the “Compiler and Runtime Meeting Notes“ tracking issue #43930 ?

That did seem useful, although I know it takes some work.

CC @josharian

Yeah. I haven't been maintaining that of late. My apologies. (It's kinda fallen on the pile of "stuff I should get to".) I'll try to do better. :)

Having said that it's unlikely that PGO would have made that tracking issue. PGO started in experimental form, and we were only trying to see if it was worth pursuing. Our experimentation and the results from some external groups lead us to believe PGO might make the 2022 roadmap, but we're still trying to figure out what form it will take.

[cristaloleg]

Regarding PGO in the latest .NET 6 release https://devblogs.microsoft.com/dotnet/announcing-net-6/#dynamic-pgo and https://devblogs.microsoft.com/dotnet/announcing-net-6/#dynamic-pgo (UPD: there is a 2nd Dynamic PGO paragraph closer to the end of the article)

[mvdan]

To echo #28262 (comment), #49688 came as a surprise to seemingly everyone except the compiler team. If #43930 isn't the right medium to keep everyone else in the loop, perhaps consider trying something else. My gut feeling is that those public weekly notes are a good starting point, and I'd like to see them resume - especially if they included a very brief summary of the main projects currently in progress.

To hopefully give a bit of perspective: the lack of transparency into what is being actively considered or experimented on discourages external contributions. Using this thread as an example, it seems like Josh has been thinking about this idea for a while, and I'd bet he would contribute towards the design, testing, and perhaps even coding/reviews. That kind of external involvement simply isn't going to happen if there isn't a public way to be kept in the loop, though.