[MC] Fix quadratic behavior in addPendingLabel

[aganea]

Summary

While investigating build-time regressions from Clang 9 to Clang 10, I discovered this:

Topmost functions in Clang 10

Line #	Process Name	Module	Function	Count	Weight (in view) (ms)	% Weight
1	clang-cl.exe			9813998	9 816 190.696800	74.94
2		clang-cl.exe		8054456	8 054 249.395800	61.49
3			llvm::MCObjectStreamer::addPendingLabel	134506	134 298.342000	1.03
4			memcmp	73094	73 097.908200	0.56
5			llvm::StringMapImpl::LookupBucketFor	72037	72 094.650600	0.55
6			llvm::FoldingSetBase::FindNodeOrInsertPos	71757	71 766.338400	0.55
7			clang::DiagnosticsEngine::DiagStateMap::getFile	68787	68 821.673400	0.53
8			llvm::SmallPtrSetImpl<const llvm::BasicBlock *>::insert	61700	61 694.511000	0.47
9			llvm::SimpleBitstreamCursor::Read	60287	60 286.848300	0.46
10			llvm::ValueHandleBase::AddToUseList	54104	54 100.684600	0.41
11			llvm::Use::getUser	51381	51 376.805000	0.39
12			llvm::removeUnreachableBlocks	48469	48 466.197100	0.37
13			llvm::PMTopLevelManager::findAnalysisPass	46510	46 503.354600	0.36
14			llvm::PMDataManager::removeNotPreservedAnalysis	44020	44 014.352500	0.34
15			llvm::SimpleBitstreamCursor::ReadVBR64	42468	42 471.558800	0.32
16			computeKnownBitsFromOperator	39548	39 548.097900	0.30
17			llvm::FoldingSetBase::GrowBucketCount	38972	38 967.456800	0.30
18			llvm::PMDataManager::initializeAnalysisImpl	38459	38 455.356500	0.29
19			llvm::AttributeList::hasAttribute	38442	38 439.664900	0.29
20			clang::Decl::castFromDeclContext	35533	35 540.141800	0.27

Then, digging a bit:

Most samples are in just two instructions. Taking a look at the generated assembly:

00000001412571F0: 4C 39 2A           cmp         qword ptr [rdx],r13
00000001412571F3: 74 39              je          000000014125722E
00000001412571F5: 48 83 C2 08        add         rdx,8
00000001412571F9: 48 83 C3 F8        add         rbx,0FFFFFFFFFFFFFFF8h
00000001412571FD: 75 F1              jne         00000001412571F0

That is the inner loop for the std::find in MCObjectStream.cpp, L62.

I've added a counter at beginning of the function, and one to count the number of iterations in this loop:

g_Calls1 -      576,427
g_Walked -	219,731,421

Which solves to N ^ 1.45.

This issue was introduced in D71368.

The proposed fix simply replaces the SmallVector by a SmallSetVector.

Differential before/after:

[MaskRay]

Thanks for noticing this and fixing it! I am wondering why PendingLabels can be large. Do you happen to note which pattern causes a large number of PendingLabels elements and causes the slowdown?

llvm/include/llvm/MC/MCObjectStreamer.h

41

Add space, i.e. MCSection *

Have you tried SmallPtrSet<MCSection *>? Does it perform better?

[aganea]

Thanks for taking a look @MaskRay !

This seems related to inlining. We are compiling using unity/blobs/jumbo files, can this explain the behavior seen?

Line #, Process, Function, Stack - (Callers of clang-cl.exe!llvm::MCObjectStreamer::addPendingLabel), Count, Weight (in view) (ms), % Weight
 4, , llvm::MCObjectStreamer::addPendingLabel, , 3132, 3,132.066900, 0.25
 5, , , clang-cl.exe!llvm::MCObjectStreamer::addPendingLabel, 3129, 3,129.079500, 0.25
 6, , ,   |- clang-cl.exe!llvm::CodeViewDebug::emitLocalVariable, 1686, 1,685.979300, 0.13
 7, , ,   |    clang-cl.exe!llvm::CodeViewDebug::emitLocalVariableList, 1686, 1,685.979300, 0.13
 8, , ,   |    |- clang-cl.exe!llvm::CodeViewDebug::emitInlinedCallSite, 1494, 1,494.012700, 0.12
 9, , ,   |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitInlinedCallSite, 1166, 1,166.030500, 0.09
10, , ,   |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitInlinedCallSite, 833, 833.003600, 0.07
11, , ,   |    |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitInlinedCallSite, 567, 567.000200, 0.05
12, , ,   |    |    |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitInlinedCallSite, 345, 345.022900, 0.03
13, , ,   |    |    |    |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitInlinedCallSite, 214, 214.008400, 0.02
14, , ,   |    |    |    |    |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForFunction, 143, 143.023800, 0.01
15, , ,   |    |    |    |    |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitInlinedCallSite, 71, 70.984600, 0.01
16, , ,   |    |    |    |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForFunction, 131, 131.014500, 0.01
17, , ,   |    |    |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForFunction, 222, 221.977300, 0.02
18, , ,   |    |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForFunction, 266, 266.003400, 0.02
19, , ,   |    |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForFunction, 333, 333.026900, 0.03
20, , ,   |    |    |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForFunction, 328, 327.982200, 0.03
21, , ,   |    |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForFunction, 173, 172.972900, 0.01
22, , ,   |    |- clang-cl.exe!llvm::CodeViewDebug::emitLexicalBlock, 19, 18.993700, 0.00
23, , ,   |- clang-cl.exe!llvm::CodeViewDebug::emitInlinedCallSite, 811, 811.067000, 0.06
24, , ,   |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForFunction, 150, 149.963500, 0.01
25, , ,   |- clang-cl.exe!llvm::DebugHandlerBase::endInstruction, 98, 97.998700, 0.01
26, , ,   |- clang-cl.exe!llvm::MCObjectStreamer::emitCVLocDirective, 84, 83.992700, 0.01
27, , ,   |- clang-cl.exe!llvm::AsmPrinter::emitFunctionEntryLabel, 54, 54.009600, 0.00
28, , ,   |- clang-cl.exe!llvm::MCObjectStreamer::emitCFILabel, 39, 39.018600, 0.00
29, , ,   |- clang-cl.exe!llvm::AsmPrinter::emitBasicBlockStart, 37, 37.036400, 0.00
30, , ,   |- clang-cl.exe!llvm::AsmPrinter::emitFunctionHeader, 31, 31.037600, 0.00
31, , ,   |- clang-cl.exe!EmitUnwindInfo, 28, 28.029200, 0.00
32, , ,   |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForUDTs, 24, 23.999000, 0.00
33, , ,   |- clang-cl.exe!llvm::AsmPrinter::emitGlobalVariable, 24, 23.991300, 0.00
34, , ,   |- clang-cl.exe!llvm::CodeViewDebug::emitLexicalBlock, 17, 16.988900, 0.00
35, , ,   |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForGlobal, 14, 13.999800, 0.00
36, , ,   |- clang-cl.exe!llvm::WinException::beginFunclet, 14, 13.969700, 0.00
37, , ,   |- clang-cl.exe!llvm::AsmPrinter::emitFunctionBody, 6, 6.000600, 0.00
38, , ,   |- clang-cl.exe!llvm::WinException::emitCXXFrameHandler3Table, 6, 5.998700, 0.00
39, , ,   |- clang-cl.exe!llvm::CodeViewDebug::emitDebugInfoForThunk, 5, 4.999600, 0.00
40, , ,   |- clang-cl.exe!llvm::DebugHandlerBase::beginInstruction, 1, 0.999300, 0.00

[aganea]

Using a SmallPtrSet. The performance is the same as SmallDenseSet.

Shouldn't they be functionally equivalent? I know SmallPtrSet does a linear search when the set is 'small' but that shouldn't matter, the cache effects dominate.

[MaskRay]

LGTM.

[aganea]

Thanks!

[mtrent]

Thanks for finding this!

[MaskRay]

I always use arcanist to upload a differential and that sets up everything correctly https://llvm.org/docs/GettingStarted.html#sending-patches

I use a shell function to drop unneeded Phabricator tags (Reviewers: Subscribers: Tags: and the substring Summary :).

arcfilter () {
        arc amend
        git log -1 --pretty=%B | awk '/Reviewers:|Subscribers:/{p=1} /Reviewed By:|Differential Revision:/{p=0} !p && !/^Summary:$/ {sub(/^Summary: /,
"");print}' | git commit --amend -F -
}

It was suggested that these tags can be removed on the Phabricator server side https://lists.llvm.org/pipermail/llvm-dev/2020-April/140808.html

[efriedma]

Iterating over a SmallPrtSet is non-deterministic; please use SmallSetVector.

[MaskRay]

In D78775#2002596, @efriedma wrote:

Iterating over a SmallPrtSet is non-deterministic; please use SmallSetVector.

Thanks for noting this. Forgot it.

[aganea]

As suggested by @efriedma, PTAL.

[MaskRay]

Looks great!

[skan]

LGTM (with one comment)

llvm/include/llvm/MC/MCObjectStreamer.h

41

Update this in description.

The proposed fix simply replaces the SmallVector by a (Small)DenseSet SmallPtrSet.

llvm/include/llvm/MC/MCObjectStreamer.h

 /// to that file format or custom semantics expected by the object writer
 /// implementation.
 class MCObjectStreamer : public MCStreamer {
   std::unique_ptr<MCAssembler> Assembler;
   MCSection::iterator CurInsertionPoint;
   bool EmitEHFrame;
   bool EmitDebugFrame;
   SmallVector<MCSymbol *, 2> PendingLabels;
-  SmallVector<MCSection*, 2> PendingLabelSections;
+  SmallPtrSet<MCSection *, 4> PendingLabelSections;
   unsigned CurSubsectionIdx;
   struct PendingMCFixup {
     const MCSymbol *Sym;
     MCFixup Fixup;
     MCDataFragment *DF;
     PendingMCFixup(const MCSymbol *McSym, MCDataFragment *F, MCFixup McFixup)
         : Sym(McSym), Fixup(McFixup), DF(F) {}
   };

llvm/lib/MC/MCObjectStreamer.cpp

if (!PendingLabels.empty()) {
         CurSection->addPendingLabel(Sym);
       PendingLabels.clear();
     }
 
     // Add this label to the current Section / Subsection.
     CurSection->addPendingLabel(S, CurSubsectionIdx);
 
     // Add this Section to the list of PendingLabelSections.
-    auto SecIt = std::find(PendingLabelSections.begin(),
-                           PendingLabelSections.end(), CurSection);
-    if (SecIt == PendingLabelSections.end())
-      PendingLabelSections.push_back(CurSection);
-  }
-  else
+    PendingLabelSections.insert(CurSection);
+  } else
     // There is no Section / Subsection for this label yet.
     PendingLabels.push_back(S);
 }
 
 void MCObjectStreamer::flushPendingLabels(MCFragment *F, uint64_t FOffset) {
   MCSection *CurSection = getCurrentSectionOnly();
   if (!CurSection) {
     assert(PendingLabels.empty());