[ELF] Keep GdbIndexSection::Symbols non-flattened to avoid allocating large vector

[MaskRay]

Summary

createSymbols reserved a large vector to flatten parallelly computed table chunks.
We can keep the non-flattened form to avoid the allocation.

This decreases maximum resident set size a bit (by NumSymbols*sizeof(GdbIndex),
which is ~100M for a test case that would take 21.8GiB RSS). The change
does not make code more complicated so I think it is still worthwhile.

[MaskRay]

If SyntheticSection::writeTo is guaranteed to be called once (I'm not sure if that is the case), Symbols.clear() in GdbIndexSection::writeTo decreases the maximum RSS by 190MiB, but I'm not sure if it is worthy to do these (freeing resources prematurely at the end of writeTo) for GdbIndexSection and/or other sections..

[ruiu]

I knew I could do this, but I chose to not do for the sake of simplicity of the code. I don't generally want to optimize code unless it is necessary. I'm working on re-commiting the patch I committed last week, which should reduce the memory consumption of this part of code significantly. I'm hoping that completely solves the issue.

ELF/SyntheticSections.h

private:
   void initOutputSize();
   size_t computeSymtabSize() const;
 
   // Each chunk contains information gathered from debug sections of a
   // single object file.
   std::vector<GdbChunk> Chunks;
 
   // A symbol table for this .gdb_index section.
-  std::vector<GdbSymbol> Symbols;
+  // The table is a vector of non-empty vectors that is
+  // computed parallelly, but not flattened to avoid allocating the flattened
+  // vector.
+  std::vector<std::vector<GdbSymbol>> Symbols;
 
   size_t Size;
 };
 
 // --eh-frame-hdr option tells linker to construct a header for all the
 // .eh_frame sections. This header is placed to a section named .eh_frame_hdr
 // and also to a PT_GNU_EH_FRAME segment.
 // At runtime the unwinder then can find all the PT_GNU_EH_FRAME segments by

ELF/SyntheticSections.cpp

 }
 
 GdbIndexSection::GdbIndexSection()
     : SyntheticSection(0, SHT_PROGBITS, 1, ".gdb_index") {}
 
 // Returns the desired size of an on-disk hash table for a .gdb_index section.
 // There's a tradeoff between size and collision rate. We aim 75% utilization.
 size_t GdbIndexSection::computeSymtabSize() const {
-  return std::max<size_t>(NextPowerOf2(Symbols.size() * 4 / 3), 1024);
+  size_t N = 0;
+  for (auto &Syms: Symbols)
+    N += Syms.size();
+  return std::max<size_t>(NextPowerOf2(N * 4 / 3), 1024);
 }
 
 // Compute the output section size.
 void GdbIndexSection::initOutputSize() {
   Size = sizeof(GdbIndexHeader) + computeSymtabSize() * 8;
 
   for (GdbChunk &Chunk : Chunks)
     Size += Chunk.CompilationUnits.size() * 16 + Chunk.AddressAreas.size() * 20;
 
   // Add the constant pool size if exists.
   if (!Symbols.empty()) {
-    GdbSymbol &Sym = Symbols.back();
+    GdbSymbol &Sym = Symbols.back().back();
     Size += Sym.NameOff + Sym.Name.size() + 1;
   }
 }
 
 static std::vector<InputSection *> getDebugInfoSections() {
   std::vector<InputSection *> Ret;
   for (InputSectionBase *S : InputSections)
     if (InputSection *IS = dyn_cast<InputSection>(S))
for (const DWARFDebugPubTable::Set &Set : Table.getData())
         Ret.push_back({{Ent.Name, computeGdbHash(Ent.Name)},
                        (Ent.Descriptor.toBits() << 24) | Idx});
   }
   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>
+static std::vector<std::vector<GdbIndexSection::GdbSymbol>>
 createSymbols(ArrayRef<std::vector<GdbIndexSection::NameTypeEntry>> NameTypes) {
   typedef GdbIndexSection::GdbSymbol GdbSymbol;
   typedef GdbIndexSection::NameTypeEntry NameTypeEntry;
 
   // 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;
for (ArrayRef<NameTypeEntry> Entries : NameTypes) {
         }
 
         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));
+  llvm::erase_if(
+      Symbols, [](const std::vector<GdbSymbol> &Syms) { return Syms.empty(); });
 
   // 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) {
+  for (auto &Syms : Symbols)
+    for (GdbSymbol &Sym : Syms) {
       Sym.CuVectorOff = Off;
       Off += (Sym.CuVector.size() + 1) * 4;
     }
-  for (GdbSymbol &Sym : Ret) {
+  for (auto &Syms : Symbols)
+    for (GdbSymbol &Sym : Syms) {
       Sym.NameOff = Off;
       Off += Sym.Name.size() + 1;
     }
 
-  return Ret;
+  return Symbols;
 }
 
 // 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
for (GdbChunk &Chunk : Chunks) {
     CuOff += Chunk.CompilationUnits.size();
   }
 
   // Write the on-disk open-addressing hash table containing symbols.
   Hdr->SymtabOff = Buf - Start;
   size_t SymtabSize = computeSymtabSize();
   uint32_t Mask = SymtabSize - 1;
 
-  for (GdbSymbol &Sym : Symbols) {
+  for (auto &Syms : Symbols)
+    for (GdbSymbol &Sym : Syms) {
       uint32_t H = Sym.Name.hash();
       uint32_t I = H & Mask;
       uint32_t Step = ((H * 17) & Mask) | 1;
 
       while (read32le(Buf + I * 8))
         I = (I + Step) & Mask;
 
       write32le(Buf + I * 8, Sym.NameOff);
       write32le(Buf + I * 8 + 4, Sym.CuVectorOff);
     }
 
   Buf += SymtabSize * 8;
 
   // Write the string pool.
   Hdr->ConstantPoolOff = Buf - Start;
-  for (GdbSymbol &Sym : Symbols)
+  for (auto &Syms : Symbols)
+    for (GdbSymbol &Sym : Syms)
       memcpy(Buf + Sym.NameOff, Sym.Name.data(), Sym.Name.size());
 
   // Write the CU vectors.
-  for (GdbSymbol &Sym : Symbols) {
+  for (auto &Syms : Symbols)
+    for (GdbSymbol &Sym : Syms) {
       write32le(Buf, Sym.CuVector.size());
       Buf += 4;
       for (uint32_t Val : Sym.CuVector) {
         write32le(Buf, Val);
         Buf += 4;
       }
     }
 }
 
 bool GdbIndexSection::empty() const { return !Out::DebugInfo; }
 
 EhFrameHeader::EhFrameHeader()
     : SyntheticSection(SHF_ALLOC, SHT_PROGBITS, 4, ".eh_frame_hdr") {}
 
 // .eh_frame_hdr contains a binary search table of pointers to FDEs.