Initialize OffsetMap in a known location

[• espindola]

Summary

This is a small optimization: 3% in clang, probably noise everywhere else.

It is also a bit simpler IMHO.

[ruiu]

ELF/SyntheticSections.cpp

2578–2579

Is the point of this patch to parallelize initOffsetMap?

How many sections do you usually have MS->Sections? I thought it's not many.

Did you try parallelizing initOffsetMap itself? We have a huge number of Pieces, so there might be a large room for parallelization.

[• espindola]

ELF/SyntheticSections.cpp

2578–2579

No, I used a parallelForEach mostly because it is used when splitting the sections and was the parallelism we would get before this patch (via call_once). I benchmarked without threads.

MS->Sections will probably have about one section per file for the common case of a simple string section.

Would you be OK with parallelizing initOffsetMap as a followup?

[ruiu]

ELF/SyntheticSections.cpp

2578–2579

I'm fine with doing it in a follow-up patch, but what I was wondering is something different. I just tried to understand this patch.

If you have to call initOffsetMap after finalizeContents, can you call initOffsetMap from finalizeContents?

[• espindola]

ELF/SyntheticSections.cpp

2578–2579

I can call it from finalizeContens, but there are two versions, one in MergeNoTailSection and one in MergeTailSection. Doing the call in here avoids duplication.

[ruiu]

LGTM

[• espindola]

r328686

ELF/InputSection.h

llvm::CachedHashStringRef getData(size_t I) const {
     return {toStringRef(Data.slice(Begin, End - Begin)), Pieces[I].Hash};
   }
 
   // Returns the SectionPiece at a given input section offset.
   SectionPiece *getSectionPiece(uint64_t Offset);
   const SectionPiece *getSectionPiece(uint64_t Offset) const;
 
   SyntheticSection *getParent() const;
+  void initOffsetMap();
 
 private:
   void splitStrings(ArrayRef<uint8_t> A, size_t Size);
   void splitNonStrings(ArrayRef<uint8_t> A, size_t Size);
 
-  mutable llvm::DenseMap<uint32_t, uint32_t> OffsetMap;
-  mutable llvm::once_flag InitOffsetMap;
+  llvm::DenseMap<uint32_t, uint32_t> OffsetMap;
 
   llvm::DenseSet<uint64_t> LiveOffsets;
 };
 
 struct EhSectionPiece {
   EhSectionPiece(size_t Off, InputSectionBase *Sec, uint32_t Size,
                  unsigned FirstRelocation)
       : InputOff(Off), Sec(Sec), Size(Size), FirstRelocation(FirstRelocation) {}

ELF/InputSection.cpp

 
 // 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;
 
-  // Initialize OffsetMap lazily.
-  llvm::call_once(InitOffsetMap, [&] {
-    OffsetMap.reserve(Pieces.size());
-    for (size_t I = 0; I < Pieces.size(); ++I)
-      OffsetMap[Pieces[I].InputOff] = I;
-  });
-
   // 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);
   if (!Piece.Live)
     return 0;
 
   uint64_t Addend = Offset - Piece.InputOff;
   return Piece.OutputOff + Addend;
 }
 
+void MergeInputSection::initOffsetMap() {
+  OffsetMap.reserve(Pieces.size());
+  for (size_t I = 0; I < Pieces.size(); ++I)
+    OffsetMap[Pieces[I].InputOff] = I;
+}
+
 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);
 template InputSection::InputSection(ObjFile<ELF64BE> &, const ELF64BE::Shdr &,
                                     StringRef);

ELF/SyntheticSections.h

 
 // MergeSyntheticSection is a class that allows us to put mergeable sections
 // with different attributes in a single output sections. To do that
 // we put them into MergeSyntheticSection synthetic input sections which are
 // attached to regular output sections.
 class MergeSyntheticSection : public SyntheticSection {
 public:
   void addSection(MergeInputSection *MS);
+  std::vector<MergeInputSection *> Sections;
 
 protected:
   MergeSyntheticSection(StringRef Name, uint32_t Type, uint64_t Flags,
                         uint32_t Alignment)
       : SyntheticSection(Flags, Type, Alignment, Name) {}
-
-  std::vector<MergeInputSection *> Sections;
 };
 
 class MergeTailSection final : public MergeSyntheticSection {
 public:
   MergeTailSection(StringRef Name, uint32_t Type, uint64_t Flags,
                    uint32_t Alignment);
 
   size_t getSize() const override;

ELF/SyntheticSections.cpp

if (I == MergeSections.end()) {
       I = std::prev(MergeSections.end());
       S = Syn;
       Syn->Entsize = MS->Entsize;
     } else {
       S = nullptr;
     }
     (*I)->addSection(MS);
   }
-  for (auto *MS : MergeSections)
+  for (auto *MS : MergeSections) {
     MS->finalizeContents();
+    parallelForEach(MS->Sections,
+                    [](MergeInputSection *Sec) { Sec->initOffsetMap(); });
+  }
 
   std::vector<InputSectionBase *> &V = InputSections;
   V.erase(std::remove(V.begin(), V.end(), nullptr), V.end());
 }
 
 MipsRldMapSection::MipsRldMapSection()
     : SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, Config->Wordsize,
                        ".rld_map") {}