Binary search to find a relocation.

[ruiu]

Summary

This change makes -gdb-index 40% faster. My test case is self-linking lld.

[grimar]

I though about that, but it is assuming that relocations are sorted by offset.
Can we really rely on that ?

lld/trunk/ELF/GdbIndex.cpp

 // 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())
+  auto It = std::lower_bound(
+      Rels.begin(), Rels.end(), Pos,
+      [](const RelTy &A, uint64_t B) { return A.r_offset < B; });
+  if (It == Rels.end() || It->r_offset != Pos)
     return None;
-  const RelTy &Rel = *I;
+  const RelTy &Rel = *It;
+
   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);