[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

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

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

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

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

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

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

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

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

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

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

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

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

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

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/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:
   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;
 
-  // Used by the garbage collector.
-  bool Live;
-
   // When inserting a thunk, we need to adjust a relocation to point to
   // the thunk instead of the actual original target Symbol.
   std::vector<Symbol *> RelocTargets;
 
+  // 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;
+
+  // Indicates whether the section should be included in the output file.
+  // Sections may become dead if the garbage collector discards them, if ICF
+  // replaces them, or if they are associated with a non-prevailing comdat
+  // section.
+  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;
 
   // 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/COFF/Chunks.cpp

SectionChunk::SectionChunk(ObjFile *F, const coff_section *H)
 
   // 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();
 }
 
+namespace {
+// This class exists just for the purpose of calculating the expected size of
+// Chunk.
+struct ChunkFields {
+  uintptr_t VPtr;
+  uint32_t Alignment;
+  uint8_t ChunkKind;
+  bool KeepUnique;
+  uint64_t RVA;
+  uintptr_t Out;
+  uint64_t OutputSectionOff;
+};
+
+// Chunk is one of the most frequently allocated classes, so it is important to
+// keep it as compact as possible.
+static_assert(sizeof(Chunk) == sizeof(ChunkFields),
+              "Chunk grew unexpectedly");
+
+// This class exists just for the purpose of calculating the expected size of
+// SectionChunk.
+struct SectionChunkFields {
+  ChunkFields ChunkBase;
+  uintptr_t File;
+  uintptr_t Header;
+  uintptr_t Sym;
+  uintptr_t Relocs[2];
+  uintptr_t RelocTargets[3];
+  uint32_t Checksum;
+  bool Live;
+  uint8_t Selection;
+  uintptr_t Repl;
+  uintptr_t SectionName[2];
+  uintptr_t AssocChildren[3];
+  uint32_t Class[2];
+};
+
+// SectionChunk is one of the most frequently allocated classes, so it is
+// important to keep it as compact as possible.
+static_assert(sizeof(SectionChunk) == sizeof(SectionChunkFields),
+              "SectionChunk grew unexpectedly");
+} // namespace
+
 // Initialize the RelocTargets vector, to allow redirecting certain relocations
 // to a thunk instead of the actual symbol the relocation's symbol table index
 // indicates.
 void SectionChunk::readRelocTargets() {
   assert(RelocTargets.empty());
   RelocTargets.reserve(Relocs.size());
   for (const coff_relocation &Rel : Relocs)
     RelocTargets.push_back(File->getSymbol(Rel.SymbolTableIndex));

llvm/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
 };