[ELF] Optimize RelocationSection<ELFT>::writeTo

[MaskRay]

Summary

When linking a 1.2G output (nearly no debug info, 2846621 dynamic relocations) using --threads=8, I measured

9.131462 Total ExecuteLinker
1.449913 Total Write output file
1.445784 Total Write sections
0.657152 Write sections {"detail":".rela.dyn"}

This change decreases the .rela.dyn time to 0.25, leading to 4% speed up in the total time.

• The parallelSort is slow because of expensive r_sym/r_offset computation. Cache the values.
• The iteration is slow. Move r_sym/r_addend computation ahead of time and parallelize it.

With the change, the new encodeDynamicReloc is cheap (0.05s). So don't parallelize it.

[MaskRay]

I have tried a serial radix sort whose performance is similar to the parallel qsort.
It has more code, has an allocation, and needs to sacrifice the D62141 ordering property (the property doesn't matter and can be sacrificed if justified):

// Sort by (!IsRelative,SymIndex). DT_REL[A]COUNT requires us to
// place R_*_RELATIVE first. SymIndex is to improve locality.
if (sort) {
  unsigned num = symTab->getNumSymbols();
  SmallVector<unsigned, 0> cnt(num);
  for (const DynamicReloc &rel : relocs)
    ++cnt[rel.r_sym];
  for (unsigned j = 0, i = 0; i != num; ++i) {
    unsigned t = j + cnt[i];
    cnt[i] = j;
    j = t;
  }
  auto tmp = relocs;
  unsigned j = 0, k = relocs.size();
  for (const DynamicReloc &rel : relocs)
    tmp[cnt[rel.r_sym]++] = rel;

  j = 0;
  for (const DynamicReloc &rel : tmp)
    if (rel.type == target->relativeRel)
      relocs[j++] = rel;
    else
      relocs[--k] = rel;
  std::reverse(relocs.begin() + k, relocs.end());
}

[peter.smith]

No objections from me. It may be worth getting some figures from the lld speed test (https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20171030/498843.html) as well, although I expect they won't show regressions.

Will be out of office for the next couple of weeks so may be a bit slow to respond. I'm happy for others to comment/approve.

lld/ELF/SyntheticSections.h

480

Just thinking about making the enum size uint8_t Not entirely sure it will make a lot of difference in this case, but you may want to reorder some of the fields so that they minimise padding between items. For example addend before r_sym. Kind may also benefit from being last.

[ikudrin]

lld/ELF/SyntheticSections.cpp

1677–1679

Preferably, that should be a method in the DynamicReloc class.

lld/ELF/SyntheticSections.h

480

RelType is uint32_t, so there is no padding. Moving Kind at the end (as well as making it uint8_t) changes nothing as the whole class should be 64-bit aligned and thus is 64-bytes long regardless the changes.

488

I do not personally like optimizations when the meaning of the field is changed in different phases. That makes the code fragile and hard to support.

At least, when addend is updated, kind should be adjusted, or else the object's state becomes inconsistent.

[MaskRay]

address comments

[MaskRay]

lld/ELF/SyntheticSections.h

480

Dropped the change to Kind.

Moved type before r_sym because r_offset/r_sym/type/addend layout is more similar to Elf64_Rela.

[ikudrin]

lld/ELF/SyntheticSections.cpp

1668

And now we have an inconsistency if kind was AddendOnlyWithTargetVA or AgainstSymbolWithTargetVA because sym is not nullptr and an assert() in computeAddend() can trigger. Maybe add a new kind PostComputeRaw and add asserts to computeAddend() and needsDynSymIndex() to ensure that they are not called after computeRaw()?

[MaskRay]

lld/ELF/SyntheticSections.cpp

1668

Every redundant operation costs. We have comprehensive tests so I do not worry much about inconsistency caused problems. Adding PostComputeRaw seems to sacrifice too much for the check.

[ikudrin]

LGTM

[MaskRay]

Thanks:)

[arichardson]

This looks like a nice improvement to me. I also like @ikudrin's suggestion of validating internal consistency in debug builds, but if this has a measurable performance impact the current patch LGTM.

lld/ELF/SyntheticSections.cpp

1668

Not sure if that makes any difference in a release build since we already have the store in computeRaw().
One thing that might also make it more resilient to bugs introduced while refactoring (or to help modified downstream consumers with less comprehensive test coverage) would be to keep the addend field private and add a r_addend() accessor that asserts that we are in the PostComputeRaw/ContentsFinalized/SomeOtherName state.

1771–1775

Does it make sense to also parallelize this or is this not meaningful for the relocation counts encountered in practise?

lld/ELF/OutputSections.cpp

parallelForEachN(0, sections.size(), [&](size_t i) {
     // When linking with -r or --emit-relocs we might also call this function
     // for input .rel[a].<sec> sections which we simply pass through to the
     // output. We skip over those and only look at the synthetic relocation
     // sections created during linking.
     const auto *sec = dyn_cast<RelocationBaseSection>(sections[i]);
     if (!sec)
       return;
     for (const DynamicReloc &rel : sec->relocs) {
-      int64_t addend = rel.computeAddend();
+      int64_t addend = rel.addend;
       const OutputSection *relOsec = rel.inputSec->getOutputSection();
       assert(relOsec != nullptr && "missing output section for relocation");
       const uint8_t *relocTarget =
           bufStart + relOsec->offset + rel.inputSec->getOffset(rel.offsetInSec);
       // For SHT_NOBITS the written addend is always zero.
       int64_t writtenAddend =
           relOsec->type == SHT_NOBITS
               ? 0

lld/ELF/SyntheticSections.h

private:
   uint64_t size = 0;
 
   llvm::DenseMap<StringRef, unsigned> stringMap;
   SmallVector<StringRef, 0> strings;
 };
 
 class DynamicReloc {
 public:
-  enum Kind {
+  enum Kind : uint8_t {
     /// The resulting dynamic relocation does not reference a symbol (#sym must
     /// be nullptr) and uses #addend as the result of computeAddend().
     AddendOnly,
     /// The resulting dynamic relocation will not reference a symbol: #sym is
     /// only used to compute the addend with InputSection::getRelocTargetVA().
     /// Useful for various relative and TLS relocations (e.g. R_X86_64_TPOFF64).
     AddendOnlyWithTargetVA,
     /// The resulting dynamic relocation references symbol #sym from the dynamic
     /// symbol table and uses #addend as the value of computeAddend().
     AgainstSymbol,
     /// The resulting dynamic relocation references symbol #sym from the dynamic
     /// symbol table and uses InputSection::getRelocTargetVA() + #addend for the
     /// final addend. It can be used for relocations that write the symbol VA as
     // the addend (e.g. R_MIPS_TLS_TPREL64) but still reference the symbol.
     AgainstSymbolWithTargetVA,
     /// This is used by the MIPS multi-GOT implementation. It relocates
     /// addresses of 64kb pages that lie inside the output section.
     MipsMultiGotPage,
   };
   /// This constructor records a relocation against a symbol.
   DynamicReloc(RelType type, const InputSectionBase *inputSec,
                uint64_t offsetInSec, Kind kind, Symbol &sym, int64_t addend,
                RelExpr expr)
-      : type(type), sym(&sym), inputSec(inputSec), offsetInSec(offsetInSec),
-        kind(kind), expr(expr), addend(addend) {}
+      : sym(&sym), inputSec(inputSec), offsetInSec(offsetInSec), type(type),
+        addend(addend), kind(kind), expr(expr) {}
   /// This constructor records a relative relocation with no symbol.
   DynamicReloc(RelType type, const InputSectionBase *inputSec,
                uint64_t offsetInSec, int64_t addend = 0)
-      : type(type), sym(nullptr), inputSec(inputSec), offsetInSec(offsetInSec),
-        kind(AddendOnly), expr(R_ADDEND), addend(addend) {}
+      : sym(nullptr), inputSec(inputSec), offsetInSec(offsetInSec), type(type),
+        addend(addend), kind(AddendOnly), expr(R_ADDEND) {}
   /// This constructor records dynamic relocation settings used by the MIPS
   /// multi-GOT implementation.
   DynamicReloc(RelType type, const InputSectionBase *inputSec,
                uint64_t offsetInSec, const OutputSection *outputSec,
                int64_t addend)
-      : type(type), sym(nullptr), inputSec(inputSec), offsetInSec(offsetInSec),
-        kind(MipsMultiGotPage), expr(R_ADDEND), addend(addend),
-        outputSec(outputSec) {}
+      : sym(nullptr), outputSec(outputSec), inputSec(inputSec),
+        offsetInSec(offsetInSec), type(type), addend(addend),
+        kind(MipsMultiGotPage), expr(R_ADDEND) {}
 
   uint64_t getOffset() const;
   uint32_t getSymIndex(SymbolTableBaseSection *symTab) const;
   bool needsDynSymIndex() const {
     return kind == AgainstSymbol || kind == AgainstSymbolWithTargetVA;
   }
 
   /// Computes the addend of the dynamic relocation. Note that this is not the
   /// same as the #addend member variable as it may also include the symbol
   /// address/the address of the corresponding GOT entry/etc.
   int64_t computeAddend() const;
 
-  RelType type;
   Symbol *sym;
+  const OutputSection *outputSec = nullptr;
   const InputSectionBase *inputSec;
   uint64_t offsetInSec;
+  uint64_t r_offset;
+  uint32_t r_sym;
+  RelType type;
+  // Initially input addend, then the output addend after
+  // RelocationSection<ELFT>::writeTo.
+  int64_t addend;
 
 private:
   Kind kind;
   // The kind of expression used to calculate the added (required e.g. for
   // relative GOT relocations).
   RelExpr expr;
-  int64_t addend;
-  const OutputSection *outputSec = nullptr;
 };
 
 template <class ELFT> class DynamicSection final : public SyntheticSection {
   LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)
 
 public:
   DynamicSection();
   void finalizeContents() override;

lld/ELF/SyntheticSections.cpp

 }
 
 RelrBaseSection::RelrBaseSection()
     : SyntheticSection(SHF_ALLOC,
                        config->useAndroidRelrTags ? SHT_ANDROID_RELR : SHT_RELR,
                        config->wordsize, ".relr.dyn") {}
 
 template <class ELFT>
-static void encodeDynamicReloc(SymbolTableBaseSection *symTab,
-                               typename ELFT::Rela *p,
+static void encodeDynamicReloc(typename ELFT::Rela *p,
                                const DynamicReloc &rel) {
+  p->r_offset = rel.r_offset;
+  p->setSymbolAndType(rel.r_sym, rel.type, config->isMips64EL);
   if (config->isRela)
-    p->r_addend = rel.computeAddend();
-  p->r_offset = rel.getOffset();
-  p->setSymbolAndType(rel.getSymIndex(symTab), rel.type, config->isMips64EL);
+    p->r_addend = rel.addend;
 }
 
 template <class ELFT>
 RelocationSection<ELFT>::RelocationSection(StringRef name, bool sort)
     : RelocationBaseSection(name, config->isRela ? SHT_RELA : SHT_REL,
                             config->isRela ? DT_RELA : DT_REL,
                             config->isRela ? DT_RELASZ : DT_RELSZ),
       sort(sort) {
   this->entsize = config->isRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
 }
 
 template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *buf) {
   SymbolTableBaseSection *symTab = getPartition().dynSymTab;
 
+  parallelForEach(relocs, [symTab](DynamicReloc &rel) {
+    rel.addend = rel.computeAddend();
+    rel.r_offset = rel.getOffset();
+    rel.r_sym = rel.getSymIndex(symTab);
+  });
   // Sort by (!IsRelative,SymIndex,r_offset). DT_REL[A]COUNT requires us to
   // place R_*_RELATIVE first. SymIndex is to improve locality, while r_offset
   // is to make results easier to read.
-  if (sort)
-    parallelSort(
-        relocs, [&](const DynamicReloc &a, const DynamicReloc &b) {
-          return std::make_tuple(a.type != target->relativeRel,
-                                 a.getSymIndex(symTab), a.getOffset()) <
-                 std::make_tuple(b.type != target->relativeRel,
-                                 b.getSymIndex(symTab), b.getOffset());
-        });
+  if (sort) {
+    const RelType relativeRel = target->relativeRel;
+    parallelSort(relocs, [&](const DynamicReloc &a, const DynamicReloc &b) {
+      return std::make_tuple(a.type != relativeRel, a.r_sym, a.r_offset) <
+             std::make_tuple(b.type != relativeRel, b.r_sym, b.r_offset);
+  }
 
   for (const DynamicReloc &rel : relocs) {
-    encodeDynamicReloc<ELFT>(symTab, reinterpret_cast<Elf_Rela *>(buf), rel);
+    encodeDynamicReloc<ELFT>(reinterpret_cast<Elf_Rela *>(buf), rel);
     buf += config->isRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
   }
 }
 
 template <class ELFT>
 AndroidPackedRelocationSection<ELFT>::AndroidPackedRelocationSection(
     StringRef name)
     : RelocationBaseSection(
bool AndroidPackedRelocationSection<ELFT>::updateAllocSize() {
   // perform the initial adjustment).
   add(relocs.size());
   add(0);
 
   std::vector<Elf_Rela> relatives, nonRelatives;
 
   for (const DynamicReloc &rel : relocs) {
     Elf_Rela r;
-    encodeDynamicReloc<ELFT>(getPartition().dynSymTab, &r, rel);
+    r.r_offset = rel.getOffset();
+    r.setSymbolAndType(rel.getSymIndex(getPartition().dynSymTab), rel.type,
+                       false);
+    if (config->isRela)
+      r.r_addend = rel.computeAddend();
 
     if (r.getType(config->isMips64EL) == target->relativeRel)
       relatives.push_back(r);
     else
       nonRelatives.push_back(r);
   }
 
   llvm::sort(relatives, [](const Elf_Rel &a, const Elf_Rel &b) {