[LLD] [COFF] Avoid O(n^2) accesses into PartialSections

[mstorsjo]

Summary

For MinGW, unique partial sections are much more common, e.g. comdat functions get sections named e.g. text$symbol.

A moderate sized example of this contains over 200K Chunks which create 174K unique PartialSections. Prior to SVN r352928 (D57574), linking this took around 1,5 seconds for me, while it afterwards takes around 13 minutes.

The std::find_if in findPartialSection will do a linear scan of the whole container until a match is found. To use something like binary_search or the std::set container's own methods, we'd need to already have a PartialSection*.

Reinstate a proper map instead of having a set with a custom sorting comparator.

A reproduction testcase can be found at https://martin.st/temp/vlc-qt-plugin-repro.zip.

[aganea]

Thanks for fixing this Martin. My mistake, I was annoyed by the fact that the key was sharing its data with the value, went to change the std::map into a std::set, then I machinally changed the search to find_if.
Is there any way to subsequently add a stress test for this? (ie. the test would fail if lld-link takes >5 sec)

COFF/Writer.cpp

1778

What about PartialSection *&PSec = PartialSections[{Name, OutChars}]; ?

1787

return PartialSections[{Name, OutChars}]; ?

[mstorsjo]

In D57666#1382661, @aganea wrote:

Thanks for fixing this Martin. My mistake, I was annoyed by the fact that the key was sharing its data with the value, went to change the std::map into a std::set, then I machinally changed the search to find_if.

Yeah, it's a bit inelegant to have it duplicated. I considered removing it from the value part here as well, but that would be more or less a revert of your commit I presume.

Is there any way to subsequently add a stress test for this? (ie. the test would fail if lld-link takes >5 sec)

Not sure how well it fits into the automated tests, as the exact threshold for what is too long and the input size where it becomes noticeable varies per machine.

I noticed it in a setup where I built code with ulimit -t 120 (to catch cases where compiler bugs makes it loop infinitely), and even then, the cases I normally build still linked fast - I only noticed it with a larger than usual input.

COFF/Writer.cpp

1778

Sure, I can do that. (I'm a little unfamiliar with the exact dos and don'ts about these, to me, "new" C++11 syntax additions.)

[mstorsjo]

Removed needless declarations of the key as variables.

[aganea]

! In D57666#1382703, @mstorsjo wrote:
Yeah, it's a bit inelegant to have it duplicated. I considered removing it from the value part here as well, but that would be more or less a revert of your commit I presume.

No, I would need the full value to back reference from OutputSection (see D54802)

COFF/Writer.cpp

237

On a second thought, and if we wanted to be optimal, I was wondering if we shouldn't be using a llvm::DenseSet here instead. std::map isn't known to scale particularly well with many elements, and you're at the implementation's mercy. At least the behavior will be more consistent with an internal structure.

I did use a DenseMap initially, but that requires more plumbing, because you need to retain the insertion order ( for later, when emitting data into the PDB). I did not see the advantage at the time, given that MSVC does not generate that many sections, but in your case, it matters. What do you think?

[aganea]

COFF/Writer.cpp

237

Correction: it is NOT the insertion order that matters; it is the map that needs to be enumerated in a sorted order on PDB emission.

[mstorsjo]

In D57666#1383144, @aganea wrote:

! In D57666#1382703, @mstorsjo wrote:
Yeah, it's a bit inelegant to have it duplicated. I considered removing it from the value part here as well, but that would be more or less a revert of your commit I presume.

No, I would need the full value to back reference from OutputSection (see D54802)

Hmm, I don't really see where PartialSection or the set/map PartialSections are used within that patch at all?

But even then, if it isn't part of the PartialSection object itself, but only part of the key in the map, can't you get it while iterating over it, like this?

for (auto It : PartialSections) {
  const PartialSectionKey &Key = It.first;
  PartialSection *PSec = It.second;
  use(Key.Name, Key.Characteristics);

COFF/Writer.cpp

237

I think using std::map is fine - that's what was used before anyway (so this is not worse than it was before), and it is fast enough for this case. As you say, std::map/set has the upside that they are maintained sorted at all times - that's also needed in Writer when creating the OutputSections.

[rnk]

COFF/Writer.cpp

237

Hm, yes, if the number of unique keys here is large, then we might want a different data structure. For mingw, this table has practically speaking O(#symbols) entries in it. Let's leave that as a follow-up, though. Going back to std::map seems OK for now.

1787

When looking for keys not in the map, this has the side effect of creating a new (null) map entry. I think the usual .find() / != .end() dance is probably what we want instead.

[aganea]

In D57666#1383852, @mstorsjo wrote:

Hmm, I don't really see where PartialSection or the set/map PartialSections are used within that patch at all?

Sorry about the confusion. It was callled InputSection in D54802, see lld/trunk/COFF/Writer.h in that patch.

But even then, if it isn't part of the PartialSection object itself, but only part of the key in the map, can't you get it while iterating over it, like this?

Not for iterating, but for referencing a PartialSection from an OutputSection for later usage, see lld/trunk/COFF/PDB.cpp, L1509.

[mstorsjo]

In D57666#1383871, @aganea wrote:

In D57666#1383852, @mstorsjo wrote:

Hmm, I don't really see where PartialSection or the set/map PartialSections are used within that patch at all?

Sorry about the confusion. It was callled InputSection in D54802, see lld/trunk/COFF/Writer.h in that patch.

But even then, if it isn't part of the PartialSection object itself, but only part of the key in the map, can't you get it while iterating over it, like this?

Not for iterating, but for referencing a PartialSection from an OutputSection for later usage, see lld/trunk/COFF/PDB.cpp, L1509.

Oh, I see. Yes, then the approach of this patch, duplicating it in the key and within the value, seems reasonable.

COFF/Writer.cpp

1787

Oh, right, will fix.

[mstorsjo]

Using find/ != end to avoid creating entries for sections that aren't found.

[thakis]

(No opinion on the patch, but since you mention time-before and time-after-D57574 in the patch description, maybe also mention time-after-this-patch.)

[mstorsjo]

In D57666#1384336, @thakis wrote:

(No opinion on the patch, but since you mention time-before and time-after-D57574 in the patch description, maybe also mention time-after-this-patch.)

Ah, yes, will do. (It's essentially the same as it was before.)

COFF/Writer.cpp

public:
   }
 
   mutable codeview::DebugInfo *BuildId = nullptr;
 };
 
 // PartialSection represents a group of chunks that contribute to an
 // OutputSection. Collating a collection of PartialSections of same name and
 // characteristics constitutes the OutputSection.
-class PartialSection {
+class PartialSectionKey {
 public:
-  PartialSection(StringRef N, uint32_t Chars)
-      : Name(N), Characteristics(Chars) {}
   StringRef Name;
   unsigned Characteristics;
-  std::vector<Chunk *> Chunks;
 
-  bool operator<(const PartialSection &Other) const {
+  bool operator<(const PartialSectionKey &Other) const {
     int C = Name.compare(Other.Name);
     if (C == 1)
       return false;
     if (C == 0)
       return Characteristics < Other.Characteristics;
     return true;
   }
 };
 
-struct PartialLess {
-  bool operator()(PartialSection *L, PartialSection *R) const {
-    return *L < *R;
-  }
+class PartialSection {
+public:
+  PartialSection(StringRef N, uint32_t Chars)
+      : Name(N), Characteristics(Chars) {}
+  StringRef Name;
+  unsigned Characteristics;
+  std::vector<Chunk *> Chunks;
 };
 
 // The writer writes a SymbolTable result to a file.
 class Writer {
 public:
   Writer() : Buffer(errorHandler().OutputBuffer) {}
   void run();
 
private:
 
   OutputSection *findSection(StringRef Name);
   void addBaserels();
   void addBaserelBlocks(std::vector<Baserel> &V);
 
   uint32_t getSizeOfInitializedData();
 
   std::unique_ptr<FileOutputBuffer> &Buffer;
-  std::set<PartialSection *, PartialLess> PartialSections;
+  std::map<PartialSectionKey, PartialSection *> PartialSections;
   std::vector<OutputSection *> OutputSections;
   std::vector<char> Strtab;
   std::vector<llvm::object::coff_symbol16> OutputSymtab;
   IdataContents Idata;
   Chunk *ImportTableStart = nullptr;
   uint64_t ImportTableSize = 0;
   Chunk *IATStart = nullptr;
   uint64_t IATSize = 0;

 // be formed correctly, the section chunks within each .idata$* section need
 // to be grouped by library, and sorted alphabetically within each library
 // (which makes sure the header comes first and the trailer last).
 bool Writer::fixGnuImportChunks() {
   uint32_t RDATA = IMAGE_SCN_CNT_INITIALIZED_DATA | IMAGE_SCN_MEM_READ;
 
   // Make sure all .idata$* section chunks are mapped as RDATA in order to
   // be sorted into the same sections as our own synthesized .idata chunks.
-  for (PartialSection *PSec : PartialSections) {
+  for (auto It : PartialSections) {
+    PartialSection *PSec = It.second;
     if (!PSec->Name.startswith(".idata"))
       continue;
     if (PSec->Characteristics == RDATA)
       continue;
     PartialSection *RDataSec = createPartialSection(PSec->Name, RDATA);
     RDataSec->Chunks.insert(RDataSec->Chunks.end(), PSec->Chunks.begin(),
                             PSec->Chunks.end());
     PSec->Chunks.clear();
   }
 
   bool HasIdata = false;
   // Sort all .idata$* chunks, grouping chunks from the same library,
   // with alphabetical ordering of the object fils within a library.
-  for (PartialSection *PSec : PartialSections) {
+  for (auto It : PartialSections) {
+    PartialSection *PSec = It.second;
     if (!PSec->Name.startswith(".idata"))
       continue;
 
     std::vector<Chunk *> &Chunks = PSec->Chunks;
     if (!Chunks.empty())
       HasIdata = true;
     std::stable_sort(Chunks.begin(), Chunks.end(), [&](Chunk *S, Chunk *T) {
       SectionChunk *SC1 = dyn_cast_or_null<SectionChunk>(S);
void Writer::createSections() {
   if (!Idata.empty())
     HasIdata = true;
 
   if (HasIdata)
     addSyntheticIdata();
 
   // Process an /order option.
   if (!Config->Order.empty())
-    for (PartialSection *PSec : PartialSections)
-      sortBySectionOrder(PSec->Chunks);
+    for (auto It : PartialSections)
+      sortBySectionOrder(It.second->Chunks);
 
   if (HasIdata)
     locateImportTables();
 
   // Then create an OutputSection for each section.
   // '$' and all following characters in input section names are
   // discarded when determining output section. So, .text$foo
   // contributes to .text, for example. See PE/COFF spec 3.2.
-  for (PartialSection *PSec : PartialSections) {
+  for (auto It : PartialSections) {
+    PartialSection *PSec = It.second;
     StringRef Name = getOutputSectionName(PSec->Name);
     uint32_t OutChars = PSec->Characteristics;
 
     if (Name == ".CRT") {
       // In link.exe, there is a special case for the I386 target where .CRT
       // sections are treated as if they have output characteristics DATA | R if
       // their characteristics are DATA | R | W. This implements the same
       // special case for all architectures.
void Writer::addBaserelBlocks(std::vector<Baserel> &V) {
   }
   if (I == J)
     return;
   RelocSec->addChunk(make<BaserelChunk>(Page, &V[I], &V[0] + J));
 }
 
 PartialSection *Writer::createPartialSection(StringRef Name,
                                              uint32_t OutChars) {
-  PartialSection *PSec = findPartialSection(Name, OutChars);
+  PartialSectionKey Key = {Name, OutChars};
+  PartialSection *&PSec = PartialSections[Key];
   if (PSec)
     return PSec;
   PSec = make<PartialSection>(Name, OutChars);
-  PartialSections.insert(PSec);
   return PSec;
 }
 
 PartialSection *Writer::findPartialSection(StringRef Name, uint32_t OutChars) {
-  auto It = find_if(PartialSections, [&](PartialSection *P) {
-    return P->Name == Name && P->Characteristics == OutChars;
-  });
-  if (It != PartialSections.end())
-    return *It;
-  return nullptr;
+  PartialSectionKey Key = {Name, OutChars};
+  return PartialSections[Key];
 }