Change https://go.dev/cl/430355 mentions this issue: design/55022-pgo.md: add design doc

This looks very interesting! Starting with the pprof format sounds good, but I have some concerns about its verbosity in two ways.

First, the files can be really big and processing them can be slow. When I work with profiling data manually, I often start with pprof-format files that include hundreds or thousands of samples, usually covering less than one thread-minute. For PGO, I'd be inclined to use "the most and best data available". For some applications I support, that means multi-megabyte pprof-format files which take multiple seconds to load. That's a big file to add to an application's source control repository (for build environments that work that way), and a big build speed hit if it applies to every package. The approach of "Some of these downsides can be solved transparently by converting the profile to a simpler, indexed format at build time and storing this processed profile in the build cache" sounds promising, but I wonder if that format should be obtainable through some explicit go tool subcommand, which could then be used until the next Go version series (re-generated when upgrading from go1.20.x to go1.21.y).

Second, how can application owners understand what the compiler is learning from the profile? When I encounter a bug that might be affected by or otherwise involve PGO, I'd like to be able to report it (including steps to reproduce) without accidentally disclosing proprietary information about the rest of my applications' performance and without accidentally changing the compiler's PGO-related decisions. When I have the choice between using a 100kB pprof file or a 10MB pprof file, I'd like to know if using the more detailed file actually changes the results. When reviewing a change to the PGO input file (maybe to adjust its weight towards more latency-critical parts of the app), I'd like to know what it's communicating to the compiler. These could also be addressed by a "simpler, indexed format" that is semi-stable and human-readable / human-redactable.

@rhysh thanks for the feedback!

Yes, if we later switch to a different format, we will provide a tool to convert profiles between the formats. And yes, if we choose a different format we will consider how to make it more human-readable. (We considered this possibility but it was unclear to me how to do that. There is also a range of possibilities. The human readable form could be very low level, basically a textual representation of the raw profile, to very high level, basically a list of "compiler optimization directives", or something in between.)

Related, I think the compiler will have an option to output what optimizations are done based on the profile, either through the -m, -json flag, or a new flag. Maybe that helps?

Visibility into the compiler's decisions via -m/-json/etc sounds like a big help, yes. That lets users report bugs like "I have this problem with the 'encoding/json' package when the compiler uses 'this list' of PGO decisions". Will the maintainers who receive a bug report like that be able to convince their copy of the compiler to apply the same set of PGO decisions?

If so, it sounds like we have the "simpler [...] format" described in the proposal, in an ad-hoc way. Maybe ad-hoc is all we need, and would keep the messier and less stable parts of the ecosystem out of the main go toolchain. But I can see it being useful enough to earn top-tier support over time.

This sounds like the "basically a list of 'compiler optimization directives'" option. What design challenges did you encounter with that? Thanks @cherrymui !

Like @rhysh, I feel strongly that the .pgo file format should be something more like a hand-editable list of compiler optimization directives, and definitely not a raw input like a pprof file. Reciting the list of reasons I gave for this previously, and adding some more...

• the compiler can stay simpler (internal)
• it is easier/possible to write compiler tests (internal)
• it is easier to debug: is the issue the interpretation of the pprof profile? (internal)
• users can easily see what it is doing
• users can bisect/minimize to figure out what optimization directive is causing issues (or providing speed-ups)
• provides a mechanism for advanced tuning, that everyone always wants compiler directives for
• 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
• it at least has a chance of supporting other common forms of optimization information, such as dynamic type info, starting goroutine stack sizes, scheduler hints
• if optimizations are not getting applied correctly (function renamed?), instead of having to generated a brand new profile, which could be expensive/difficult, it can be fixed directly by hand-editing
• easier to write CI tests around

Interesting idea about compiler optimization directive list for bug report. Thanks.

I thought for bug report due to PGO we would expect one to share the profile in order to reproduce the buggy build. It is understandable that this can be difficult in some cases. Maybe we can consider supporting an optimization list, even just for debugging purposes. (FWIW, we even had a prototype for optimization list (thanks @dr2chase) which I used for early experiments.)

One challenge is how to generate such an optimization directive list from raw profiles. For a streamlined user experience, one would take profiles from production binary, and go build could use that to build a new binary, without much manual work. So if we use optimization list, we will need a tool to convert/compute it from the raw profile. I would think the tool will need to, besides parse the profile, also parse the source files, do some analysis such as control flow propagation, etc., in order to map profile samples to optimization decisions. This has a lot overlap with what the compiler already does. So, instead of building a separate tool (and keep in in sync with the compiler), probably we just let the compiler do it.

Another benefit for profiles is that we can do multiple optimizations based on, say, a CPU profile. If we add a new type of PGO-based optimization, one would automatically get the optimization without taking a new profile. For optimization lists, one would need to explicitly add it to the file.

I'm not really clear what the optimization list would include. Should it be binary (boolean) options, or weights? Binary options sound simpler, but maybe weights are better for optimizations, so the compiler can take into account the information from source code and its own analysis?

There is also the question about the file becoming stale. Of course profiles can also become stale. It might be possible to design an optimization directive list format that is resilient to staleness.

Maybe one option is to have the compiler

• accept pprof profiles
• generate an optimization list based on profile
• also accept an optimization list as an alternative / debugging option ?

Non-main packages

As a package writer, I cannot supply any improvements. It would require package users to implement pgo benchmarks that hits my package. Writing these benchmarks to build cpu profiles are far from trivial. As a result 99% of all compiles with my packages would be without (useful) pgo.

You mention this as future work, but it seems like a big miss.

Platforms

This will only cover platform independent code. Much optimized code has separate code paths for different platforms. As proposed I don't see any reasonable way to handle multiple platforms automatically, for example when cross-compiling.

You could make this a user problem, and say they should use go build -pgo=$GOOS_$GOARCH.pgo, but it isn't very friendly, and will probably hinder adoption.

Future Optimization Scope

I may be lacking imagination, but I don't see the scope of this going much beyond inline decisions.

Maybe with branch-information, you could re-order unordered switch statements to check the most common targets first. Maybe some auto-vectorization could be done in a few cases.

To justify such a rather complex setup it is important to keep the end-goal in sight.

Counter Proposal: Simplify Proposal

I appreciate the intent to make this automatic and low-effort. But writing the benchmarks and/or capture useful profiles is a big task and for a big application with many subsystems it will be a massive. While it proposes to just run pprof on a production server, apply the profile -> faster application, it isn't really that simple, since profiles would need to continuously be captured as code changes.

I very much agree with Josh, et al, that this should be simpler and in the hands of the developer.

To add to that, I know that Go doesn't like pragmas, but it seems to me with a few, well designed pragmas we could get the same result, that doesn't have all the problems.
I feel that that would bring us the benefit we are looking for in a much more controlled manner as described by Josh.

As far as I can see having a program propose pragmas (or code reordering) from a profile would be just as simple, and allows you to review the proposed changes before they are committed.

If Go still isn't ready for performance related pragmas, then an external file describing the same would also be an (IMO suboptimal) solution. I dread a bit how you would specify inlining at callers and auto-vectorization of a for loop without resorting to line numbers in such a file.

@klauspost Given inlining is the most significant optimisation mechanism, I believe even at the current status, pgo is a much valuable improvement. In addition to inlining, pgo can be applied to interface dispatch, which helps devirtualise method invocations, profiling on branch-taken frequency helps produce better code layout at the very least, and guides the optimiser toward better decisions in other operations such as loop unrolling, cloning operations through phi nodes, in extreme cases branch pruning is also a possibility.

While pragmas or external decorative files work on call graphs, optimisation decisions are most optimal when having information in the call trees, this would be a suboptimal proposal. Additionally, it is not internal details, so I would disagree with this idea.

@merykitty Thanks! I see your point with interface dispatch, where knowing common implementation could output implementation specific branches.

The other cases I don't really see as something that couldn't be done with pragsmas. Granted, generic implementations could make this hard to control, since they would probably apply to all instances.

I don't see how you can make branch pruning without the compiler being able to prove that branches are impossible, in which case you don't really need pgo. Branch reordering and loop unrolling (without vectorization) has very limited impact on modern CPUs.

Either way, I stand by my point, that as proposed seems like a complex system that is hard to use correctly, and will provide limited benefits. It is not a "set up and forget", which is my main problem.

I am hoping for a simpler system that is more controllable, that doesn't require 'main-function' implementation with continuous updates required, which provides 90% of the benefits.

One worry I have with using profiles directly is that it can easily be an unstable mechanism. If I profile a program's current build and use that profile to rebuild it with PGO, grabbing another profile would likely result in fairly different results. For example, if a function call used to take ~2% of CPU time due to being in a very hot path and PGO now inlines it, then it could become far less relevant in the second profile.

I imagine we want developers to only use PGO with profiles obtained from runs without PGO. Can we restrict that to prevent confusion?

@mvdan The ability to collect profiles from a PGO-optimized binary is actually a core requirement in our design because it simplifies profile collection significantly (you can collect directly from production deployments without need for some kind of unoptimized "canary" deployment used only for profile collection).

It certainly has the challenge you mention, which we call "iterative stability" and discuss here and here. Sections 4.2.1 and 5.2 of the AutoFDO paper also discuss this. This is something we will need to pay close attention to and test well to make sure results are stable, and may be an area where additional metadata could help (e.g., collecting a CPU "last branch record" (LBR) profile would tell us which basic blocks are frequently executed, even if they have become much cheaper, so, used carefully, that could further mitigate this issue).

@josharian Having a list of optimization directives (or pragmas in the source) is something we've thought about, and definitely has pros and cons. I certainly think we want PGO to be applicable from a profile (which I think you agree with?), but whether translation to optimization decisions happens directly in the compiler, or as a pre-processing step.

Some thoughts on list of advantages below. Note, this list actually talks about two axes: profile vs optimization list and binary vs plain text format. I think we could decide along either of these axes (e.g., we could use a plain-text format that describes the pprof profile).

• the compiler can stay simpler (internal)

I'm not sure I fully agree with this. While I agree that the compiler will be simpler if it only takes a list of directives rather than having to process a profile, something still needs to convert the profile to a list of directives. That new tool will contain the complexity, and share a lot of similarities with the compiler, perhaps even directly sharing code, depending on the specifics of the directives.

e.g., if inlining directives are binary decisions ("inline this function"), then the conversion tool should probably contain a near copy of the compiler's inlining heuristics so that it makes very similar decisions. That is perhaps less important if the directives are more abstract (providing an inlining importance "weight"?), but if we go too abstract then we are probably just describing a profile anyways.

As Cherry mentioned, one option here is that the compiler could accept either a profile or optimization list. When given a profile, it generates the optimization list to be used for future compilations.

• it is easier/possible to write compiler tests (internal)
• it is easier to debug: is the issue the interpretation of the pprof profile? (internal)

I agree this would be easier to test/debug because it adds an intermediate format which you could test both sides of.

• users can easily see what it is doing
• users can bisect/minimize to figure out what optimization directive is causing issues (or providing speed-ups)

100% agreed that a plain test format and an optimization list are more transparent about what is happening in the build.

• provides a mechanism for advanced tuning, that everyone always wants compiler directives for
• 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

While I agree that an optimization list makes manual optimization tuning easier/possible, that has not been a goal of this proposal, and it is something we have avoided adding pragmas for (also likely a reason we wouldn't have PGO work by adding pragmas to source code). I think it is a bigger discussion if we want to support custom tuning of optimizations.

or combining profiles taken across a fleet of machines

This strikes me as out of place in your list. We absolutely want to support (and encourage!) merging profiles from multiple instances in order to get a more representative sample. This seems to be a point in favor of pprof, as it is easy to merge pprof profiles (go tool pprof -proto 1.pprof 2.pprof > merged.pprof).

On the other hand, optimization lists seem difficult to merge. If one list says "inline foo" and the other says "do not inline foo", how do you merged? It seems in this case you'd still want to merge the profiles prior to generating the optimization list.

• it at least has a chance of supporting other common forms of optimization information, such as dynamic type info, starting goroutine stack sizes, scheduler hints

Earlier in our design we were planning to create a new PGO format specifically to have the flexibility of adding information beyond CPU profiles. We switched to proposing pprof directly because the format, while not perfect, is actually quite flexible.

e.g., dynamic type info could be encoded as a Label on Samples of calls describing the type being called (though for calls the type is already obvious from the call destination, so not the best example). Stack sizes could be sampled as Samples with Location == gp.startpc, and value == stack size.

The format is not perfect and we may find ourselves limited in the future (discussion here), but I think there is a lot of runway.

• if optimizations are not getting applied correctly (function renamed?), instead of having to generated a brand new profile, which could be expensive/difficult, it can be fixed directly by hand-editing

Agreed that a plain-text format makes fix-ups easier. We've discussed tooling for renames for pprof files, but plain text is easier.

• easier to write CI tests around

I'm not sure what you mean by this, could you expand?

@klauspost My opinion is that history tells us that using pragmas to guide optimizations doesn't sustain over time. What happens is that someone does a bunch of analysis with a specific compiler version and a specific set of benchmarks, and writes a bunch of pragmas that makes those benchmarks faster. So far so good. But two years later the compiler has changed, the libraries have changed, and the program has changed. The existing optimization pragmas have not changed, and no longer do any good, and occasionally actually do harm.

Profiling can have the same problem, of course, if nobody updates the profiles. But updating the profiles is a much simpler task than analyzing performance in detail, and therefore tends to happen more frequently. In the best case, updating the profiling is simply automated.

So over the long term, I believe that profile guided optimization is a better approach for most projects. It's unlikely to beat careful analysis and hand tuning at the point in time when that happens. But profile guided optimization is much cheaper in what is for most projects the greatest expense: developer time.

Just my opinion, of course, but based on experience.

@klauspost, just a small point

I don't see how you can make branch pruning without the compiler being able to prove that branches are impossible

Branch pruning here means splitting everything below the if to separate hot paths and cold paths in the whole function.

@klauspost

Platforms

This will only cover platform independent code. Much optimized code has separate code paths for different platforms. As proposed I don't see any reasonable way to handle multiple platforms automatically, for example when cross-compiling.

You could make this a user problem, and say they should use go build -pgo=$GOOS_$GOARCH.pgo, but it isn't very friendly, and will probably hinder adoption.

This is something we've been thinking about recently and are open to suggestions. I think we may want automatic build configuration selection eventually, but the details are tricky. Do we use suffixes, like .go files (default_linux_amd64.pgo)? That could make directories quite noisy with a dozen or more files (should we move to a subdirectory like testdata?). How should we handle selection for build tags?

What we've proposed I think is the MVP option which remains forward compatible with future auto-selection we might do.

(FWIW, I think that a single profile for all platforms is likely good enough for more users. A platform-specific one will of course be at least a bit better, but my intuition says that the vast majority of most profiles will be common across platforms. We could verify this with data by comparing profiles).)

@klauspost

I may be lacking imagination, but I don't see the scope of this going much beyond inline decisions.

To add to what others have said, we've actually been keeping an eye toward many possible PGO-based optimizations while designing this. Here's a non-exhaustive list:

Edit 2023-09-05: A more up-to-date and exhaustive list is here

• Inlining just seems like the obvious first step, since it's likely to provide a lot of bang for your buck. We've been talking about using PGO for inlining for many, many years. :)
• Local basic block ordering: ordering blocks within a function to cluster hot blocks and potentially improve branch prediction (though the win of the latter on modern CPUs is small).
• Register allocation: register allocation currently uses heuristics to determine a hot path and move spills off that hot path. PGO can tell it the true hot path.
• Function ordering: Clustering functions at a whole-binary level for better locality.
• Global block ordering: A step beyond function ordering. The basic form of this is hot/cold splitting, but it can be more aggressive than that.
• Indirect call devirtualization: If the profile shows that a particular function is by far the most common target of an indirect call, specialize the caller to check that that's the target and make a direct call if it is (possibly even inlining the target). (Edit: Note that this would apply to both closure calls and interface method calls.)
• Stenciling: Stencil hot generic functions, possibly based on type information from the profile.
• Map/slice pre-sizing: Pre-size maps and slices based on allocation site. (This requires more than a CPU profile.)
• Lifetime allocation: Co-locate allocations with similar lifetimes by allocation site. (This also requires more than a CPU profile.)

@klauspost thanks for the feedback!

Non-main packages

I totally agree that PGO for non-main packages are important (we want to do it for the standard library as well), and we spent quite some time considering it. But many details are still unclear to us. At the moment we're proposing what we know how to do, and leave the door open for future improvements including PGO for non-main packages. I think this is better than waiting.

It would require package users to implement pgo benchmarks that hits my package.

This is not what we expected. Instead, we expect the user to take profiles from their main program. If in that program your package is in the hot path, PGO will apply to your package.

Platforms

As @prattmic mentioned, we are proposing an MVP option which remains forward compatible with future improvements.

As mentioned in the design doc

In the future, we may support automatic lookup for different profiles for different build configurations (e.g., GOOS/GOARCH), but for now we expect profiles to be fairly portable between configurations.

By "portable", for example, if the workloads are similar across platforms, the hot functions on one platform is likely also hot on another platform.

See also "Input welcome" from the original post. We're particularly welcome input for naming default profiles.

Future Optimization Scope

I'm not really sure what your comment meant. But here is a (non-exhaustive) list of optimizations we plan to do in the future https://go.googlesource.com/proposal/+/master/design/55022-pgo.md#optimizations

I will first admit that I do not have direct experience with profile-guided optimization in any other language, and so my line of questioning here may be naive. If this seems like a nonsense question, I'm happy to accept that as an answer to avoid anyone feeling the need to do my homework for me! 😄

The proposal and some of the commentary above discusses the fact that a particular set of profile information is specific to a particular version of the compiler (because it may generate code with different execution characteristics) and to particular input source code (because changing the program will at least change the behavior of the part of the program that changed, and may also have knock-on effects elsewhere from optimizations that are able to consider global information).

I quite enjoy the fact that go test is able to (mostly) reliably determine when a particular part of the test cache has been invalidated by changes to the input source code. It works well enough that I rarely question whether it's working correctly, and am surprised in the rare cases where I catch it out by doing something particularly odd!

Of course I understand that profile-guided optimization cannot possibly be implemented with an automatically-maintained cache, because gathering profile information is always an explicit step and similarly it's up to the person running go build to decide which profile information is relevant to the current situation.

However, I do wonder if it seems feasible for the toolchain to automatically announce when a particular profile information file has been invalidated, so that I could be prompted to regenerate it. I assume "invalidated" is not a boolean value in this case but perhaps more like a code coverage report: how much of the program is still the same now as it was when this profile information was generated? What specific parts of the program are not covered by this profile because they have changed since the profile was generated? Was the profile generated from a program compiled with the same toolchain version as I'm currently using? (Hopefully this could also somehow take into account the degree to which the system can "make do" with mismatching profiles, giving higher precedence to changes that are outside the set that the compiler and trace format can account for automatically, as described in Stability to source code and compiler changes.)

With what I've understood from reviewing the proposal so far it seems like it would be too expensive to track this sort of "profile coverage" on a per-line or per-statement basis, since it would seem to require retaining some sort of checksum for every single line/statement. But I wonder if it would be feasible to track at a coarser grain, such as per-function, per-file, or per-package, just to give the user something meaningful to understand the results against, so that they can then use their intuition to estimate whether the indicated objects have changed enough to warrant the effort of capturing fresh profile data.

(For this question I'm imagining a situation where a team collects profile information semi-manually once and uses it for some time before semi-manually generating it again. I expect that the capability I'm describing would be far less useful in situations where a team is able to constantly gather profile information for a currently-running and feed it into the next build, as described in Iterative Stability. The software I spend most of my time working on is "shrinkwrap" software which we package and ship to users to run on their own computers, and so our ability to capture traces from real user runs is limited. "This feature is primarily intended for servers you can profile constantly" would be a perfectly reasonable argument to dismiss my questioning above, of course.)

easier to write CI tests around

I'm not sure what you mean by this, could you expand?

Yes, that was rather vague. :) It's similar to @apparentlymart's point (which is a good one).

In many systems, performance properties are correctness properties. Losing key optimizations can cause performance regressions, which can cause existing provisioning to be insufficient, which can take down a system. Even merely slowing down a system can cause cascading failures. (I speak from experience, unfortunately.)

The more opaque the toolchain and its inputs are, the harder it is to (a) write safety checks that detect performance problems before they make it to production and (b) diagnose performance issues after they make it to production. This is in some ways even worse with less severe regressions, which don't result in an obvious, immediate problem.

The obvious approach here using pprof files is to have excellent compiler diagnostic output. This puts us in the same boat as (for example) current inlining tests: exec a build from inside a test and check for magic output strings. It's kind of a miserable existence, but it works.

@apparentlymart's notion of a PGO fitness/staleness score would also help, albeit in a less fine-grained way.

Or to put it a different way: How do I code review a commit that replaces one pprof profile with a new one?

Thanks for the clarification, that makes sense. Having an optimization list doesn't solve the problem of determining if a new profile has "good" results, but it is at least easier to look at a diff and notice potentially worrying changes.

(Though if the list is thousands of lines long and changes a lot from profile-to-profile, then I imagine that could also be difficult to review).

Thanks.

I think we all agree that we want the compiler to emit an optimization list for optimizations it does based on a given profile.

Interesting idea about profile invalidation. I think that is a good point. And we can make the compiler emit some information when some profile information doesn't apply, either in the same optimization list file our some other file. I think it shouldn't be too hard or expensive.

Change https://go.dev/cl/447997 mentions this issue: DO NOT SUBMIT: tool for parallel PGO testing on gomotes

Change https://go.dev/cl/449500 mentions this issue: DO NOT SUBMIT: experiemntal pprof trimming tool

Excellent discussion here, and this initiative is really great overall. Reading the above, I think @klauspost has some very valid concerns, and I know how much effort he puts into making things perform really well.

I think that some pragmas (forced inlining hints) would be a huge help for package maintainers, and looking at older discussions it was denied with the argument that you could just "copy and paste code" to do the inlining yourself, which to me sounds absurd. Defining functions and methods is about clarity and human understanding, a layer that is removed at compile time, to make efficient execution the primary concern. There is a clash here, which could be improved upon.

My use case is primarily as app developer, but I have one or two modules that others use. I often do profiling of my primary application, which does some heavy reading, decompression, interning and correlations ... but that's just one profile. Another run might be to create data, not to read it. So are multiple profiles supported, and how are they prioritized?

For module developers, there is no reason not to think that they are actually the specialists on what performs or not, and not allowing them to "chip in" with knowledge (either by manual inline pragma hints or by supplying profiling data to be merged at compile time) would be a shame.

So are multiple profiles supported, and how are they prioritized?

Sorry, I'm not sure I really understand your question. I'll try to answer as I understand it. For multiple profiles for the same program, user can specify which profile to use in the command line (go build -pgo=<profile>). If a program has different workloads, only the user would know what workloads to optimize for in a particular build. Or, if one wants to build a single binary that works reasonably well for different workloads, they can merge the profiles before the build.

For module developers, there is no reason not to think that they are actually the specialists on what performs or not, and not allowing them to "chip in" with knowledge (either by manual inline pragma hints or by supplying profiling data to be merged at compile time) would be a shame.

Module/library profiles are on our road map, and we definitely want to support it in the future. It is just that it still requires more thinking and designing, so not done in Go 1.20. Thanks for understanding.

Change https://go.dev/cl/453636 mentions this issue: doc/go1.20: add release notes for PGO

Change https://go.dev/cl/463684 mentions this issue: _content/doc: add PGO usage guide

A preview of PGO support will be available in Go 1.20 (to be released very soon). 🎉 The user guide is available here.

We have a few more problems to tackle before we're ready to call PGO generally available, which we're planning to work on for 1.21:

• cmd/go: support multiple main packages with -pgo=auto #58099
• Make -pgo=auto the default
• cmd/compile: reduce PGO profile processing overhead #58102
• cmd/compile: PGO compiler diagnostics #58153

Then the next priority is tackling the long list of further PGO-based optimizations.

Change https://go.dev/cl/464477 mentions this issue: _content/doc/go1.20: add link to PGO user guide

Change https://go.dev/cl/474236 mentions this issue: cmd/go: enable -pgo=auto by default

I've filed a new umbrella issue to track PGO optimization opportunities: #62463

I read the discussion of some optimizations that need the basic block counters (unrolling, pgo register allocation, basic block ordering), but currently I do not see any issues or PRs or discussion of this feature. Is there any proposal or plans for implementing it?

It's in the list of PGO optimization opportunities we'd like to pursue, but we don't yet have specific plans. We likely need discriminators in profiles (#59612) before we can do basic block-level PGO optimizations.