Avoid hash table lookup when sorting local symbols.

[ruiu]

Summary

Looking up a hash table for each symbol should be avoided for
performance reasons. In this patch, I assign a unique ID to each
file and use that number to sort symbols.

The other way of doing this would be to use object addresses of files,
but that algorithm fails to make output reproducible. So I had to
add FileId member to InputFile class.

[grimar]

Will not help I believe. Please see my answer in the D45519 thread.

[grimar]

Numbers I got after re-profiling this place today:

lld-speed-test\mozilla\response-O0.txt
(Configuration: RelWithDebInfo, used MSVS2015 built-in profiler)

Benchmarked execution time of
lld::elf::SymbolTableBaseSection::postThunkContents

• LLD vanilla r329846: Total CPU (%): 3.42 Total CPU (ms): 246

• Changed predicate to return L.Sym->File < R.Sym->File; Total CPU (%): 2.3 Total CPU (ms): 161

• My patch (D45519) applied: Total CPU (%): 0.72 Total CPU (ms): 49

• This (D45548) patch applied: Total CPU (%): 2.08 Total CPU (ms): 148

Results were pretty stable.
Versions with sorting ((2) and (4)) seem to show almost equal time, and I believe it is expected.
The approach used in my patch (3) is about 3 times faster than them. And does not require additional members.
So IMO it is better.

[• espindola]

My idea was actually to combine both patches.

With this patch the map

MapVector<InputFile *, std::vector<SymbolTableEntry>> Arr;

in D45519 can become a simple array, no?

I will benchmark each independently and the combined patch.

[• espindola]

lld/ELF/SyntheticSections.cpp

1570

Given regular symbol A and an internal symbol B (file is null), this comparison will return false for A < B and B < A.

I think this has to be

if (!L.Sym->File || !R.Sym->File)

return L.Sym->File; // or R.Sym->File.

[• espindola]

The results I got

master: 2.819319468 seconds time elapsed
This patch: 2.735310955 seconds time elapsed
D45519: 2.624760166 seconds time elapsed
combined: 2.604495001 seconds time elapsed

So I think we want both.

[grimar]

In D45548#1066314, @espindola wrote:

The results I got

master: 2.819319468 seconds time elapsed
This patch: 2.735310955 seconds time elapsed
D45519: 2.624760166 seconds time elapsed
combined: 2.604495001 seconds time elapsed

So I think we want both.

Thanks for the numbers. For me having combined version is fine. Rui, what do you think? (I'll rebase mine when/if this be landed).

With this patch the map

MapVector<InputFile *, std::vector<SymbolTableEntry>> Arr;

in D45519 can become a simple array, no?

There is one minor issue I am thinking about. We will need the array of size [number of files].
We could use the NextFileId to find array size, but since LLD can be used as a library, we
will have to reset NextFileId to zero value in elf::link, otherwise, we will have a hidden issue here,
which will lead to creating arrays larger than needed.

(this is one line change fix, posted just for the record to not forget. Probably it worth to include that change
to this patch).

[grimar]

LGTM with Rafael's comment addressed.

[• espindola]

LGTM with the sort predicate fixed.

[grimar]

Can it be committed? D45519 depends on this.

[grimar]

Rui, can you commit this please? Or do you have any concerns?

lld/ELF/InputFiles.h

public:
   mutable std::string ToStringCache;
 
   std::string getSrcMsg(const Symbol &Sym, InputSectionBase &Sec,
                         uint64_t Offset);
 
   // True if this is an argument for --just-symbols. Usually false.
   bool JustSymbols = false;
 
+  // This is a unique monotonically-increasing number assigned to each
+  // file. This doesn't have a big role but is convenient to sort
+  // symbols quickly in a reproducible manner.
+  uint32_t FileId;
+
   // GroupId is used for --warn-backrefs which is an optional error
   // checking feature. All files within the same --{start,end}-group
   // get the same group ID. Otherwise, each file gets a new group
   // ID. For more info, see checkDependency() in SymbolTable.cpp.
   uint32_t GroupId;
   static bool IsInGroup;
 
 protected:
   InputFile(Kind K, MemoryBufferRef M);
   std::vector<InputSectionBase *> Sections;
   std::vector<Symbol *> Symbols;
 
 private:
   const Kind FileKind;
 
+  static uint32_t NextFileId;
   static uint32_t NextGroupId;
 };
 
 template <typename ELFT> class ELFFileBase : public InputFile {
 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Word Elf_Word;

lld/ELF/InputFiles.cpp

 using namespace llvm::object;
 using namespace llvm::sys;
 using namespace llvm::sys::fs;
 
 using namespace lld;
 using namespace lld::elf;
 
 bool InputFile::IsInGroup;
+uint32_t InputFile::NextFileId;
 uint32_t InputFile::NextGroupId;
 std::vector<BinaryFile *> elf::BinaryFiles;
 std::vector<BitcodeFile *> elf::BitcodeFiles;
 std::vector<InputFile *> elf::ObjectFiles;
 std::vector<InputFile *> elf::SharedFiles;
 
 TarWriter *elf::Tar;
 
 InputFile::InputFile(Kind K, MemoryBufferRef M)
-    : MB(M), GroupId(NextGroupId), FileKind(K) {
+    : MB(M), FileId(NextFileId++), GroupId(NextGroupId), FileKind(K) {
   // All files within the same --{start,end}-group get the same group ID.
   // Otherwise, a new file will get a new group ID.
   if (!IsInGroup)
     ++NextGroupId;
 }
 
 Optional<MemoryBufferRef> elf::readFile(StringRef Path) {
   // The --chroot option changes our virtual root directory.

lld/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];
+                     if (!L.Sym->File || !R.Sym->File)
+                       return false;
+                     return L.Sym->File->FileId < R.Sym->File->FileId;
                    });
 }
 
 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();

lld/test/ELF/local-symbols-order.s

 # REQUIRES: x86
 
 # RUN: echo '.data; .file "file2"; foo2:; .global bar2; .hidden bar2; bar2:' > %t2.s
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %t2.s -o %t2.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
 
 # RUN: ld.lld -o %t %t1.o %t2.o --emit-relocs
 # RUN: llvm-readobj -symbols -sections -elf-output-style=GNU %t | FileCheck %s
 
-## Check we sort local symbols to match the following order: 
+## Check we sort local symbols to match the following order:
 ## file1, local1, section1, hidden1, file2, local2, section2, hidden2 ...
 
 # CHECK: Section Headers:
-# CHECK:   [Nr] Name
-# CHECK:   [ [[ST:.*]]] .text
-# CHECK:   [ [[SD:.*]]] .data
-# CHECK:   [ [[SC:.*]]] .comment
+# CHECK: [ 1] .text
+# CHECK: [ 2] .data
+# CHECK: [ 3] .comment
 
 # CHECK:      Num:    Value          Size Type    Bind   Vis      Ndx Name
 # CHECK-NEXT:   0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
 # CHECK-NEXT:   1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS file1
 # CHECK-NEXT:   2: 0000000000201000     0 NOTYPE  LOCAL  DEFAULT    1 foo1
-# CHECK-NEXT:   3: 0000000000201000     0 SECTION LOCAL  DEFAULT    [[ST]]
+# CHECK-NEXT:   3: 0000000000201000     0 SECTION LOCAL  DEFAULT    1
 # CHECK-NEXT:   4: 0000000000201000     0 NOTYPE  LOCAL  HIDDEN     1 bar1
 # CHECK-NEXT:   5: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS file2
 # CHECK-NEXT:   6: 0000000000201000     0 NOTYPE  LOCAL  DEFAULT    2 foo2
-# CHECK-NEXT:   7: 0000000000201000     0 SECTION LOCAL  DEFAULT    [[SD]]
-# CHECK-NEXT:   8: 0000000000201000     0 NOTYPE  LOCAL  HIDDEN     2 bar2
-# CHECK-NEXT:   9: 0000000000000000     0 SECTION LOCAL  DEFAULT    [[SC]]
+# CHECK-NEXT:   7: 0000000000201000     0 SECTION LOCAL  DEFAULT    2
+# CHECK-NEXT:   8: 0000000000000000     0 SECTION LOCAL  DEFAULT    3
+# CHECK-NEXT:   9: 0000000000201000     0 NOTYPE  LOCAL  HIDDEN     2 bar2
 
 foo1:
 
 .global bar1
 .hidden bar1
 bar1:
 
 .file "file1"