[ELF] --gdb-index: don't retain NameAttrs

[MaskRay]

Summary

Tested a large internal target on a machine with 6 cores.

Before: 25.245s 13.73GiB
After: 31.198s 12.9GiB

/usr/bin/gold (Debian): 145.07s 12.07GiB

lld --no-gdb-index: 21.198s 9.12GiB

[MaskRay]

ELF/SyntheticSections.cpp

2521

The lost of parallelism happens here. If there is some parallel primitive to partition threads into 2 groups, a better scheme is for one group to call readPubNamesAndTypes, the other group to work on NameAttrs.

[MaskRay]

I experimented an enhancement: strip-mining on Sections: https://reviews.llvm.org/differential/diff/187004/ it is more complex (but still simpler than the original code) and slightly faster (28.*s).

ELF/SyntheticSections.cpp

for (std::unique_ptr<DWARFUnit> &Cu : Dwarf.compile_units()) {
     }
     ++CuIdx;
   }
 
   return Ret;
 }
 
 template <class ELFT>
-static std::vector<GdbIndexSection::NameAttrEntry>
+static void
 readPubNamesAndTypes(const LLDDwarfObj<ELFT> &Obj,
-                     const std::vector<GdbIndexSection::CuEntry> &CUs) {
+                     const std::vector<GdbIndexSection::CuEntry> &CUs,
+                     std::vector<GdbIndexSection::NameAttrEntry> &Ret) {
   const DWARFSection &PubNames = Obj.getGnuPubNamesSection();
   const DWARFSection &PubTypes = Obj.getGnuPubTypesSection();
 
-  std::vector<GdbIndexSection::NameAttrEntry> Ret;
+  Ret.clear();
   for (const DWARFSection *Pub : {&PubNames, &PubTypes}) {
     DWARFDebugPubTable Table(Obj, *Pub, Config->IsLE, true);
     for (const DWARFDebugPubTable::Set &Set : Table.getData()) {
       // The value written into the constant pool is Kind << 24 | CuIndex. As we
       // don't know how many compilation units precede this object to compute
       // CuIndex, we compute (Kind << 24 | CuIndexInThisObject) instead, and add
       // the number of preceding compilation units later.
       uint32_t I =
           lower_bound(CUs, Set.Offset,
                       [](GdbIndexSection::CuEntry CU, uint32_t Offset) {
                         return CU.CuOffset < Offset;
                       }) -
           CUs.begin();
       for (const DWARFDebugPubTable::Entry &Ent : Set.Entries)
         Ret.push_back({{Ent.Name, computeGdbHash(Ent.Name)},
                        (Ent.Descriptor.toBits() << 24) | I});
     }
   }
-  return Ret;
 }
 
-// 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::NameAttrEntry>> NameAttrs,
-              const std::vector<GdbIndexSection::GdbChunk> &Chunks) {
+// Returns a newly-created .gdb_index section.
+template <class ELFT> GdbIndexSection *GdbIndexSection::create() {
   typedef GdbIndexSection::GdbSymbol GdbSymbol;
   typedef GdbIndexSection::NameAttrEntry NameAttrEntry;
 
-  // For each chunk, compute the number of compilation units preceding it.
-  uint32_t CuIdx = 0;
-  std::vector<uint32_t> CuIdxs(Chunks.size());
-  for (uint32_t I = 0, E = Chunks.size(); I != E; ++I) {
-    CuIdxs[I] = CuIdx;
-    CuIdx += Chunks[I].CompilationUnits.size();
-  }
-
-  // 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 = 32;
-  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<std::vector<GdbSymbol>> Symbols(NumShards);
-  parallelForEachN(0, Concurrency, [&](size_t ThreadId) {
-    uint32_t I = 0;
-    for (ArrayRef<NameAttrEntry> Entries : NameAttrs) {
-      for (const NameAttrEntry &Ent : Entries) {
-        size_t ShardId = Ent.Name.hash() >> Shift;
-        if ((ShardId & (Concurrency - 1)) != ThreadId)
-          continue;
-
-        uint32_t V = Ent.CuIndexAndAttrs + CuIdxs[I];
-        size_t &Idx = Map[ShardId][Ent.Name];
-        if (Idx) {
-          Symbols[ShardId][Idx - 1].CuVector.push_back(V);
-          continue;
-        }
-
-        Idx = Symbols[ShardId].size() + 1;
-        Symbols[ShardId].push_back({Ent.Name, {V}, 0, 0});
-      }
-      ++I;
-    }
-  });
-
-  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;
-  }
-  for (GdbSymbol &Sym : Ret) {
-    Sym.NameOff = Off;
-    Off += Sym.Name.size() + 1;
-  }
-
-  return Ret;
-}
-
-// Returns a newly-created .gdb_index section.
-template <class ELFT> GdbIndexSection *GdbIndexSection::create() {
   std::vector<InputSection *> Sections = getDebugInfoSections();
 
   // .debug_gnu_pub{names,types} are useless in executables.
   // They are present in input object files solely for creating
   // a .gdb_index. So we can remove them from the output.
   for (InputSectionBase *S : InputSections)
     if (S->Name == ".debug_gnu_pubnames" || S->Name == ".debug_gnu_pubtypes")
       S->Live = false;
 
   std::vector<GdbChunk> Chunks(Sections.size());
-  std::vector<std::vector<NameAttrEntry>> NameAttrs(Sections.size());
+  std::vector<GdbSymbol> Symbols;
+
+  DenseMap<CachedHashStringRef, uint32_t> Map;
+  std::vector<uint32_t> CuIdxs(Chunks.size());
 
   parallelForEachN(0, Sections.size(), [&](size_t I) {
     ObjFile<ELFT> *File = Sections[I]->getFile<ELFT>();
     DWARFContext Dwarf(make_unique<LLDDwarfObj<ELFT>>(File));
-
     Chunks[I].Sec = Sections[I];
     Chunks[I].CompilationUnits = readCuList(Dwarf);
     Chunks[I].AddressAreas = readAddressAreas(Dwarf, Sections[I]);
-    NameAttrs[I] = readPubNamesAndTypes<ELFT>(
+  });
+  uint32_t CuIdx = 0;
+  for (uint32_t I = 0, E = Chunks.size(); I != E; ++I) {
+    CuIdxs[I] = CuIdx;
+    CuIdx += Chunks[I].CompilationUnits.size();
+  }
+
+  std::mutex Mutex;
+  parallelForEachN(0, Sections.size(), [&](size_t I) {
+    ObjFile<ELFT> *File = Sections[I]->getFile<ELFT>();
+    DWARFContext Dwarf(make_unique<LLDDwarfObj<ELFT>>(File));
+    std::vector<NameAttrEntry> NameAttrs;
+    readPubNamesAndTypes<ELFT>(
         static_cast<const LLDDwarfObj<ELFT> &>(Dwarf.getDWARFObj()),
-        Chunks[I].CompilationUnits);
+        Chunks[I].CompilationUnits, NameAttrs);
+    std::lock_guard<std::mutex> Lock(Mutex);
+    for (NameAttrEntry &Ent : NameAttrs) {
+      auto R = Map.try_emplace(Ent.Name, Symbols.size());
+      if (R.second)
+        Symbols.push_back({Ent.Name, {}, 0, 0});
+      Symbols[R.first->second].CuVector.push_back(Ent.CuIndexAndAttrs +
+                                                  CuIdxs[I]);
+    }
   });
 
+  // CU vectors and symbol names are adjacent in the output file.
+  // We can compute their offsets in the output file now.
+  uint32_t Off = 0;
+  for (GdbSymbol &Sym : Symbols) {
+    Sym.CuVectorOff = Off;
+    Off += (1 + Sym.CuVector.size()) * 4;
+  }
+
+  for (GdbSymbol &Sym : Symbols) {
+    Sym.NameOff = Off;
+    Off += Sym.Name.size() + 1;
+  }
+
   auto *Ret = make<GdbIndexSection>();
   Ret->Chunks = std::move(Chunks);
-  Ret->Symbols = createSymbols(NameAttrs, Ret->Chunks);
+  Ret->Symbols = std::move(Symbols);
   Ret->initOutputSize();
   return Ret;
 }
 
 void GdbIndexSection::writeTo(uint8_t *Buf) {
   // Write the header.
   auto *Hdr = reinterpret_cast<GdbIndexHeader *>(Buf);
   uint8_t *Start = Buf;