Use OffsetMap in getSectionPiece

[• espindola]

Summary

OffsetMap maps to a SectionPiece index, but we were not taking advantage of that in getSectionPiece.

With this patch both getOffset and getSectionPiece use OffsetMap and the binary search is moved to findSectionPiece.

This is a measurable win (up to 2,2%) in most tests.

[• espindola]

ping

[ruiu]

Sorry, I missed this one. LGTM.

[• espindola]

329044

ELF/InputSection.cpp

while (Size != 1) {
     const It MI = First + H;
     Size -= H;
     First = Comp(Value, *MI) ? First : First + H;
   }
   return Comp(Value, *First) ? First : First + 1;
 }
 
 // Do binary search to get a section piece at a given input offset.
-SectionPiece *MergeInputSection::getSectionPiece(uint64_t Offset) {
-  if (Data.size() <= Offset)
-    fatal(toString(this) + ": entry is past the end of the section");
+static SectionPiece *findSectionPiece(MergeInputSection *Sec, uint64_t Offset) {
+  if (Sec->Data.size() <= Offset)
+    fatal(toString(Sec) + ": entry is past the end of the section");
 
   // Find the element this offset points to.
   auto I = fastUpperBound(
-      Pieces.begin(), Pieces.end(), Offset,
+      Sec->Pieces.begin(), Sec->Pieces.end(), Offset,
       [](const uint64_t &A, const SectionPiece &B) { return A < B.InputOff; });
   --I;
   return &*I;
 }
 
+SectionPiece *MergeInputSection::getSectionPiece(uint64_t Offset) {
+  // Find a piece starting at a given offset.
+  auto It = OffsetMap.find(Offset);
+  if (It != OffsetMap.end())
+    return &Pieces[It->second];
+
+  // If Offset is not at beginning of a section piece, it is not in the map.
+  // In that case we need to search from the original section piece vector.
+  return findSectionPiece(this, Offset);
+}
+
 // Returns the offset in an output section for a given input offset.
 // Because contents of a mergeable section is not contiguous in output,
 // it is not just an addition to a base output offset.
 uint64_t MergeInputSection::getOffset(uint64_t Offset) const {
   if (!Live)
     return 0;
 
   // Find a string starting at a given offset.
   auto It = OffsetMap.find(Offset);
   if (It != OffsetMap.end())
     return Pieces[It->second].OutputOff;
 
   // If Offset is not at beginning of a section piece, it is not in the map.
   // In that case we need to search from the original section piece vector.
-  const SectionPiece &Piece = *getSectionPiece(Offset);
+  const SectionPiece &Piece =
+      *findSectionPiece(const_cast<MergeInputSection *>(this), Offset);
   if (!Piece.Live)
     return 0;
 
   uint64_t Addend = Offset - Piece.InputOff;
   return Piece.OutputOff + Addend;
 }
 
 void MergeInputSection::initOffsetMap() {