This is an archive of the discontinued LLVM Phabricator instance.

[llvm-profdata] Implement llvm-profdata overlap for sample profiles
ClosedPublic

Authored by weihe on Jul 14 2020, 10:59 PM.

Details

Summary

Implemented the llvm-profdata overlap feature for sample profiles. It reports weighted similarity and unweighted overlap metrics at program and function level for two input profiles. Similarity metrics are symmetric with regards to the order of two input profiles. By default, the tool only reports program-level summary. Users can look into function-level details via additional options --function, --similarity-cutoff, and --value-cutoff.

The similarity metrics are designed as follows:

  • Program-level summary
    • Whole program profile similarity is an aggregate over function-level similarity FS: PS = sum(FS(A) * avg_weight(A)) for all function A.
    • Whole program sample overlap: PSO = common_samples / total_samples.
    • Function overlap: FO = #common_function / #total_function.
    • Hot-function overlap: HFO = #common_hot_function / #total_hot_function.
    • Hot-block overlap: HBO = #common_hot_block / #total_hot_block.
  • Function-level details
    • Function-level similarity is an aggregate over line/block-level similarities BS of all sample lines/blocks in the function, weighted by the closeness of the function's weights in two profiles: FS = sum(BS(i)) * (1 - weight_distance(A)).
    • Function-level sample overlap: FSO = common_samples / total_samples for samples in the function.

Diff Detail

Event Timeline

weihe created this revision.Jul 14 2020, 10:59 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 14 2020, 10:59 PM
weihe edited the summary of this revision. (Show Details)Jul 14 2020, 11:25 PM
weihe edited the summary of this revision. (Show Details)Jul 15 2020, 6:58 AM
weihe updated this revision to Diff 278180.Jul 15 2020, 7:19 AM

Corrected two typos in comment.

hoyFB added inline comments.Jul 17 2020, 12:19 AM
llvm/tools/llvm-profdata/llvm-profdata.cpp
1058

function-level similarity?

1248

I think you want just const auto Match = .... The return value will be returned by reference if it is large.

1250

May just increase HotFuncOverlap.UnionCount before continue, instead of erasing every matched function from TestHotFunc? like

for (const auto &F : TestHotFunc) {
    if (BaseHotFunc.count(F.first()))
       ++HotFuncOverlap.OverlapCount;
    else
       ++HotFuncOverlap.UnionCount;
}
weihe updated this revision to Diff 278969.Jul 17 2020, 10:19 PM
weihe marked an inline comment as done.

Refactored computeHotFuncOverlap() and renamed computeSampleFunctionOverlap() to computeSampleFunctionInternalOverlap()

weihe marked 2 inline comments as done.Jul 17 2020, 10:25 PM
weihe added inline comments.
llvm/tools/llvm-profdata/llvm-profdata.cpp
1058

Thank you for the comment! This is not exactly the function-level similarity we report in the tool, but an intermediate result towards it. The formula of function-level similarity is given at line 882.

I renamed this function to computeSampleFunctionInternalOverlap() and moved it to a private member to reduce confusions.

1248

Thank you for the suggestion! I've changed the code accordingly.

1250

This suggestion is really good! The refactored code is much cleaner. Thank you very much!

@wmi We'd like to hear about your input on this. Thanks!

wmi added a comment.Jul 25 2020, 11:39 AM

Thanks for the work. It is a very useful feature.

llvm/tools/llvm-profdata/llvm-profdata.cpp
1166–1167

Can we make the similarity within range 0~1 to be consistent with Block and profile similarity? It is more natural to reason the similarity with range 0~1.

1268–1274

Seemly a lot of complexity of the function comes from lock step iteration of the maps from two profiles at the same time. Could you extract the lock step iteration logic into a separate class? This way we don't have to deal with the logic multiple times in iterating BodySampleMap, CallsiteSamplesMap and FunctionSamplesMap.

1293–1298

updateForUnmatchedBlock is a special case of the block above. We may be able to share the code.

weihe updated this revision to Diff 281468.Jul 28 2020, 9:52 PM

Extracted lock step iteration logic into class MatchStep and revised code according to other suggestions.

weihe added inline comments.Jul 28 2020, 9:58 PM
llvm/tools/llvm-profdata/llvm-profdata.cpp
1166–1167

Thank you for the suggestion! I have changed the function computeSampleFunctionInternalOverlap() to return a double in range 0~1.

1268–1274

I have extracted the logic of lock step iteration to class MatchStep. This is a great suggestion. Thank you very much!

1293–1298

Thank you for the suggestion! I combined this code with updateForUnmatchedBlock() into a new function updateOverlapStatsForFunction().

wmi accepted this revision.Aug 1 2020, 10:14 AM

Thanks. Another suggestion about comment. Other than that, LGTM.

llvm/tools/llvm-profdata/llvm-profdata.cpp
1253–1254

Both weightFuncSimilarity and weightByImportance considers the weight of the function in the profile, so at the beginning I felt confused what are their difference. I find out the difference is weightFuncSimilarity absorbs the weight difference into the similarity so the similarity is still in the range of 0~1, while weightByImportance multiplies the similarity by weight ratio of the function in the profile (the average ratio of the two profiles), so the aggregate similarity of all the functions in the profiles will be in the range of 0~1. Please correct me if I am wrong. But it is better to make the intention of these two functions more clear in the comments.

This revision is now accepted and ready to land.Aug 1 2020, 10:14 AM
weihe updated this revision to Diff 283819.Aug 6 2020, 11:31 PM

Grouped previous weightFuncSimilarity() and computeSampleFunctionInternalOverlap() to computeSampleFunctionOverlap() and added comments for readability.

weihe added inline comments.Aug 6 2020, 11:45 PM
llvm/tools/llvm-profdata/llvm-profdata.cpp
1253–1254

Yes, that's right! In fact, the previous weightFuncSimilarity() is part of the computation of "function-level similarity", whereas weightByImportance() is part of the computation that aggregates "function-level similarity" to "profile-level similarity". So the two functions use weights in slightly different ways.

I also realized these two functions may be confusing, so I grouped the previous weightFuncSimilarity() (renamed as weightForFuncSimilarity()) and computeSampleFunctionInternalOverlap() into one computeSampleFunctionOverlap() function. In addition, I added comments to weightForFuncSimilarity() and weightByImportance() to explain the different purpose of these functions.

Thank you for pointing this out!

hoyFB added inline comments.Aug 7 2020, 11:00 AM
llvm/tools/llvm-profdata/llvm-profdata.cpp
1011–1017

Can you please decorate these functions with const?

hoyFB accepted this revision.Aug 7 2020, 11:00 AM
weihe updated this revision to Diff 284144.EditedAug 8 2020, 2:46 PM

Added const keyword to member functions of MatchStep.

weihe added inline comments.Aug 8 2020, 2:47 PM
llvm/tools/llvm-profdata/llvm-profdata.cpp
1011–1017

Thank you for this suggestion! I have added const keyword to the member functions.

MaskRay added a subscriber: MaskRay.Aug 8 2020, 3:18 PM
MaskRay added inline comments.
llvm/test/tools/llvm-profdata/sample-overlap.test
2

You may consider a new test utility split-file, which can group multiple auxiliary files. D83834

wenlei accepted this revision.Aug 8 2020, 5:46 PM

Thank you for working on this during internship, @weihe! The extra tweaks here on top of our internal version look good to me as well. The test failure doesn't seem related, I will rebase and land this on your behalf.

llvm/test/tools/llvm-profdata/sample-overlap.test
2

Thanks for the pointer - I wasn't aware of the recently added utility. That will work, but in this particular case, I think it's still better to keep profile inputs separate so they're semantically legal afdo profile by themselves.

This revision was landed with ongoing or failed builds.Aug 8 2020, 6:02 PM
This revision was automatically updated to reflect the committed changes.
aganea added a subscriber: aganea.EditedSep 1 2021, 1:50 PM

Hello @wenlei, @weihe,

llvm/tools/llvm-profdata/llvm-profdata.cpp
1599

Match is invalidated after this line, so it cannot be compared with BaseFuncProf.end() afterwards at L1607 and L1609.

In a Debug build on Windows/MSVC this asserts in MS-STL:

The following tests fail because of this:

LLVM :: tools/llvm-profdata/compact-sample.proftext
LLVM :: tools/llvm-profdata/sample-overlap.test

The following patch seems to fi the issue, but I thought I'll let you decide what to do?

diff --git a/llvm/tools/llvm-profdata/llvm-profdata.cpp b/llvm/tools/llvm-profdata/llvm-profdata.cpp
index 488dc8fa4317..38d9cb9461bb 100644
--- a/llvm/tools/llvm-profdata/llvm-profdata.cpp
+++ b/llvm/tools/llvm-profdata/llvm-profdata.cpp
@@ -1633,6 +1633,7 @@ void SampleOverlapAggregator::computeSampleProfileOverlap(raw_fd_ostream &OS) {
            "except inlinees");
     FuncOverlap.TestSample = TestStats[FuncOverlap.TestName].SampleSum;

+    bool Matched = false;
     const auto Match = BaseFuncProf.find(FuncOverlap.TestName);
     if (Match == BaseFuncProf.end()) {
       const FuncSampleStats &FuncStats = TestStats[FuncOverlap.TestName];
@@ -1677,6 +1678,8 @@ void SampleOverlapAggregator::computeSampleProfileOverlap(raw_fd_ostream &OS) {
       // Remove matched base functions for later reporting functions not found
       // in test profile.
       BaseFuncProf.erase(Match);
+
+      Matched = true;
     }

     // Print function-level similarity information if specified by options.
@@ -1684,9 +1687,8 @@ void SampleOverlapAggregator::computeSampleProfileOverlap(raw_fd_ostream &OS) {
            "TestStats should have records for all functions in test profile "
            "except inlinees");
     if (TestStats[FuncOverlap.TestName].MaxSample >= FuncFilter.ValueCutoff ||
-        (Match != BaseFuncProf.end() &&
-         FuncOverlap.Similarity < LowSimilarityThreshold) ||
-        (Match != BaseFuncProf.end() && !FuncFilter.NameFilter.empty() &&
+        (Matched && FuncOverlap.Similarity < LowSimilarityThreshold) ||
+        (Matched && !FuncFilter.NameFilter.empty() &&
          FuncOverlap.BaseName.toString().find(FuncFilter.NameFilter) !=
              std::string::npos)) {
       assert(ProfOverlap.BaseSample > 0 &&
wenlei added inline comments.Sep 1 2021, 2:31 PM
llvm/tools/llvm-profdata/llvm-profdata.cpp
1599

Good catch, thanks! I will fix it as you suggested.