Split SectionPiece in its parts

[• espindola]

Summary

More testing in an oldish xeon shows that almost half of the time in the getOffset method is because of one memory access, the one fetching OutputOff in

return Pieces[It->second].OutputOff;

putting all the OutputOff in a single vector improves it.

[• espindola]

Benchmark on a i7-7567U

[smeenai]

Patch is missing context.

[• espindola]

now with context.

[• espindola]

Results on a

E5-2697 v2

[• espindola]

Have the OutputOffsets store just a uint64_t. This uses a bit of the hash for the live bit.

With this there is nothing to do after the load other that return the value, which should allow pipelining the relocation loop.

ELF/InputSection.h

 };
 
 // SectionPiece represents a piece of splittable section contents.
 // We allocate a lot of these and binary search on them. This means that they
 // have to be as compact as possible, which is why we don't store the size (can
 // be found by looking at the next one).
 struct SectionPiece {
   SectionPiece(size_t Off, uint32_t Hash, bool Live)
-      : InputOff(Off), Hash(Hash), OutputOff(0),
-        Live(Live || !Config->GcSections) {}
+      : InputOff(Off), Hash(Hash >> 1), Live(Live || !Config->GcSections) {}
 
   uint32_t InputOff;
-  uint32_t Hash;
-  int64_t OutputOff : 63;
-  uint64_t Live : 1;
+  uint32_t Hash : 31;
+  uint32_t Live : 1;
 };
 
-static_assert(sizeof(SectionPiece) == 16, "SectionPiece is too big");
+static_assert(sizeof(SectionPiece) == 8, "SectionPiece is too big");
 
 // This corresponds to a SHF_MERGE section of an input file.
 class MergeInputSection : public InputSectionBase {
 public:
   template <class ELFT>
   MergeInputSection(ObjFile<ELFT> &F, const typename ELFT::Shdr &Header,
                     StringRef Name);
   MergeInputSection(uint64_t Flags, uint32_t Type, uint64_t Entsize,
public:
 
   // Translate an offset in the input section to an offset in the parent
   // MergeSyntheticSection.
   uint64_t getParentOffset(uint64_t Offset) const;
 
   // Splittable sections are handled as a sequence of data
   // rather than a single large blob of data.
   std::vector<SectionPiece> Pieces;
+  std::vector<uint64_t> OutputOffsets;
   llvm::DenseMap<uint32_t, uint32_t> OffsetMap;
 
   // Returns I'th piece's data. This function is very hot when
   // string merging is enabled, so we want to inline.
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   llvm::CachedHashStringRef getData(size_t I) const {
     size_t Begin = Pieces[I].InputOff;
     size_t End =

ELF/InputSection.cpp

void MergeInputSection::splitIntoPieces() {
   assert(Pieces.empty());
 
   if (Flags & SHF_STRINGS)
     splitStrings(Data, Entsize);
   else
     splitNonStrings(Data, Entsize);
 
   OffsetMap.reserve(Pieces.size());
+  OutputOffsets.resize(Pieces.size());
   for (size_t I = 0, E = Pieces.size(); I != E; ++I)
     OffsetMap[Pieces[I].InputOff] = I;
 
   if (Config->GcSections && (Flags & SHF_ALLOC))
     for (uint32_t Off : LiveOffsets)
       getSectionPiece(Off)->Live = true;
 }
 
 template <class It, class T, class Compare>
 static It fastUpperBound(It First, It Last, const T &Value, Compare Comp) {
   size_t Size = std::distance(First, Last);
   assert(Size != 0);
   while (Size != 1) {
     size_t H = Size / 2;
     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.
-static SectionPiece *findSectionPiece(MergeInputSection *Sec, uint64_t Offset) {
+static int findSectionPieceIndex(const 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(
       Sec->Pieces.begin(), Sec->Pieces.end(), Offset,
       [](const uint64_t &A, const SectionPiece &B) { return A < B.InputOff; });
   --I;
-  return &*I;
+  return std::distance(Sec->Pieces.begin(), 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);
+  return &Pieces[findSectionPieceIndex(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::getParentOffset(uint64_t Offset) const {
   // Find a string starting at a given offset.
   auto It = OffsetMap.find(Offset);
   if (It != OffsetMap.end())
-    return Pieces[It->second].OutputOff;
+    return OutputOffsets[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.
-  const SectionPiece &Piece =
-      *findSectionPiece(const_cast<MergeInputSection *>(this), Offset);
-  uint64_t Addend = Offset - Piece.InputOff;
-  return Piece.OutputOff + Addend;
+  int Index = findSectionPieceIndex(this, Offset);
+  uint64_t Addend = Offset - Pieces[Index].InputOff;
+  return OutputOffsets[Index] + Addend;
 }
 
 template InputSection::InputSection(ObjFile<ELF32LE> &, const ELF32LE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF32BE> &, const ELF32BE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF64LE> &, const ELF64LE::Shdr &,
                                     StringRef);

ELF/SyntheticSections.h

 
 private:
   // We use the most significant bits of a hash as a shard ID.
   // The reason why we don't want to use the least significant bits is
   // because DenseMap also uses lower bits to determine a bucket ID.
   // If we use lower bits, it significantly increases the probability of
   // hash collisons.
   size_t getShardId(uint32_t Hash) {
-    return Hash >> (32 - llvm::countTrailingZeros(NumShards));
+    assert((Hash & (1 << 31)) == 0);
+    return Hash >> (31 - llvm::countTrailingZeros(NumShards));
   }
 
   // Section size
   size_t Size;
 
   // String table contents
   constexpr static size_t NumShards = 32;
   std::vector<llvm::StringTableBuilder> Shards;

ELF/SyntheticSections.cpp

void MergeTailSection::finalizeContents() {
   Builder.finalize();
 
   // finalize() fixed tail-optimized strings, so we can now get
   // offsets of strings. Get an offset for each string and save it
   // to a corresponding StringPiece for easy access.
   for (MergeInputSection *Sec : Sections)
     for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
       if (Sec->Pieces[I].Live)
-        Sec->Pieces[I].OutputOff = Builder.getOffset(Sec->getData(I));
+        Sec->OutputOffsets[I] = Builder.getOffset(Sec->getData(I));
 }
 
 void MergeNoTailSection::writeTo(uint8_t *Buf) {
   for (size_t I = 0; I < NumShards; ++I)
     Shards[I].write(Buf + ShardOffsets[I]);
 }
 
 // This function is very hot (i.e. it can take several seconds to finish)
Concurrency =
         std::min<size_t>(PowerOf2Floor(hardware_concurrency()), NumShards);
 
   // Add section pieces to the builders.
   parallelForEachN(0, Concurrency, [&](size_t ThreadId) {
     for (MergeInputSection *Sec : Sections) {
       for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I) {
         size_t ShardId = getShardId(Sec->Pieces[I].Hash);
         if ((ShardId & (Concurrency - 1)) == ThreadId && Sec->Pieces[I].Live)
-          Sec->Pieces[I].OutputOff = Shards[ShardId].add(Sec->getData(I));
+          Sec->OutputOffsets[I] = Shards[ShardId].add(Sec->getData(I));
       }
     }
   });
 
   // Compute an in-section offset for each shard.
   size_t Off = 0;
   for (size_t I = 0; I < NumShards; ++I) {
     Shards[I].finalizeInOrder();
     if (Shards[I].getSize() > 0)
       Off = alignTo(Off, Alignment);
     ShardOffsets[I] = Off;
     Off += Shards[I].getSize();
   }
   Size = Off;
 
   // So far, section pieces have offsets from beginning of shards, but
   // we want offsets from beginning of the whole section. Fix them.
   parallelForEach(Sections, [&](MergeInputSection *Sec) {
     for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
       if (Sec->Pieces[I].Live)
-        Sec->Pieces[I].OutputOff +=
-            ShardOffsets[getShardId(Sec->Pieces[I].Hash)];
+        Sec->OutputOffsets[I] += ShardOffsets[getShardId(Sec->Pieces[I].Hash)];
   });
 }
 
 static MergeSyntheticSection *createMergeSynthetic(StringRef Name,
                                                    uint32_t Type,
                                                    uint64_t Flags,
                                                    uint32_t Alignment) {
   bool ShouldTailMerge = (Flags & SHF_STRINGS) && Config->Optimize >= 2;