LGTM.

In D109860#3016016, @spupyrev wrote:

In D109860#3009910, @wmi wrote:

Thanks Sergey. That looks like a good work to improve the consistency of the profile. Have you checked whether the new algorithm can infer the missing parts based on equivalence relationship on the CFG? If it can, could you add a test for it?

Do you mind to elaborate more on this? What kind of a test would you like to see? (i may not be familiar with the terminology)

Thanks Sergey. That looks like a good work to improve the consistency of the profile. Have you checked whether the new algorithm can infer the missing parts based on equivalence relationship on the CFG? If it can, could you add a test for it?

LGTM.

In D109531#2993484, @hoy wrote:

In D109531#2993394, @wmi wrote:

In D109531#2992721, @hoy wrote:

In D109531#2992702, @wenlei wrote:

The change makes sense given instr PGO also happens for O0. But practically, if a file is being built with O0, do we care about its profile given we're not really optimizing it anyways? Functions from O0 modules are not supposed to be inlined into O1+ modules either.

We probably don't care about performance for O0 build. The change is for consistency, also makes the compiler happy which otherwise will complain about "Pseudo-probe-based profile requires SampleProfileProbePass" for O0 modules that don't have probes.

The complain message is emitted in SampleProfileLoader::doInitialization. llvm will not run SampleProfileLoader pass for O0 module. Why there is the complain?

Good question. It could happen in lto postlink which by default optimizes in -O2 mode. More specifically, with the following command, both cc1 and lld will run in default mode, which is -O0 for cc1 and -O2 for lld.

clang -flto 1.cpp -v -fuse-ld=lld

In D109531#2992721, @hoy wrote:

In D109531#2992702, @wenlei wrote:

The change makes sense given instr PGO also happens for O0. But practically, if a file is being built with O0, do we care about its profile given we're not really optimizing it anyways? Functions from O0 modules are not supposed to be inlined into O1+ modules either.

We probably don't care about performance for O0 build. The change is for consistency, also makes the compiler happy which otherwise will complain about "Pseudo-probe-based profile requires SampleProfileProbePass" for O0 modules that don't have probes.

LGTM.

LGTM.

LGTM.

LGTM.

LGTM.

LGTM, thanks.

In D107299#2955596, @hoy wrote:

In D107299#2955079, @wmi wrote:

Thanks Hongtao. The compile time result looks great. The patch is large. Is it possible to split it into smaller ones, SampleContext related change and SecCSNameTable related change for example?

Thanks for the suggestion. The separation may not be complete. The point is that the previous StringRef context is used in both reader/writer, and now we are changing it to be an ArrayRef which relies on an underlying array buffer (i.e., the CSName the reader builds up). Separating SecCSNameTable from this patch will still require the reader to build the underlying CSName table to bridge full string contexts in profile to ArrayRef contexts used elsewhere. Does this sound good to you?

Thanks Hongtao. The compile time result looks great. The patch is large. Is it possible to split it into smaller ones, SampleContext related change and SecCSNameTable related change for example?

Got a testcase and put it here: https://bugs.llvm.org/show_bug.cgi?id=51540

LGTM. Thanks.

LGTM.

LGTM.

In D107876#2939691, @hoy wrote:

In D107876#2939624, @wmi wrote:

Could you remind me the discriminator difference between debug info based AFDO and pseudo probe based AFDO? I forgot it. I am sure it is described in some patch but I havn't found it. Give me a pointer is good enough.

In short, unlike block pseudo probe, a callsite probe relies on the calliste discriminator to be tracked. This has a couple usage: 1. to track direct call and indirect callsite 2. to model inline contexts with a list of callsite probes.

A probe discriminator is treated as empty or null for AutoFDO since it has lowest three bits as "111".

Could you remind me the discriminator difference between debug info based AFDO and pseudo probe based AFDO? I forgot it. I am sure it is described in some patch but I havn't found it. Give me a pointer is good enough.

This extra pass turns to be positive in performance -- I'm seeing additional 0.6% - 0.8% improvement.

I tried the idea of using vector<Callsite> (Callsite is a struct containing function name and LineLocation) in SampleContext and changed the ProfileMap to be map<SampleContext, FunctionSamples> in the last two days. I believed the idea should work but I found the required change was much larger than I thought since ProfileMap has been used in many interfaces. I am worried that for the moment I cannot devote enough time to finish the whole change, so now I tend to use Hongtao's md5 patch and leave the further improvement to the future since the current patch has already significantly improved the build process and unblocked our experiment. We can always come back to revisit it. What is your opinion?

Thanks for the heads-up, Wei. Sounds good to stick with this patch for now, if you need more time to complete your idea which I think will get us a bigger win and be more aligned with the non-CS implementation. Will you continue working on that?

I tried the idea

In D107173#2921423, @wenlei wrote:

In D107173#2920842, @wmi wrote:

In D107173#2920602, @hoy wrote:

In D107173#2920521, @wmi wrote:

In D107173#2920321, @wenlei wrote:

Thanks for working on this.

Decomposing context strings into two levels is natural choice for deduplication. However, that means we would need to reconstruct strings in profile reader. So it's more like space vs speed thing. If compiler speed is the same, then storing decomposed strings in file and reconstruct them on profile loading might be a better choice as it's more compact and also more consistent with non-CS profile. Perhaps would be good to measure both.. Right now with md5 profile, plus some context trimming through cold threshold or pre-inliner tuning, we hope to bring e2e build time on par with AutoFDO for large workloads.

Right, D107173 in its own can already let me build our search benchmark in distributed way which I cannot do that before because of OOM issue, and that is really helpful. https://reviews.llvm.org/D107299 will still run into OOM in distributed build because we will still have the full context strings after profile reading, and that consumes excessive memory. For D107299, I believe that issue can also be solved after I add md5 support to it.

Like wenlei said, decomposing context strings can give us more compact profile (deduplicating: 418M vs md5: 1.8G for the profile collected from our search test), but reconstructing takes more time (2x). I am thinking about whether reconstructing the context string is necessary since the context represented in ContextTrieNode is also decomposed into multiple levels?

By the way, the context reconstructing time may also be reduced if D107299 can be coupled with md5.

@wmi Thanks for sharing your change and the numbers! And thanks for trying my implementation. Interested have you seen build time improvement with it?

I didn't compare it with the case without md5 because I cannot build it successfully in our build system without md5. I tried building it locally but it took one week to finish.

I tried dumping the profile to text format and the md5 version took about a half time to finish compared with the case without md5, so that is an indication we should see build time improvement with it.

Curious were you trying probe-based CS profile or line-based CS profile?

In D107173#2920602, @hoy wrote:

In D107173#2920521, @wmi wrote:

In D107173#2920321, @wenlei wrote:

Thanks for working on this.

Decomposing context strings into two levels is natural choice for deduplication. However, that means we would need to reconstruct strings in profile reader. So it's more like space vs speed thing. If compiler speed is the same, then storing decomposed strings in file and reconstruct them on profile loading might be a better choice as it's more compact and also more consistent with non-CS profile. Perhaps would be good to measure both.. Right now with md5 profile, plus some context trimming through cold threshold or pre-inliner tuning, we hope to bring e2e build time on par with AutoFDO for large workloads.

Right, D107173 in its own can already let me build our search benchmark in distributed way which I cannot do that before because of OOM issue, and that is really helpful. https://reviews.llvm.org/D107299 will still run into OOM in distributed build because we will still have the full context strings after profile reading, and that consumes excessive memory. For D107299, I believe that issue can also be solved after I add md5 support to it.

Like wenlei said, decomposing context strings can give us more compact profile (deduplicating: 418M vs md5: 1.8G for the profile collected from our search test), but reconstructing takes more time (2x). I am thinking about whether reconstructing the context string is necessary since the context represented in ContextTrieNode is also decomposed into multiple levels?

By the way, the context reconstructing time may also be reduced if D107299 can be coupled with md5.

@wmi Thanks for sharing your change and the numbers! And thanks for trying my implementation. Interested have you seen build time improvement with it?

In D107173#2920321, @wenlei wrote:

Thanks for working on this.

Decomposing context strings into two levels is natural choice for deduplication. However, that means we would need to reconstruct strings in profile reader. So it's more like space vs speed thing. If compiler speed is the same, then storing decomposed strings in file and reconstruct them on profile loading might be a better choice as it's more compact and also more consistent with non-CS profile. Perhaps would be good to measure both.. Right now with md5 profile, plus some context trimming through cold threshold or pre-inliner tuning, we hope to bring e2e build time on par with AutoFDO for large workloads.

In D107173#2917462, @hoy wrote:

In D107173#2917382, @wmi wrote:

Thanks for the work to reduce the CS profile size! It is something we really need.

I am also trying it in a slightly different way.
For "[main:3.1 @ _Z5funcBi]:120:19" in your example, I split the context string into multiple tuples of {string, line, discriminator}:
{main, 3, 1} {_Z5funcBi, 0, 0}, and for each name in the tuple, we will only save the index to the name table. So we will not have new entry in the name table for different contexts.

In this way, we won't have any increase in the name table section compared with non-CS profile even when we uses string based name. We do need to have a new section called CSNameTable to store the tuples. When we read the section, we will recontruct the context string from the tuple and the rest of the profile handling will have no change.

In this way, on top of it we can also apply md5 to the nametable using existing md5 mechanism, to further compress the name table section.

I havn't finished the implemention, but I am close to it. It will be good to discuss how we converge the effort here.

@wmi good to know you are also working on improving the efficiency. Thanks!
The string split design sounds interesting. I'm curious to know more about it, like how context strings are split in the profile, and how they are constructed and represented in the compiler.

Thanks for the work to reduce the CS profile size! It is something we really need.

LGTM.

Good catch.

We saw a performance regression caused by this change and filed a bug here: https://bugs.llvm.org/show_bug.cgi?id=51149

LGTM.

-funique-internal-linkage-names is not enabled by default. Will -fpseudo-probe-for-profiling implicitly enable -funique-internal-linkage-names?

Thanks Hongtao, I will try it.

In "6. Be consistent with non-CS dwarf line number based profile", if you can mention how the compiler treat missing line number and missing pseudo in the description as a record, that will be helpful.

In D104129#2821201, @wenlei wrote:

In D104129#2821189, @hoy wrote:

In D104129#2821164, @wenlei wrote:

Be consistent with dwarf line number based profile.

This is not accurate, see earlier comments. What i meant was not about "non-probe profile -> dwarf line number profile".

Otherwise lgtm. Thanks.

It should be consistent with non-CS dwarf-based profile. CS dwarf-based profile doesn't have either zero or dangling reported, likely needs a fix. Is that what you meant?

Non-cs dwarf-based profile normally doesn't have zero counts in the profile. Any count below a certain threshold is omitted in the profile to save size. This is the default behavior for our production usage (I believe for google as well). This is why the current change that needs explicit zero is not consistent with afdo.

LGTM.

LGTM.

LGTM.

LGTM.

LGTM.

LGTM.

LGTM.

If we target AutoFDO as well, would be good to mention the impact on AutoFDO too.

I haven't tested for non-CS case. In theory it should help there but with a less-than-ideal counts quality, the change may not help in practice.

LGTM.

Thanks for splitting the patches.

Can you split the changes under ProfileData into a separate patch?

LGTM.

LGTM, thanks.

LGTM, thanks.

LGTM.

LGTM.

Address Teresa's comment.

LGTM.

LGTM.