Parallelize tail-merge string table construction.

[ruiu]

Summary

This patch parallelizes MergeTailSection just like I did to
MergeNoTailSection in r314588.

On my 2-socket 20-core 40-threads Xeon E5-2680 @ 2.8 GHz machine,
this patch shortens the clang debug build link time with -O2 from
11.35s to 5.72s. Without -O2, it's 5.23s, so the overhead of -O2 is
now about a half second in this test environment.

[ruiu]

• Embed TailHash into SectionPiece

[ruiu]

Ping. What do you think of this?

[ruiu]

I forgot this patch, but I'd like to get this in. Can you review?

[inglorion]

lld/ELF/SyntheticSections.cpp

2276

What if you did the equivalent of:

size_t N = std::min(4, S.size());
uint32_t X = 0;
memcpy(&X, S.data() + S.size() - N, N);
return hash_value(X);

That would allow you to handle strings of any length and should be super efficient.

If you need the hash to not depend on the endianness of the host you could use ulittle32_t, but I think in this case you don't need to care what the actual values produced by the hash function are so ignoring endianness seems fine.

[ruiu]

• rebased

[grimar]

It is a bit unclear to me which test you want to change to show the effect of this patch.
I.e. I would expect either adding one new test or modifying one of the
existent, but you change the 3 tests here and it is a bit confusing IMO.

Also, since this patch really has an old base (you posted it in 2017),
do you think it is worth to update its description with fresh numbers?

lld/ELF/SyntheticSections.cpp

2289

nit: I might be mistaken, but I think here you need a comma: "Currently" -> "Currently, "

lld/ELF/SyntheticSections.h

672

nit: no full stop at the end of the comment.

[ruiu]

This patch naturally changes the order how strings are placed in a merged string section. In addition to that, with this change, strings equal to or shorter than 4 bytes long are not merged. This is why.

Assume we have two string, "cd" and "abcd". They have the same tail.

Since we use a hash value of the last 4 characters of each string as a shard ID, we compute two hashes, H1=hash_vaule("cd") and H2=hash_value("abcd"). It is unlikely that H1==H2 because they are just different strings. Therefore, it is likely that "cd" and "abcd" are added to different shards, and they are not merged.

Due to the above behavior, I needed to make the strings used in the test little longer, as otherwise they wouldn't have been merged at all.

[ruiu]

• address review comments
• simplify

[ruiu]

lld/ELF/SyntheticSections.cpp

2276

After simplifying this function it became too short, so I inlined the function.

[ruiu]

• 80 columns

[grimar]

Thanks for the explanation! Two more comments/questions below.

lld/ELF/InputSection.h

223

Seems you could store ShardID : 5 here instead of TailHash.
That would save a few bits for OutputOff and you can get rid of computations in the code.
Does it make sense?

lld/ELF/SyntheticSections.cpp

2285

Not only when -O2, but actually -On, where n >= 2.

[ruiu]

• rebased
• instead of storing a tail hash, directly store shard-id to SectionPieces

lld/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) and put the hash in a side table.
 struct SectionPiece {
   SectionPiece(size_t Off, uint32_t Hash, bool Live)
-      : InputOff(Off), Hash(Hash), OutputOff(-1),
-        Live(Live || !Config->GcSections) {}
+      : InputOff(Off), Hash(Hash), Live(Live || !Config->GcSections),
+        TailHash(0), OutputOff(-1) {}
 
   uint32_t InputOff;
   uint32_t Hash;
-  uint64_t OutputOff : 63;
   uint64_t Live : 1;
+  uint64_t TailHash : 10;
+  uint64_t OutputOff : 53;
 };
 
 static_assert(sizeof(SectionPiece) == 16, "SectionPiece is too big");
 
 // This corresponds to a SHF_MERGE section of an input file.
 class MergeInputSection : public InputSectionBase {
 public:
   template <class ELFT>

lld/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);
+  size_t getSize() const override { return Size; }
+  void writeTo(uint8_t *Buf) override;
 
 protected:
   MergeSyntheticSection(StringRef Name, uint32_t Type, uint64_t Flags,
-                        uint32_t Alignment)
-      : SyntheticSection(Flags, Type, Alignment, Name) {}
+                        uint32_t Alignment);
 
   std::vector<MergeInputSection *> Sections;
+
+  // Section size
+  size_t Size;
+
+  // Concurrency level.
+  size_t Concurrency;
+
+  // String table contents
+  constexpr static size_t NumShards = 32;
+  std::vector<llvm::StringTableBuilder> Shards;
+  size_t ShardOffsets[NumShards];
 };
 
 class MergeTailSection final : public MergeSyntheticSection {
 public:
   MergeTailSection(StringRef Name, uint32_t Type, uint64_t Flags,
-                   uint32_t Alignment);
-
-  size_t getSize() const override;
-  void writeTo(uint8_t *Buf) override;
+                   uint32_t Alignment)
+      : MergeSyntheticSection(Name, Type, Flags, Alignment) {}
   void finalizeContents() override;
-
-private:
-  llvm::StringTableBuilder Builder;
 };
 
 class MergeNoTailSection final : public MergeSyntheticSection {
 public:
   MergeNoTailSection(StringRef Name, uint32_t Type, uint64_t Flags,
                      uint32_t Alignment)
       : MergeSyntheticSection(Name, Type, Flags, Alignment) {}
-
-  size_t getSize() const override { return Size; }
-  void writeTo(uint8_t *Buf) override;
   void finalizeContents() override;
 
 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));
   }
-
-  // Section size
-  size_t Size;
-
-  // String table contents
-  constexpr static size_t NumShards = 32;
-  std::vector<llvm::StringTableBuilder> Shards;
-  size_t ShardOffsets[NumShards];
 };
 
 // .MIPS.abiflags section.
 template <class ELFT>
 class MipsAbiFlagsSection final : public SyntheticSection {
   typedef llvm::object::Elf_Mips_ABIFlags<ELFT> Elf_Mips_ABIFlags;
 
 public:

lld/ELF/SyntheticSections.cpp

 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support;
 using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
-constexpr size_t MergeNoTailSection::NumShards;
+constexpr size_t MergeSyntheticSection::NumShards;
 
 uint64_t SyntheticSection::getVA() const {
   if (OutputSection *Sec = getParent())
     return Sec->Addr + OutSecOff;
   return 0;
 }
 
 // Create a .bss section for each common symbol and replace the common symbol
for (const std::pair<SharedFile<ELFT> *, size_t> &P : Needed)
     Size += P.first->VerdefMap.size() * sizeof(Elf_Vernaux);
   return Size;
 }
 
 template <class ELFT> bool VersionNeedSection<ELFT>::empty() const {
   return getNeedNum() == 0;
 }
 
-void MergeSyntheticSection::addSection(MergeInputSection *MS) {
-  MS->Parent = this;
-  Sections.push_back(MS);
-}
-
-MergeTailSection::MergeTailSection(StringRef Name, uint32_t Type,
+MergeSyntheticSection::MergeSyntheticSection(StringRef Name, uint32_t Type,
                                              uint64_t Flags, uint32_t Alignment)
-    : MergeSyntheticSection(Name, Type, Flags, Alignment),
-      Builder(StringTableBuilder::RAW, Alignment) {}
-
-size_t MergeTailSection::getSize() const { return Builder.getSize(); }
-
-void MergeTailSection::writeTo(uint8_t *Buf) { Builder.write(Buf); }
-
-void MergeTailSection::finalizeContents() {
-  // Add all string pieces to the string table builder to create section
-  // contents.
-  for (MergeInputSection *Sec : Sections)
-    for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
-      if (Sec->Pieces[I].Live)
-        Builder.add(Sec->getData(I));
+    : SyntheticSection(Flags, Type, Alignment, Name) {
+  // Initialize string builders.
+  for (size_t I = 0; I < NumShards; ++I)
+    Shards.emplace_back(StringTableBuilder::RAW, Alignment);
 
-  // Fix the string table content. After this, the contents will never change.
-  Builder.finalize();
+  // Initializes concurrency level. Must be a power of 2 to avoid
+  // the expensive modulo operation when dividing with this value.
+  if (ThreadsEnabled)
+    Concurrency =
+        std::min<size_t>(PowerOf2Floor(hardware_concurrency()), NumShards);
+  else
+    Concurrency = 1;
+}
 
-  // 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));
+void MergeSyntheticSection::addSection(MergeInputSection *MS) {
+  MS->Parent = this;
+  Sections.push_back(MS);
 }
 
-void MergeNoTailSection::writeTo(uint8_t *Buf) {
+void MergeSyntheticSection::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)
 // because sometimes the number of inputs is in an order of magnitude of
 // millions. So, we use multi-threading.
 //
 // For any strings S and T, we know S is not mergeable with T if S's hash
 // value is different from T's. If that's the case, we can safely put S and
 // T into different string builders without worrying about merge misses.
 // We do it in parallel.
 void MergeNoTailSection::finalizeContents() {
-  // Initializes string table builders.
-  for (size_t I = 0; I < NumShards; ++I)
-    Shards.emplace_back(StringTableBuilder::RAW, Alignment);
-
-  // Concurrency level. Must be a power of 2 to avoid expensive modulo
-  // operations in the following tight loop.
-  size_t Concurrency = 1;
-  if (ThreadsEnabled)
-    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) {
         if (!Sec->Pieces[I].Live)
           continue;
         size_t ShardId = getShardId(Sec->Pieces[I].Hash);
         if ((ShardId & (Concurrency - 1)) == ThreadId)
void MergeNoTailSection::finalizeContents() {
   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)];
   });
 }
 
+static uint32_t tailHash(StringRef S) {
+  if (S.size() < 4)
+    return 0;
+  const uint8_t *P = (const uint8_t *)S.data() + S.size();
+  return hash_value((P[-4] << 24) | (P[-3] << 16) | (P[-2] << 8) | P[-1]);
+}
+
+// This function basically does the same thing as MergeNoTailSection
+// does but creates a tail-merged string table. E.g. "def\0" is merged
+// with "abcdef\0". This is enabled only when -O2 is given.
+//
+// Input strings are sharded based on their very last few characters.
+// This works because, if strings S and T can be tail-merged, S and T
+// must have the same tail substring. Currently we use the last 4
+// characters for sharding.
+//
+// Note that strings shorter than 4 characters may not be tail-merged.
+// That is okay because the loss seems negligible. My observation is
+// that a loss is 8 KiB when we create a 1.7 GiB clang executable.
+void MergeTailSection::finalizeContents() {
+  // Initializes TailHashes by hash values of last few characters.
+  parallelForEach(Sections, [&](MergeInputSection *Sec) {
+    for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
+      if (Sec->Pieces[I].Live)
+        Sec->Pieces[I].TailHash = tailHash(Sec->getData(I).val());
+  });
+
+  // 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) {
+        if (!Sec->Pieces[I].Live)
+          continue;
+        size_t ShardId = Sec->Pieces[I].TailHash % NumShards;
+        if ((ShardId & (Concurrency - 1)) == ThreadId)
+          Shards[ShardId].add(Sec->getData(I));
+      }
+    }
+  });
+
+  parallelForEach(Shards, [](StringTableBuilder &S) { S.finalize(); });
+
+  // Compute an in-section offset for each shard.
+  size_t Off = 0;
+  for (size_t I = 0; I < NumShards; ++I) {
+    if (Shards[I].getSize() > 0)
+      Off = alignTo(Off, Alignment);
+    ShardOffsets[I] = Off;
+    Off += Shards[I].getSize();
+  }
+  Size = Off;
+
+  // Set to section piece offsets.
+  parallelForEach(Sections, [&](MergeInputSection *Sec) {
+    for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I) {
+      if (!Sec->Pieces[I].Live)
+        continue;
+      size_t ShardId = Sec->Pieces[I].TailHash % NumShards;
+      Sec->Pieces[I].OutputOff =
+          ShardOffsets[ShardId] + Shards[ShardId].getOffset(Sec->getData(I));
+    }
+  });
+}
+
 static MergeSyntheticSection *createMergeSynthetic(StringRef Name,
                                                    uint32_t Type,
                                                    uint64_t Flags,
                                                    uint32_t Alignment) {
   bool ShouldTailMerge = (Flags & SHF_STRINGS) && Config->Optimize >= 2;
   if (ShouldTailMerge)
     return make<MergeTailSection>(Name, Type, Flags, Alignment);
   return make<MergeNoTailSection>(Name, Type, Flags, Alignment);

lld/test/ELF/merge-shared-str.s

 // REQUIRES: x86
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
-// RUN: ld.lld %t.o -o %t.so -shared -O3
+// RUN: ld.lld %t.o -o %t.so -shared -O2
 // RUN: llvm-readobj -r -s %t.so | FileCheck %s
 
-
-        .section        foo,"aMS",@progbits,1
-        .asciz "bar"
-        .asciz "ar"
+.section foo,"aMS",@progbits,1
+.asciz "foobarbaz"
+.asciz "barbaz"
 
-        .data
-        .quad foo + 4
-
+.quad foo + 11
 
 // CHECK:      Name: foo
 // CHECK-NEXT: Type: SHT_PROGBITS
 // CHECK-NEXT: Flags [
 // CHECK-NEXT:   SHF_ALLOC
 // CHECK-NEXT:   SHF_MERGE
 // CHECK-NEXT:   SHF_STRINGS
 // CHECK-NEXT: ]
 // CHECK-NEXT: Address: 0x1C8
 
 // CHECK:      Relocations [
 // CHECK-NEXT:   Section ({{.*}}) .rela.dyn {
-// CHECK-NEXT:     0x{{.*}} R_X86_64_RELATIVE - 0x1C9
+// CHECK-NEXT:     0x{{.*}} R_X86_64_RELATIVE - 0x1CC
 // CHECK-NEXT:   }
 // CHECK-NEXT: ]

lld/test/ELF/merge-string.s

 // REQUIRES: x86
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 // RUN: ld.lld -O 2 %t.o -o %t.so -shared
 // RUN: llvm-readobj -s -section-data -t %t.so | FileCheck %s
 // RUN: ld.lld -O 1 %t.o -o %t.so -shared
 // RUN: llvm-readobj -s -section-data -t %t.so | FileCheck --check-prefix=NOTAIL %s
 // RUN: ld.lld -O 0 %t.o -o %t.so -shared
 // RUN: llvm-readobj -s -section-data -t %t.so | FileCheck --check-prefix=NOMERGE %s
 
         .section  .rodata1,"aMS",@progbits,1
-  .asciz  "abc"
+  .asciz  "abcdef"
 foo:
-  .ascii  "a"
+  .ascii  "abcd"
 bar:
-        .asciz  "bc"
-        .asciz  "bc"
+        .asciz  "ef"
+        .asciz  "cdef"
 
         .section        .rodata2,"aMS",@progbits,2
         .align  2
 zed:
         .short  20
         .short  0
 
 // CHECK:      Name:    .rodata1
 // CHECK-NEXT: Type:    SHT_PROGBITS
 // CHECK-NEXT: Flags [
 // CHECK-NEXT:   SHF_ALLOC
 // CHECK-NEXT:   SHF_MERGE
 // CHECK-NEXT:   SHF_STRINGS
 // CHECK-NEXT: ]
 // CHECK-NEXT: Address:         0x1C8
 // CHECK-NEXT: Offset:  0x1C8
-// CHECK-NEXT: Size:    4
+// CHECK-NEXT: Size:
 // CHECK-NEXT: Link: 0
 // CHECK-NEXT: Info: 0
 // CHECK-NEXT: AddressAlignment: 1
 // CHECK-NEXT: EntrySize: 0
 // CHECK-NEXT: SectionData (
-// CHECK-NEXT:   0000: 61626300                             |abc.|
+// CHECK-NEXT:   |abcdef.|
 // CHECK-NEXT: )
 
 // NOTAIL:      Name:    .rodata1
 // NOTAIL-NEXT: Type:    SHT_PROGBITS
 // NOTAIL-NEXT: Flags [
 // NOTAIL-NEXT:   SHF_ALLOC
 // NOTAIL-NEXT:   SHF_MERGE
 // NOTAIL-NEXT:   SHF_STRINGS
 // NOTAIL-NEXT: ]
 // NOTAIL-NEXT: Address:         0x1C8
 // NOTAIL-NEXT: Offset:  0x1C8
-// NOTAIL-NEXT: Size:    7
+// NOTAIL-NEXT: Size:
 // NOTAIL-NEXT: Link: 0
 // NOTAIL-NEXT: Info: 0
 // NOTAIL-NEXT: AddressAlignment: 1
 // NOTAIL-NEXT: EntrySize: 0
 // NOTAIL-NEXT: SectionData (
-// NOTAIL-NEXT:   0000: 62630061 626300                     |bc.abc.|
+// NOTAIL-NEXT:   |cdef.abcdef.|
 // NOTAIL-NEXT: )
 
 // NOMERGE:      Name:    .rodata1
 // NOMERGE-NEXT: Type:    SHT_PROGBITS
 // NOMERGE-NEXT: Flags [
 // NOMERGE-NEXT:   SHF_ALLOC
 // NOMERGE-NEXT:   SHF_MERGE
 // NOMERGE-NEXT:   SHF_STRINGS
 // NOMERGE-NEXT: ]
 // NOMERGE-NEXT: Address:         0x1C8
 // NOMERGE-NEXT: Offset:  0x1C8
-// NOMERGE-NEXT: Size:    11
+// NOMERGE-NEXT: Size:
 // NOMERGE-NEXT: Link: 0
 // NOMERGE-NEXT: Info: 0
 // NOMERGE-NEXT: AddressAlignment: 1
 // NOMERGE-NEXT: EntrySize: 1
 // NOMERGE-NEXT: SectionData (
-// NOMERGE-NEXT:   0000: 61626300 61626300 626300 |abc.abc.bc.|
+// NOMERGE-NEXT:   |abcdef.abcdef.cd|
+// NOMERGE-NEXT:   |ef.|
 // NOMERGE-NEXT: )
 
 // CHECK:      Name: .rodata2
 // CHECK-NEXT: Type: SHT_PROGBITS
 // CHECK-NEXT: Flags [
 // CHECK-NEXT:   SHF_ALLOC
 // CHECK-NEXT:   SHF_MERGE
 // CHECK-NEXT:   SHF_STRINGS
 // CHECK-NEXT: ]
-// CHECK-NEXT: Address: 0x1CC
-// CHECK-NEXT: Offset: 0x1CC
-// CHECK-NEXT: Size: 4
+// CHECK-NEXT: Address: 0x1D0
+// CHECK-NEXT: Offset: 0x1D0
+// CHECK-NEXT: Size:
 // CHECK-NEXT: Link: 0
 // CHECK-NEXT: Info: 0
 // CHECK-NEXT: AddressAlignment: 2
 // CHECK-NEXT: EntrySize: 0
 // CHECK-NEXT: SectionData (
-// CHECK-NEXT:   0000: 14000000                             |....|
+// CHECK-NEXT:   |....|
 // CHECK-NEXT: )
 
 
 // CHECK:      Name:    bar
-// CHECK-NEXT: Value:   0x1C9
+// CHECK-NEXT: Value:   0x1CC
 
 // CHECK:      Name:    foo
 // CHECK-NEXT: Value:   0x1C8
 
 // CHECK:      Name: zed
-// CHECK-NEXT: Value: 0x1CC
+// CHECK-NEXT: Value: 0x1D0
 // CHECK-NEXT: Size: 0

lld/test/ELF/tail-merge-string-align.s

 // REQUIRES: x86
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
-// RUN: ld.lld %t.o -o %t.so -shared -O3
+// RUN: ld.lld %t.o -o %t.so -shared -O2
 // RUN: llvm-readobj -s -section-data %t.so | FileCheck %s
 
-        .section        .rodata.4a,"aMS",@progbits,1
-        .align 4
-        .asciz "abcdef"
+.asciz "abcdefg"
 
-        .section        .rodata.4b,"aMS",@progbits,1
-        .align 4
-        .asciz "ef"
+.asciz "efg"
 
-        .section        .rodata.4c,"aMS",@progbits,1
-        .align 4
-        .asciz "f"
-
+.asciz "defgh"
 
 // CHECK:      Name: .rodata
 // CHECK-NEXT: Type: SHT_PROGBITS
 // CHECK-NEXT: Flags [
 // CHECK-NEXT:   SHF_ALLOC
 // CHECK-NEXT:   SHF_MERGE
 // CHECK-NEXT:   SHF_STRINGS
 // CHECK-NEXT: ]
 // CHECK-NEXT: Address:
 // CHECK-NEXT: Offset:
-// CHECK-NEXT: Size: 1
+// CHECK-NEXT: Size:
 // CHECK-NEXT: Link: 0
 // CHECK-NEXT: Info: 0
 // CHECK-NEXT: AddressAlignment: 4
 // CHECK-NEXT: EntrySize:
 // CHECK-NEXT: SectionData (
-// CHECK-NEXT:   0000:    61626364 65660000 6600               |abcdef..f.|
+// CHECK-NEXT:   |defgh...abcdefg.|
 // CHECK-NEXT: )