[ELF] - Change the way of sorting local symbols.

[grimar]

Summary

rLLD329787 added the stable sorting to SymbolTableBaseSection::postThunkContents.

I profiled the Mozilla (response-O0.txt) from lld-speed-test package and found
std::stable_sort is showing up in profile results and consuming the 3.1% of the total
CPU time in the RelWithDebug build. Total time of postThunkContents is 3.54%, 238ms.

This change reduces postTimeContents time to 50ms, making it to take 0.73% of Total CPU time.

Instead of sorting the local part I suggest to just rebuild it.

[• espindola]

Add a comment on why we don't use stable_sort.

LGTM with that.

[ruiu]

Strictly speaking, this is a violation of the rule that we shouldn't use a hash table for symbols other than the Symbol Table. Is there any way to avoid using a new hash table?

[ruiu]

I mean just sorting a symbol shouldn't take 0.73% of the total execution time.

[ruiu]

George, can you try to not use hash table like this in the future? Both this patch and your previous patch use a hash table to store a lot of symbols, which is a violation of the rule I set to achieve a good performance. If it is unavoidable, please explain in the commit message so that we can discuss and examine if it is really unavoidable. Just using a hash table without an explanation isn't good.

[• espindola]

In D45519#1065031, @ruiu wrote:

George, can you try to not use hash table like this in the future? Both this patch and your previous patch use a hash table to store a lot of symbols, which is a violation of the rule I set to achieve a good performance. If it is unavoidable, please explain in the commit message so that we can discuss and examine if it is really unavoidable. Just using a hash table without an explanation isn't good.

Note that this hash in on InputFiles, not symbols.

[ruiu]

Yeah, but the it looks up the hash table N times where N is the number of local symbols, no?

[• espindola]

In D45519#1065037, @ruiu wrote:

Yeah, but the it looks up the hash table N times where N is the number of local symbols, no?

It does.

Since the order of two files is arbitrary, how about just giving each InputFile a number when it is created ?

[ruiu]

Since the order of two files is arbitrary, how about just giving each InputFile a number when it is created ?

That's exactly what I was thinking. :) I'll send you guys a patch.

[grimar]

In D45519#1065055, @ruiu wrote:

Since the order of two files is arbitrary, how about just giving each InputFile a number when it is created ?

That's exactly what I was thinking. :) I'll send you guys a patch.

That will not work. First what I tried was: I changed the predicate from return FileIDs[L.Sym->File] < FileIDs[R.Sym->File]; to return L.Sym->File < R.Sym->File; (just to look how the lookup in the hash table affects the perfomance).
It decreased CPU time by about 1%, but it still was about 2%. After that this patch born.

[grimar]

Can we land it stand alone? It still brings a noticeable speed-up even without D45548.

[grimar]

Ping.

[ruiu]

LGTM

[grimar]

Thanks, Rui!

ELF/SyntheticSections.cpp

void SymbolTableBaseSection::postThunkContents() {
   // Move all local symbols before global symbols.
   auto E = std::stable_partition(
       Symbols.begin(), Symbols.end(), [](const SymbolTableEntry &S) {
         return S.Sym->isLocal() || S.Sym->computeBinding() == STB_LOCAL;
       });
   size_t NumLocals = E - Symbols.begin();
   getParent()->Info = NumLocals + 1;
 
-  // Assign the growing unique ID for each local symbol's file.
-  DenseMap<InputFile *, unsigned> FileIDs;
-  for (auto I = Symbols.begin(); I != E; ++I)
-    FileIDs.insert({I->Sym->File, FileIDs.size()});
-
-  // Sort the local symbols to group them by file. We do not need to care about
-  // the STT_FILE symbols, they are already naturally placed first in each group.
-  // That happens because STT_FILE is always the first symbol in the object and
-  // hence precede all other local symbols we add for a file.
-  std::stable_sort(Symbols.begin(), E,
-                   [&](const SymbolTableEntry &L, const SymbolTableEntry &R) {
-                     return FileIDs[L.Sym->File] < FileIDs[R.Sym->File];
-                   });
+  // We want to group the local symbols by file. For that we rebuild the local
+  // part of the symbols vector. We do not need to care about the STT_FILE
+  // symbols, they are already naturally placed first in each group. That
+  // happens because STT_FILE is always the first symbol in the object and hence
+  // precede all other local symbols we add for a file.
+  MapVector<InputFile *, std::vector<SymbolTableEntry>> Arr;
+  for (const SymbolTableEntry &S : llvm::make_range(Symbols.begin(), E))
+    Arr[S.Sym->File].push_back(S);
+
+  auto I = Symbols.begin();
+  for (std::pair<InputFile *, std::vector<SymbolTableEntry>> &P : Arr)
+    for (SymbolTableEntry &Entry : P.second)
+      *I++ = Entry;
 }
 
 void SymbolTableBaseSection::addSymbol(Symbol *B) {
   // Adding a local symbol to a .dynsym is a bug.
   assert(this->Type != SHT_DYNSYM || !B->isLocal());
 
   bool HashIt = B->isLocal();
   Symbols.push_back({B, StrTabSec.addString(B->getName(), HashIt)});