[ELF] --gdb-index: use const char *, uint32_t to replace CachedHashStringRef

[MaskRay]

Summary

This decreases the size of NameAttrEntry from 20 bytes to 16 bytes on 64-bit platforms.

[ruiu]

I believe the memory savings of this patch is not free; it now has to scan the same string more than once to find a null terminator. Even though we want to reduce memory usage of lld for Google, in general, saving memory is not always the goal that we want to achieve. We need to get a right balance. To do that, can you tell me how much memory you can save with this patch, and how much is the performance penalty of this patch?

[MaskRay]

In D54968#1310361, @ruiu wrote:

I believe the memory savings of this patch is not free; it now has to scan the same string more than once to find a null terminator. Even though we want to reduce memory usage of lld for Google, in general, saving memory is not always the goal that we want to achieve. We need to get a right balance. To do that, can you tell me how much memory you can save with this patch, and how much is the performance penalty of this patch?

I think the memory saving may be negligible but interestingly my testing says it makes it faster when linking clang. My understanding is that the smaller size of NameAttrs improves caching a bit.

cmake -H. -BStaticDebug -G Ninja -DCMAKE_BUILD_TYPE=Debug -DCMAKE_EXE_LINKER_FLAGS=-Wl,--gdb-index ...
rm bin/clang-8; ninja -C StaticDebug -v -n clang to extract the clang command line, append '-###' to get the ld.lld command line. bin/clang-8 is of 601,059,920 bytes

perf stat -r 20 /tmp/link-clang => run several times without and with the patch. Without the patch it is usually 4.8 seconds (4.884600870 seconds time elapsed) while with the patch, it is usually 4.7 seconds (4.743274463 seconds time elapsed).

Even though we want to reduce memory usage of lld for Google

Thanks for the reminder but please believe I weigh much the general-purpose usability a lot.

[ruiu]

I tried this patch myself, but it is hard to say if this patch makes a difference. Probably the performance difference is negligible.

Do you know how many NameAttrEntry's are created for your test case? (I.e. how many bytes are saved?)

[MaskRay]

• For clang, the total number of NameAttrs is 32496
• For an internal larger executable, it is 193776

I think both memory/space changes are negligible (I made a mistake when giving the statistics "4.8 seconds (4.884600870 seconds time elapsed) while with the patch, it is usually 4.7": used a wrong ld.lld).

[ruiu]

Thank you for measuring it. Given these numbers, I wouldn't land this change as StringRef is more straightforward.

ELF/SyntheticSections.h

public:
   };
 
   struct CuEntry {
     uint64_t CuOffset;
     uint64_t CuLength;
   };
 
   struct NameAttrEntry {
-    llvm::CachedHashStringRef Name;
+    const char *Name;
+    uint32_t NameHash;
     uint32_t CuIndexAndAttrs;
   };
 
   struct GdbChunk {
     InputSection *Sec;
     std::vector<AddressEntry> AddressAreas;
     std::vector<CuEntry> CompilationUnits;
   };

ELF/SyntheticSections.cpp

for (const DWARFDebugPubTable::Set &Set : Table.getData()) {
       // 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.
       //
       // We assume both CUs[*].CuOff and Set.Offset are increasing.
       while (I < CUs.size() && CUs[I].CuOffset < Set.Offset)
         ++I;
       for (const DWARFDebugPubTable::Entry &Ent : Set.Entries)
-        Ret.push_back({{Ent.Name, computeGdbHash(Ent.Name)},
+        Ret.push_back({Ent.Name.data(), 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.
createSymbols(ArrayRef<std::vector<GdbIndexSection::NameAttrEntry>> NameAttrs,
   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;
+        size_t ShardId = Ent.NameHash >> Shift;
         if ((ShardId & (Concurrency - 1)) != ThreadId)
           continue;
 
+        CachedHashStringRef Name(Ent.Name, Ent.NameHash);
         uint32_t V = Ent.CuIndexAndAttrs + CuIdxs[I];
-        size_t &Idx = Map[ShardId][Ent.Name];
+        size_t &Idx = Map[ShardId][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});
+        Symbols[ShardId].push_back({Name, {V}, 0, 0});
       }
       ++I;
     }
   });
 
   size_t NumSymbols = 0;
   for (ArrayRef<GdbSymbol> V : Symbols)
     NumSymbols += V.size();