This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by mstorsjo on Feb 3 2019, 2:07 PM.

Details

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.

Diff Detail

Event Timeline

mstorsjo created this revision.Feb 3 2019, 2:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 3 2019, 2:07 PM
aganea accepted this revision.Feb 3 2019, 4:46 PM

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}]; ?

This revision is now accepted and ready to land.Feb 3 2019, 4:46 PM
mstorsjo marked 3 inline comments as done.Feb 3 2019, 11:05 PM

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 updated this revision to Diff 184994.Feb 3 2019, 11:05 PM
mstorsjo marked an inline comment as done.

Removed needless declarations of the key as variables.

aganea added a comment.Feb 4 2019, 7:07 AM

! 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 added inline comments.Feb 4 2019, 7:12 AM
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 marked an inline comment as done.Feb 4 2019, 12:49 PM

! 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 added inline comments.Feb 4 2019, 12:56 PM
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.

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 marked an inline comment as done.Feb 4 2019, 1:06 PM

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 updated this revision to Diff 185142.Feb 4 2019, 1:11 PM
mstorsjo retitled this revision from [LLD] [COFF] Avoid O(n^2) insertion into PartialSections to [LLD] [COFF] Avoid O(n^2) accesses into PartialSections.

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

thakis added a subscriber: thakis.Feb 4 2019, 4:29 PM

(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.)

(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.)

This revision was automatically updated to reflect the committed changes.