Parallelize string merging.

[ruiu]

Summary

String merging is one of the most time-consuming functions in lld.
This patch parallelize it to speed it up. On my 2-socket 20-core
40-threads Xeon E5-2680 @ 2.8 GHz machine, this patch shorten the
clang debug build link time from 7.11s to 5.16s. It's a 27%
improvement and actually pretty noticeable. In this test condition,
lld is now 4x faster than gold.

[grimar]

lld/ELF/SyntheticSections.cpp

2241 ↗

(On Diff #116627)

Will it be better to calculate Begin and End instead of iterating over all pieces and using constructions like Sec->Hashes[I] % NumShards == ShardId ?
Something like:

size_t TaskSize = Sec->Pieces.size() / NumShards;
size_t I = TaskSize * ShardId;
size_t E = (ShardId == NumShards - 1) ? Sec->Pieces.size() : I + TaskSize;

[ruiu]

lld/ELF/SyntheticSections.cpp

2241 ↗

(On Diff #116627)

That won't work because it doesn't guarantee to produce a minimum table.

[grimar]

lld/ELF/SyntheticSections.cpp

2241 ↗

(On Diff #116627)

What I want to say is that spec says: "SHF_MERGE is an optional flag indicating a possible optimization. The link-editor is allowed to perform the optimization, or to ignore the optimization."

MergeNoTailSection is used for -O1. So for full optimization it is not used and that means users agree to have larger output size than is possible in theory, but have faster link time.
In that sence it can be acceptable not to guatantee a minimum table as it anyways not minimum possible one.

if such change does not noticably reduces the link time, it make no sence though.

[ruiu]

• Implemented a better algorithm. The new algorithm has little overhead on a single core use case unlike the previous one.

[ruiu]

• Fix a few minor errors.

[chapuni]

@ruiu, this happened to fail check-lld on -m32 (i686). Seems x86-64 is fine.
http://bb.pgr.jp/builders/test-lld-i686-linux-RA/builds/538

Could you investigate it please? I will investigate tomorrow.

lld/trunk/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;
-  void writeTo(uint8_t *Buf) override;
 
 protected:
   MergeSyntheticSection(StringRef Name, uint32_t Type, uint64_t Flags,
-                        uint32_t Alignment);
+                        uint32_t Alignment)
+      : SyntheticSection(Flags, Type, Alignment, Name) {}
 
   std::vector<MergeInputSection *> Sections;
-  llvm::StringTableBuilder Builder;
 };
 
 class MergeTailSection final : public MergeSyntheticSection {
 public:
   MergeTailSection(StringRef Name, uint32_t Type, uint64_t Flags,
-                   uint32_t Alignment)
-      : MergeSyntheticSection(Name, Type, Flags, Alignment) {}
+                   uint32_t Alignment);
 
+  size_t getSize() const override;
+  void writeTo(uint8_t *Buf) override;
   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/trunk/ELF/SyntheticSections.cpp

 #include "llvm/Object/Decompressor.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/xxhash.h"
 #include <cstdlib>
+#include <thread>
 
 using namespace llvm;
 using namespace llvm::dwarf;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support;
 using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
+const size_t MergeNoTailSection::NumShards;
+
 uint64_t SyntheticSection::getVA() const {
   if (OutputSection *Sec = getParent())
     return Sec->Addr + OutSecOff;
   return 0;
 }
 
 // Create a .bss section for each common section and replace the common symbol
 // with a DefinedRegular 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;
 }
 
-MergeSyntheticSection::MergeSyntheticSection(StringRef Name, uint32_t Type,
-                                             uint64_t Flags, uint32_t Alignment)
-    : SyntheticSection(Flags, Type, Alignment, Name),
-      Builder(StringTableBuilder::RAW, Alignment) {}
-
 void MergeSyntheticSection::addSection(MergeInputSection *MS) {
   MS->Parent = this;
   Sections.push_back(MS);
 }
 
-size_t MergeSyntheticSection::getSize() const { return Builder.getSize(); }
+MergeTailSection::MergeTailSection(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 MergeSyntheticSection::writeTo(uint8_t *Buf) { Builder.write(Buf); }
+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));
 
   // Fix the string table content. After this, the contents will never change.
   Builder.finalize();
 
   // 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 MergeNoTailSection::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() {
-  // Add all string pieces to the string table builder to create section
-  // contents. Because we are not tail-optimizing, offsets of strings are
-  // fixed when they are added to the builder (string table builder contains
-  // a hash table from strings to offsets).
-  for (MergeInputSection *Sec : Sections)
+  // 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.
+  size_t Concurrency = 1;
+  if (Config->Threads)
+    if (int N = std::thread::hardware_concurrency())
+      Concurrency = std::min(PowerOf2Floor(N), 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;
+        CachedHashStringRef Str = Sec->getData(I);
+        size_t ShardId = getShardId(Str.hash());
+        if ((ShardId & (Concurrency - 1)) == ThreadId)
+          Sec->Pieces[I].OutputOff = Shards[ShardId].add(Str);
+      }
+    }
+  });
+
+  // Compute an in-section offset for each shard.
+  size_t Off = 0;
+  for (size_t I = 0; I < NumShards; ++I) {
+    Shards[I].finalizeInOrder();
+    if (Shards[I].getSize() > 0)
+      Off = alignTo(Off, Alignment);
+    ShardOffsets[I] = Off;
+    Off += Shards[I].getSize();
+  }
+  Size = Off;
+
+  // So far, section pieces have offsets from beginning of shards, but
+  // we want offsets from beginning of the whole section. Fix them.
+  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 = Builder.add(Sec->getData(I));
-
-  Builder.finalizeInOrder();
+        Sec->Pieces[I].OutputOff +=
+            ShardOffsets[getShardId(Sec->getData(I).hash())];
+  });
 }
 
 static MergeSyntheticSection *createMergeSynthetic(StringRef Name,
                                                    uint32_t Type,
                                                    uint64_t Flags,
                                                    uint32_t Alignment) {
   bool ShouldTailMerge = (Flags & SHF_STRINGS) && Config->Optimize >= 2;
   if (ShouldTailMerge)

lld/trunk/test/ELF/comment-gc.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/comment-gc.s -o %t2.o
 # RUN: ld.lld %t.o %t2.o -o %t1 --gc-sections -shared
 # RUN: llvm-objdump -s %t1 | FileCheck %s
 
 # CHECK:      Contents of section .comment:
-# CHECK-NEXT:  0000 00666f6f 00626172 004c4c44 20312e30 .foo.bar.LLD 1.0
-# CHECK-NEXT:  0010 00 .
+# CHECK-NEXT: foo.LLD 1.0..bar
 
 .ident "foo"
 
 .globl _start
 _start:
   nop

lld/trunk/test/ELF/compressed-debug-input.s

 # DATA-NEXT:   Address: 0x0
 # DATA-NEXT:   Offset: 0x1060
 # DATA-NEXT:   Size: 69
 # DATA-NEXT:   Link: 0
 # DATA-NEXT:   Info: 0
 # DATA-NEXT:   AddressAlignment: 1
 # DATA-NEXT:   EntrySize: 0
 # DATA-NEXT:   SectionData (
-# DATA-NEXT:     0000: 73686F72 7420756E 7369676E 65642069  |short unsigned i|
-# DATA-NEXT:     0010: 6E740075 6E736967 6E656420 696E7400  |nt.unsigned int.|
+# DATA-NEXT:     0000: 756E7369 676E6564 20696E74 00636861  |unsigned int.cha|
+# DATA-NEXT:     0010: 7200756E 7369676E 65642063 68617200  |r.unsigned char.|
 # DATA-NEXT:     0020: 6C6F6E67 20756E73 69676E65 6420696E  |long unsigned in|
-# DATA-NEXT:     0030: 74006368 61720075 6E736967 6E656420  |t.char.unsigned |
-# DATA-NEXT:     0040: 63686172 00                          |char.|
+# DATA-NEXT:     0030: 74007368 6F727420 756E7369 676E6564  |t.short unsigned|
+# DATA-NEXT:     0040: 20696E74 00                          | int.|
 # DATA-NEXT:   )
 # DATA-NEXT: }
 
 .section .debug_str,"MS",@progbits,1
 .LASF2:
  .string "short unsigned int"
 .LASF3:
  .string "unsigned int"
 .LASF0:
  .string "long unsigned int"
 .LASF8:
  .string "char"
 .LASF1:
  .string "unsigned char"

lld/trunk/test/ELF/merge-string.s

 // NOTAIL-NEXT: Address:         0x1C8
 // NOTAIL-NEXT: Offset:  0x1C8
 // NOTAIL-NEXT: Size:    7
 // NOTAIL-NEXT: Link: 0
 // NOTAIL-NEXT: Info: 0
 // NOTAIL-NEXT: AddressAlignment: 1
 // NOTAIL-NEXT: EntrySize: 0
 // NOTAIL-NEXT: SectionData (
-// NOTAIL-NEXT:   0000: 61626300 626300                     |abc.bc.|
+// NOTAIL-NEXT:   0000: 62630061 626300                     |bc.abc.|
 // 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

lld/trunk/test/ELF/string-gc.s

 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 // RUN: ld.lld %t.o -o %t --gc-sections
 // RUN: llvm-readobj -symbols %t | FileCheck %s
 
 // CHECK:      Symbols [
 // CHECK-NEXT:   Symbol {
 // CHECK-NEXT:     Name:  (0)
 // CHECK-NEXT:     Value: 0x0
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local (0x0)
 // CHECK-NEXT:     Type: None (0x0)
 // CHECK-NEXT:     Other: 0
 // CHECK-NEXT:     Section: Undefined (0x0)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
 // CHECK-NEXT:     Name: s3
-// CHECK-NEXT:     Value: 0x200125
+// CHECK-NEXT:     Value: 0x200120
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local (0x0)
 // CHECK-NEXT:     Type: Object (0x1)
 // CHECK-NEXT:     Other: 0
 // CHECK-NEXT:     Section: .rodata (0x1)
 // CHECK-NEXT:   }
 // CHECK-NEXT:   Symbol {
 // CHECK-NEXT:     Name: s1
-// CHECK-NEXT:     Value: 0x200120
+// CHECK-NEXT:     Value: 0x200125
 // CHECK-NEXT:     Size: 0
 // CHECK-NEXT:     Binding: Local (0x0)
 // CHECK-NEXT:     Type: Object (0x1)
 // CHECK-NEXT:     Other [ (0x2)
 // CHECK-NEXT:       STV_HIDDEN (0x2)
 // CHECK-NEXT:     ]
 // CHECK-NEXT:     Section: .rodata (0x1)
 // CHECK-NEXT:   }