[COFF] Reduce the size of Chunk and SectionChunk, NFC

[rnk]

Summary

Reorder the fields in both to use padding more efficiently, and add more
comments on the purpose of the fields.

Replace std::vector<SectionChunk*> AssociativeChildren with a
singly-linked list. This avoids the separate vector allocation to list
associative children, and shrinks the 3 pointers used for the typically
empty vector down to 1.

In the end, this reduces the sum of heap allocations used to link
browser_tests.exe with NO PDB by 13.10%, going from 2,248,728 KB to
1,954,071 KB of heap. These numbers exclude memory mapped files, which
are of course a significant factor in LLD's memory usage.

[rnk]

• Fix -Wreorder

[ruiu]

lld/COFF/Chunks.cpp

47 ↗

(On Diff #192193)

This might be useful but at the same time it looks a bit overly cautious? Perhaps the symbol size is more important but we don't have something like this for them, for example.

[rnk]

lld/COFF/Chunks.cpp

47 ↗

(On Diff #192193)

Well, we don't have checks for symbol size yet. :)

Given that we don't have performance monitoring, I really want people to think hard before they casually add another field to SectionChunk. I wouldn't insist on it if we did, but these types of static_asserts have proven useful in LLVM for preventing size creep.

[ruiu]

lld/COFF/Chunks.cpp

47 ↗

(On Diff #192193)

Then maybe reiterating everything again, how about checking directly with a number like static_assert(sizeof(Chunk) == 48)? This should suffice to prevent making the struct larger by accident.

[rnk]

lld/COFF/Chunks.cpp

47 ↗

(On Diff #192193)

It would be wrong for 32-bit. Rather than trying to express it as math on sizeof(void*), I think the struct makes it clearer. And it helps document hidden members like vptr.

[aganea]

@rnk wrote:
This reduces the total size of all LLD heap allocations by 5.22%

What is the total heap size before/after? What percentage of that heap size is used by Chunks? How many of them do you have?

lld/COFF/Chunks.cpp

79 ↗

(On Diff #192193)

Is std::vector<SectionChunk *>'s implementation guaranteed to be 3 pointers? Wouldn't something like AlignedCharArrayUnion<std::vector<SectionChunk *>> be better? Just wondering.

lld/COFF/Chunks.h

127 ↗

(On Diff #192193)

64-bit for a value that's probably <10 most of the time, seems like an awful waste of space ;-)

If this takes so much memory, it'd be interesting to investigate (in terms of performance and dynamic value range) if some of the pointer members below could be converted to offset / bitfields.

[ruiu]

lld/COFF/Chunks.cpp

47 ↗

(On Diff #192193)

Yeah, but it still feels weird to me to repeat all the members again in a different file just for the purpose of assertion. For 32-bit, we can just set the upper bound like static_assert(sizeof(Chunk) <= 48) where 48 is the size of the struct in 64-bit.

[rnk]

In D59797#1442250, @aganea wrote:

@rnk wrote:
This reduces the total size of all LLD heap allocations by 5.22%

What is the total heap size before/after? What percentage of that heap size is used by Chunks? How many of them do you have?

I used the VS memory profiling tool and used the type view to see the most commonly allocated types. "void" just means allocations whose type wasn't determined, and a lot of it comes from vectors, specifically the new RelocTargets vector @mstorsjo added.

Before:
heap usage: 176,077 KB
type                                    count           size
lld-link.exe!lld::coff::SectionChunk    370,809         71,195,328
void                                    251,990         63,254,440
lld-link.exe!lld::coff::Symbol[]        444,020         24,865,120
lld-link.exe!lld::coff::DefinedRegular  379,729         18,226,992
char[]  249     1,233,585

After:
heap usage: 167,335 KB
type                                   |count          |byte size
---------------------------------------|---------------|-------------
void                                   |251,990        |63,254,440
lld-link.exe!lld::coff::SectionChunk   |370,809        |62,295,912
lld-link.exe!lld::coff::Symbol[]       |444,020        |24,865,120
lld-link.exe!lld::coff::DefinedRegular |379,729        |18,226,992
char[]                                 |249            |1,233,585

5.22% heap usage reduction

[mstorsjo]

In D59797#1442365, @rnk wrote:

I used the VS memory profiling tool and used the type view to see the most commonly allocated types. "void" just means allocations whose type wasn't determined, and a lot of it comes from vectors, specifically the new RelocTargets vector @mstorsjo added.

Since that vector isn't needed at all for x86, I guess it should be possible to skip it altogether there. It'll complicate the code a little bit, and the conditional might cost a little bit of runtime, but that'd give you back a lot as well.

[riccibruno]

lld/COFF/Chunks.h

236 ↗

(On Diff #192193)

I think that llvm::SmallVector<Symbol *, 0> is one pointer smaller, with the drawback that it is limited to 2^32-1 elements.

[rnk]

• replace struct with current size

[rnk]

lld/COFF/Chunks.cpp

47 ↗

(On Diff #192193)

Fair enough. Honestly, writing down all the fields in one place helped me identify the profitable reorderings, but we don't need to commit it.

lld/COFF/Chunks.h

232 ↗

(On Diff #192193)

I'm not sure we need to store this, actually, it's pretty easy to recompute on demand. At the very least, we could shorten the size to 32-bits. I think ~4 billion is a reasonable implementation limit on relocations.

236 ↗

(On Diff #192193)

My plan is to see if I can eliminate it completely, but I wanted to treat it separately once I established that the size of this was important and put a cap on it.

259 ↗

(On Diff #192193)

This, for example, is typically 2-3 elements long: each comdat .text section will have a an assoc pdata and xdata. A singly linked list could suffice instead.

[pcc]

lld/COFF/Chunks.cpp

47 ↗

(On Diff #192193)

I found D59044 (and, to a lesser extent, D59269) by staring at the output of clang with -Xclang -fdump-record-layouts. Maybe it would be worth adding this trick to the documentation somewhere?

[smeenai]

lld/COFF/Chunks.cpp

47 ↗

(On Diff #192193)

The clang static analyzer has a padding checker (https://clang.llvm.org/docs/analyzer/checkers.html#optin-performance-padding), and clang-tools-extra has clang-reorder-fields to automatically reorder fields according to the padding checker's findings. I haven't used those myself, but a coworker had success with them in the past.

[rnk]

• Replace std::vector<> with singly linked list

[rnk]

I added one last size optimization, replacing a std::vector with a forward linked list and a custom iterator for it. PTAL

[rnk]

I think I've addressed all the comments, and I know that @ruiu is currently travelling or recovering from travel to Japan, so I'll go ahead and land this. Feel free to provide post-commit feedback.

[rnk]

• last update

[MaskRay]

this reduces the sum of heap allocations ... These numbers exclude memory mapped files

May I ask how you counted the memory usage minus memory mapped files?

[rnk]

In D59797#1452440, @MaskRay wrote:

this reduces the sum of heap allocations ... These numbers exclude memory mapped files

May I ask how you counted the memory usage minus memory mapped files?

I'm using the Visual Studio memory profiler tool, which I believe just tracks heap allocations. It doesn't look at virtual memory or file mappings at all, it just sums the total size of all active heap allocations. So, it's not a complete picture of memory usage, but it represents the memory that we have the most control over.

lld/trunk/COFF/Chunks.h

 const uint32_t TypeMask = 0x000000E0;
 
 // A Chunk represents a chunk of data that will occupy space in the
 // output (if the resolver chose that). It may or may not be backed by
 // a section of an input file. It could be linker-created data, or
 // doesn't even have actual data (if common or bss).
 class Chunk {
 public:
-  enum Kind { SectionKind, OtherKind };
+  enum Kind : uint8_t { SectionKind, OtherKind };
   Kind kind() const { return ChunkKind; }
   virtual ~Chunk() = default;
 
   // Returns the size of this chunk (even if this is a common or BSS.)
   virtual size_t getSize() const = 0;
 
   // Write this chunk to a mmap'ed file, assuming Buf is pointing to
   // beginning of the file. Because this function may use RVA values
public:
   uint32_t Alignment = 1;
 
   virtual bool isHotPatchable() const { return false; }
 
 protected:
   Chunk(Kind K = OtherKind) : ChunkKind(K) {}
   const Kind ChunkKind;
 
+public:
+  // Whether this section needs to be kept distinct from other sections during
+  // ICF. This is set by the driver using address-significance tables.
+  bool KeepUnique = false;
+
+protected:
   // The RVA of this chunk in the output. The writer sets a value.
   uint64_t RVA = 0;
 
   // The output section for this chunk.
   OutputSection *Out = nullptr;
 
 public:
   // The offset from beginning of the output section. The writer sets a value.
   uint64_t OutputSectionOff = 0;
-
-  // Whether this section needs to be kept distinct from other sections during
-  // ICF. This is set by the driver using address-significance tables.
-  bool KeepUnique = false;
 };
 
 // A chunk corresponding a section of an input file.
 class SectionChunk final : public Chunk {
   // Identical COMDAT Folding feature accesses section internal data.
   friend class ICF;
 
 public:
public:
   }
 
   // Allow iteration over the bodies of this chunk's relocated symbols.
   llvm::iterator_range<symbol_iterator> symbols() const {
     return llvm::make_range(symbol_iterator(File, Relocs.begin()),
                             symbol_iterator(File, Relocs.end()));
   }
 
+  // Single linked list iterator for associated comdat children.
+  class AssociatedIterator
+      : public llvm::iterator_facade_base<
+            AssociatedIterator, std::forward_iterator_tag, SectionChunk> {
+  public:
+    AssociatedIterator() = default;
+    AssociatedIterator(SectionChunk *Head) : Cur(Head) {}
+    AssociatedIterator &operator=(const AssociatedIterator &R) {
+      Cur = R.Cur;
+      return *this;
+    }
+    bool operator==(const AssociatedIterator &R) const { return Cur == R.Cur; }
+    const SectionChunk &operator*() const { return *Cur; }
+    SectionChunk &operator*() { return *Cur; }
+    AssociatedIterator &operator++() {
+      Cur = Cur->AssocChildren;
+      return *this;
+    }
+
+  private:
+    SectionChunk *Cur = nullptr;
+  };
+
   // Allow iteration over the associated child chunks for this section.
-  ArrayRef<SectionChunk *> children() const { return AssocChildren; }
+  llvm::iterator_range<AssociatedIterator> children() const {
+    return llvm::make_range(AssociatedIterator(AssocChildren),
+                            AssociatedIterator(nullptr));
+  }
 
   // The section ID this chunk belongs to in its Obj.
   uint32_t getSectionNumber() const;
 
   ArrayRef<uint8_t> consumeDebugMagic();
 
   static ArrayRef<uint8_t> consumeDebugMagic(ArrayRef<uint8_t> Data,
                                              StringRef SectionName);
 
   static SectionChunk *findByName(ArrayRef<SectionChunk *> Sections,
                                   StringRef Name);
 
   bool isHotPatchable() const override { return File->HotPatchable; }
 
-  // A pointer pointing to a replacement for this chunk.
-  // Initially it points to "this" object. If this chunk is merged
-  // with other chunk by ICF, it points to another chunk,
-  // and this chunk is considered as dead.
-  SectionChunk *Repl;
-
-  // The CRC of the contents as described in the COFF spec 4.5.5.
-  // Auxiliary Format 5: Section Definitions. Used for ICF.
-  uint32_t Checksum = 0;
-
-  const coff_section *Header;
-
   // The file that this chunk was created from.
   ObjFile *File;
 
+  // Pointer to the COFF section header in the input file.
+  const coff_section *Header;
+
   // The COMDAT leader symbol if this is a COMDAT chunk.
   DefinedRegular *Sym = nullptr;
 
-  // The COMDAT selection if this is a COMDAT chunk.
-  llvm::COFF::COMDATType Selection = (llvm::COFF::COMDATType)0;
-
+  // Relocations for this section.
   ArrayRef<coff_relocation> Relocs;
 
+  // The CRC of the contents as described in the COFF spec 4.5.5.
+  // Auxiliary Format 5: Section Definitions. Used for ICF.
+  uint32_t Checksum = 0;
+
   // Used by the garbage collector.
   bool Live;
 
+  // The COMDAT selection if this is a COMDAT chunk.
+  llvm::COFF::COMDATType Selection = (llvm::COFF::COMDATType)0;
+
+  // A pointer pointing to a replacement for this chunk.
+  // Initially it points to "this" object. If this chunk is merged
+  // with other chunk by ICF, it points to another chunk,
+  // and this chunk is considered as dead.
+  SectionChunk *Repl;
+
 private:
   StringRef SectionName;
-  std::vector<SectionChunk *> AssocChildren;
+  SectionChunk *AssocChildren = nullptr;
 
   // Used for ICF (Identical COMDAT Folding)
   void replace(SectionChunk *Other);
   uint32_t Class[2] = {0, 0};
 };
 
 // This class is used to implement an lld-specific feature (not implemented in
 // MSVC) that minimizes the output size by finding string literals sharing tail

lld/trunk/COFF/Chunks.cpp

 using namespace llvm::support::endian;
 using namespace llvm::COFF;
 using llvm::support::ulittle32_t;
 
 namespace lld {
 namespace coff {
 
 SectionChunk::SectionChunk(ObjFile *F, const coff_section *H)
-    : Chunk(SectionKind), Repl(this), Header(H), File(F),
-      Relocs(File->getCOFFObj()->getRelocations(Header)) {
+    : Chunk(SectionKind), File(F), Header(H),
+      Relocs(File->getCOFFObj()->getRelocations(Header)), Repl(this) {
   // Initialize SectionName.
   File->getCOFFObj()->getSectionName(Header, SectionName);
 
   Alignment = Header->getAlignment();
 
   // If linker GC is disabled, every chunk starts out alive.  If linker GC is
   // enabled, treat non-comdat sections as roots. Generally optimized object
   // files will be built with -ffunction-sections or /Gy, so most things worth
   // stripping will be in a comdat.
   Live = !Config->DoGC || !isCOMDAT();
 }
 
+// SectionChunk is one of the most frequently allocated classes, so it is
+// important to keep it as compact as possible. As of this writing, the number
+// below is the size of this class on x64 platforms.
+static_assert(sizeof(SectionChunk) <= 128, "SectionChunk grew unexpectedly");
+
 static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); }
 static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); }
 static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); }
 static void or16(uint8_t *P, uint16_t V) { write16le(P, read16le(P) | V); }
 static void or32(uint8_t *P, uint32_t V) { write32le(P, read32le(P) | V); }
 
 // Verify that given sections are appropriate targets for SECREL
 // relocations. This check is relaxed because unfortunately debug
case ARM64:
       break;
     default:
       llvm_unreachable("unknown machine type");
     }
   }
 }
 
 void SectionChunk::addAssociative(SectionChunk *Child) {
-  AssocChildren.push_back(Child);
+  // Insert this child at the head of the list.
+  assert(Child->AssocChildren == nullptr &&
+         "associated sections cannot have their own associated children");
+  Child->AssocChildren = AssocChildren;
+  AssocChildren = Child;
 }
 
 static uint8_t getBaserelType(const coff_relocation &Rel) {
   switch (Config->Machine) {
   case AMD64:
     if (Rel.Type == IMAGE_REL_AMD64_ADDR64)
       return IMAGE_REL_BASED_DIR64;
     return IMAGE_REL_BASED_ABSOLUTE;

lld/trunk/COFF/ICF.cpp

while (Begin < End) {
     Begin = Mid;
   }
 }
 
 // Returns true if two sections' associative children are equal.
 bool ICF::assocEquals(const SectionChunk *A, const SectionChunk *B) {
   auto ChildClasses = [&](const SectionChunk *SC) {
     std::vector<uint32_t> Classes;
-    for (const SectionChunk *C : SC->children())
-      if (!C->SectionName.startswith(".debug") &&
-          C->SectionName != ".gfids$y" && C->SectionName != ".gljmp$y")
-        Classes.push_back(C->Class[Cnt % 2]);
+    for (const SectionChunk &C : SC->children())
+      if (!C.SectionName.startswith(".debug") &&
+          C.SectionName != ".gfids$y" && C.SectionName != ".gljmp$y")
+        Classes.push_back(C.Class[Cnt % 2]);
     return Classes;
   };
   return ChildClasses(A) == ChildClasses(B);
 }
 
 // Compare "non-moving" part of two sections, namely everything
 // except relocation targets.
 bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {

lld/trunk/COFF/MarkLive.cpp

while (!Worklist.empty()) {
     assert(SC->Live && "We mark as live when pushing onto the worklist!");
 
     // Mark all symbols listed in the relocation table for this section.
     for (Symbol *B : SC->symbols())
       if (B)
         AddSym(B);
 
     // Mark associative sections if any.
-    for (SectionChunk *C : SC->children())
-      Enqueue(C);
+    for (SectionChunk &C : SC->children())
+      Enqueue(&C);
   }
 }
 
 }
 }

llvm/trunk/include/llvm/BinaryFormat/COFF.h

enum RelocationTypesARM64 : unsigned {
   IMAGE_REL_ARM64_TOKEN = 0x000C,
   IMAGE_REL_ARM64_SECTION = 0x000D,
   IMAGE_REL_ARM64_ADDR64 = 0x000E,
   IMAGE_REL_ARM64_BRANCH19 = 0x000F,
   IMAGE_REL_ARM64_BRANCH14 = 0x0010,
   IMAGE_REL_ARM64_REL32 = 0x0011,
 };
 
-enum COMDATType : unsigned {
+enum COMDATType : uint8_t {
   IMAGE_COMDAT_SELECT_NODUPLICATES = 1,
   IMAGE_COMDAT_SELECT_ANY,
   IMAGE_COMDAT_SELECT_SAME_SIZE,
   IMAGE_COMDAT_SELECT_EXACT_MATCH,
   IMAGE_COMDAT_SELECT_ASSOCIATIVE,
   IMAGE_COMDAT_SELECT_LARGEST,
   IMAGE_COMDAT_SELECT_NEWEST
 };