Parallelize GdbIndexSection's symbol table creation.

[ruiu]

Summary

Since .gdb_index sections contain all known symbols, they can be very large.
One of my executable has a .gdb_index section of 1350 GiB. Uniquifying
symbols by name takes 3.77 seconds on my machine. This patch parallelize it.

Time to call createSymbols() with 8.4 million unique symbols:

Without this patch: 3773 ms
Parallelism = 1:    4374 ms
Parallelism = 2:    2628 ms
Parallelism = 16:    837 ms

As you can see above, this algorithm is a bit more inefficient
than the non-parallelized version, but even with dual-core, it is
faster than that, so I think it is overall a win.

[ruiu]

• rebased

[grimar]

LGTM.

lld/ELF/SyntheticSections.cpp

2372

MergeNoTailSection has NumShards == 32, I wonder why 16 here?

[ruiu]

lld/ELF/SyntheticSections.cpp

2372

No particular reason. Will change to 32. Due to diminishing return, 16 and 32 wouldn't be that different though.

lld/ELF/SyntheticSections.cpp

 
 // Create a list of symbols from a given list of symbol names and types
 // by uniquifying them by name.
 static std::vector<GdbIndexSection::GdbSymbol>
 createSymbols(ArrayRef<std::vector<GdbIndexSection::NameTypeEntry>> NameTypes) {
   typedef GdbIndexSection::GdbSymbol GdbSymbol;
   typedef GdbIndexSection::NameTypeEntry NameTypeEntry;
 
-  // A map to uniquify symbols by name.
-  DenseMap<CachedHashStringRef, size_t> Map;
+  // The number of symbols we will handle in this function is of the order
+  // of millions for very large executables, so we use multi-threading to
+  // speed it up.
+  size_t NumShards = 16;
+  size_t Concurrency = 1;
+  if (ThreadsEnabled)
+    Concurrency =
+        std::min<size_t>(PowerOf2Floor(hardware_concurrency()), NumShards);
+
+  // A sharded map to uniquify symbols by name.
+  std::vector<DenseMap<CachedHashStringRef, size_t>> Map(NumShards);
+  size_t Shift = 32 - countTrailingZeros(NumShards);
 
   // Instantiate GdbSymbols while uniqufying them by name.
-  std::vector<GdbSymbol> Ret;
+  std::vector<std::vector<GdbSymbol>> Symbols(NumShards);
+  parallelForEachN(0, Concurrency, [&](size_t ThreadId) {
     for (ArrayRef<NameTypeEntry> Entries : NameTypes) {
       for (const NameTypeEntry &Ent : Entries) {
-      size_t &Idx = Map[Ent.Name];
+        size_t ShardId = Ent.Name.hash() >> Shift;
+        if ((ShardId & (Concurrency - 1)) != ThreadId)
+          continue;
+
+        size_t &Idx = Map[ShardId][Ent.Name];
         if (Idx) {
-        Ret[Idx - 1].CuVector.push_back(Ent.Type);
+          Symbols[ShardId][Idx - 1].CuVector.push_back(Ent.Type);
           continue;
         }
 
-      Idx = Ret.size() + 1;
-      Ret.push_back({Ent.Name, {Ent.Type}, 0, 0});
+        Idx = Symbols[ShardId].size() + 1;
+        Symbols[ShardId].push_back({Ent.Name, {Ent.Type}, 0, 0});
       }
     }
+  });
+
+  size_t NumSymbols = 0;
+  for (ArrayRef<GdbSymbol> V : Symbols)
+    NumSymbols += V.size();
+
+  // The return type is a flattened vector, so we'll copy each vector
+  // contents to Ret.
+  std::vector<GdbSymbol> Ret;
+  Ret.reserve(NumSymbols);
+  for (std::vector<GdbSymbol> &Vec : Symbols)
+    for (GdbSymbol &Sym : Vec)
+      Ret.push_back(std::move(Sym));
 
   // CU vectors and symbol names are adjacent in the output file.
   // We can compute their offsets in the output file now.
   size_t Off = 0;
   for (GdbSymbol &Sym : Ret) {
     Sym.CuVectorOff = Off;
     Off += (Sym.CuVector.size() + 1) * 4;
   }

lld/test/ELF/gdb-index.s

 # DWARF-NEXT:    Version = 7
 # DWARF:       CU list offset = 0x18, has 2 entries:
 # DWARF-NEXT:    0: Offset = 0x0, Length = 0x34
 # DWARF-NEXT:    1: Offset = 0x34, Length = 0x34
 # DWARF:       Address area offset = 0x38, has 2 entries:
 # DWARF-NEXT:    Low/High address = [0x201000, 0x201001) (Size: 0x1), CU id = 0
 # DWARF-NEXT:    Low/High address = [0x201004, 0x201006) (Size: 0x2), CU id = 1
 # DWARF:       Symbol table offset = 0x60, size = 1024, filled slots:
-# DWARF-NEXT:    512: Name offset = 0x2b, CU vector offset = 0x14
-# DWARF-NEXT:      String name: aaaaaaaaaaaaaaaa, CU vector index: 2
-# DWARF-NEXT:    754: Name offset = 0x27, CU vector offset = 0x8
-# DWARF-NEXT:      String name: int, CU vector index: 1
-# DWARF-NEXT:    822: Name offset = 0x1c, CU vector offset = 0x0
-# DWARF-NEXT:      String name: entrypoint, CU vector index: 0
+# DWARF-NEXT:    512: Name offset = 0x1c, CU vector offset = 0x0
+# DWARF-NEXT:      String name: aaaaaaaaaaaaaaaa, CU vector index: 0
+# DWARF-NEXT:    754: Name offset = 0x38, CU vector offset = 0x10
+# DWARF-NEXT:      String name: int, CU vector index: 2
+# DWARF-NEXT:    822: Name offset = 0x2d, CU vector offset = 0x8
+# DWARF-NEXT:      String name: entrypoint, CU vector index: 1
 # DWARF:       Constant pool offset = 0x2060, has 3 CU vectors:
-# DWARF-NEXT:    0(0x0): 0x30000000
-# DWARF-NEXT:    1(0x8): 0x90000000 0x90000001
-# DWARF-NEXT:    2(0x14): 0x30000001
+# DWARF-NEXT:    0(0x0): 0x30000001
+# DWARF-NEXT:    1(0x8): 0x30000000
+# DWARF-NEXT:    2(0x10): 0x90000000 0x90000001
 
 # SECTION-NOT: debug_gnu_pubnames
 
 # RUN: ld.lld --gdb-index --no-gdb-index %t1.o %t2.o -o %t2
 # RUN: llvm-readobj -sections %t2 | FileCheck -check-prefix=NOGDB %s
 # NOGDB-NOT: Name: .gdb_index
 
 ## The following section contents are created by this using gcc 7.1.0: