[COFF] Avoid O(n^2) accesses into PartialSections
authorMartin Storsjo <martin@martin.st>
Tue, 5 Feb 2019 08:16:10 +0000 (08:16 +0000)
committerMartin Storsjo <martin@martin.st>
Tue, 5 Feb 2019 08:16:10 +0000 (08:16 +0000)
commitccd4e5e01684f7f05ea329a475a0b7a62b311039
treedbd76e3f86196954fefe1b95910c0736e3f20c69
parent537a718fcbbc830ba660477af5a7328cd157c8b9
[COFF] Avoid O(n^2) accesses into PartialSections

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. After this patch, the
linking time is back to what it was before.

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.

Differential Revision: https://reviews.llvm.org/D57666

llvm-svn: 353146
lld/COFF/Writer.cpp