[ELF] - Speedup .gdb_index building with use of relocation caching layer.

[grimar]

Summary

This patch introduces relocation caching helper.
Instead of plain std::find by offset, caching helper
allows either to take relocation from cache or
to continue searching from last unvisited relocation.

That gives speedup by 55%. I used built-in benchmark for
perfomance estimating (D36076). It runs .gdb_index building in
a loop and calculated average time.
After 50 runs, results are:

• With patch: Avg: 2.700828e+00, N: 50 Min: 2.658942e+00, Max: 2.729724e+00, Last: 2.717378e+00
• W/o patch: Avg: 4.903375e+00, N: 50 Min: 4.889383e+00, Max: 4.949485e+00, Last: 4.928791e+00

2.7/4.9 == 0.551

I also tried traditional benchmarking approach, linked debug clang
(used clang objects and reproduce from clang-gdb-index folder
of lld-speed-test.tar.xz archive posted by Rafael earlier)

Without patch time is: 15,026934140 seconds time elapsed ( +- 0,50% )
With patch: 12,907121321 seconds time elapsed ( +- 0,72% )

So it is 15.02 / (15.02 - 12.9) == 7.08% speedup of total link timewith --gdb-index,
though calculations are not so accurate as built-in benchmark above shows.

[ruiu]

I don't think this patch is not towards a right direction. I'll send you a different patch.

[ruiu]

Sorry, I mean I think this is not towards a right direction. See https://reviews.llvm.org/D36079.

ELF/GdbIndex.h

 namespace elf {
 
 class InputSection;
 
 struct LLDDWARFSection final : public llvm::DWARFSection {
   InputSectionBase *Sec = nullptr;
 };
 
+struct RelocCache {
+  const void *FirstReloc;
+  uint64_t NumRelocs;
+  uint64_t NumProccessedRelocs;
+  llvm::DenseMap<uint64_t, uint64_t> OffsetToIndex;
+
+  template <class RelTy> uint64_t getIndex(uint64_t Offset);
+};
+
 template <class ELFT> class LLDDwarfObj final : public llvm::DWARFObject {
   ObjFile<ELFT> *Obj;
   LLDDWARFSection InfoSection;
   LLDDWARFSection RangeSection;
   LLDDWARFSection LineSection;
   StringRef AbbrevSection;
   StringRef GnuPubNamesSection;
   StringRef GnuPubTypesSection;
+  llvm::DenseMap<const InputSectionBase *, RelocCache> RelocationsCache;
 
   template <class RelTy>
-  llvm::Optional<llvm::RelocAddrEntry> findAux(const InputSectionBase &Sec,
-                                               uint64_t Pos,
-                                               ArrayRef<RelTy> Rels) const;
+  llvm::Optional<llvm::RelocAddrEntry>
+  findAux(const InputSectionBase &Sec, uint64_t Pos, ArrayRef<RelTy> Rels);
 
 public:
   explicit LLDDwarfObj(ObjFile<ELFT> *Obj);
   const llvm::DWARFSection &getInfoSection() const override {
     return InfoSection;
   }
   const llvm::DWARFSection &getRangeSection() const override {
     return RangeSection;

ELF/GdbIndex.cpp

if (Sec->Name == ".debug_abbrev")
       AbbrevSection = toStringRef(Sec->Data);
     else if (Sec->Name == ".debug_gnu_pubnames")
       GnuPubNamesSection = toStringRef(Sec->Data);
     else if (Sec->Name == ".debug_gnu_pubtypes")
       GnuPubTypesSection = toStringRef(Sec->Data);
   }
 }
 
+template <class RelTy> uint64_t RelocCache::getIndex(uint64_t Offset) {
+  auto It = OffsetToIndex.find(Offset);
+  if (It != OffsetToIndex.end())
+    return It->second;
+
+  ArrayRef<RelTy> V(static_cast<const RelTy *>(FirstReloc), NumRelocs);
+  V = V.drop_front(NumProccessedRelocs);
+
+  while (!V.empty()) {
+    const RelTy &Rel = V.front();
+    V = V.drop_front();
+    uint64_t Index = NumProccessedRelocs++;
+
+    OffsetToIndex[Rel.r_offset] = Index;
+    if (Rel.r_offset == Offset)
+      return Index;
+  }
+
+  return (uint64_t)-1;
+}
+
 // Find if there is a relocation at Pos in Sec.  The code is a bit
 // more complicated than usual because we need to pass a section index
 // to llvm since it has no idea about InputSection.
 template <class ELFT>
 template <class RelTy>
-Optional<RelocAddrEntry>
-LLDDwarfObj<ELFT>::findAux(const InputSectionBase &Sec, uint64_t Pos,
-                           ArrayRef<RelTy> Rels) const {
-  auto I = llvm::find_if(Rels,
-                         [=](const RelTy &Rel) { return Rel.r_offset == Pos; });
-  if (I == Rels.end())
+Optional<RelocAddrEntry> LLDDwarfObj<ELFT>::findAux(const InputSectionBase &Sec,
+                                                    uint64_t Pos,
+                                                    ArrayRef<RelTy> Rels) {
+  auto P = RelocationsCache.insert({&Sec, {}});
+  RelocCache &Cache = P.first->second;
+  if (P.second) {
+    Cache.FirstReloc = Rels.data();
+    Cache.NumRelocs = Rels.size();
+    Cache.NumProccessedRelocs = 0;
+  }
+
+  uint64_t Index = Cache.getIndex<RelTy>(Pos);
+  if (Index == (uint64_t)-1)
       return None;
-  const RelTy &Rel = *I;
+
+  const RelTy &Rel = Rels[Index];
   const ObjFile<ELFT> *File = Sec.getFile<ELFT>();
   uint32_t SymIndex = Rel.getSymbol(Config->IsMips64EL);
   const typename ELFT::Sym &Sym = File->getELFSymbols()[SymIndex];
   uint32_t SecIndex = File->getSectionIndex(Sym);
   SymbolBody &B = File->getRelocTargetSym(Rel);
   auto &DR = cast<DefinedRegular>(B);
   uint64_t Val = DR.Value + getAddend<ELFT>(Rel);
 
   // FIXME: We should be consistent about always adding the file
   // offset or not.
   if (DR.Section->Flags & ELF::SHF_ALLOC)
     Val += cast<InputSection>(DR.Section)->getOffsetInFile();
 
   RelocAddrEntry Ret{SecIndex, Val};
   return Ret;
 }
 
 template <class ELFT>
 Optional<RelocAddrEntry> LLDDwarfObj<ELFT>::find(const llvm::DWARFSection &S,
                                                  uint64_t Pos) const {
   auto &Sec = static_cast<const LLDDWARFSection &>(S);
   if (Sec.Sec->AreRelocsRela)
-    return findAux(*Sec.Sec, Pos, Sec.Sec->template relas<ELFT>());
-  return findAux(*Sec.Sec, Pos, Sec.Sec->template rels<ELFT>());
+    return const_cast<LLDDwarfObj<ELFT> *>(this)->findAux(
+        *Sec.Sec, Pos, Sec.Sec->template relas<ELFT>());
+  return const_cast<LLDDwarfObj<ELFT> *>(this)->findAux(
+      *Sec.Sec, Pos, Sec.Sec->template rels<ELFT>());
 }
 
 template class elf::LLDDwarfObj<ELF32LE>;
 template class elf::LLDDwarfObj<ELF32BE>;
 template class elf::LLDDwarfObj<ELF64LE>;
 template class elf::LLDDwarfObj<ELF64BE>;