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

2240

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

2240

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

[grimar]

lld/ELF/SyntheticSections.cpp

2240

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/ELF/InputSection.h

llvm::CachedHashStringRef getData(size_t I) const {
     size_t Begin = Pieces[I].InputOff;
     size_t End;
     if (Pieces.size() - 1 == I)
       End = this->Data.size();
     else
       End = Pieces[I + 1].InputOff;
 
     StringRef S = {(const char *)(this->Data.data() + Begin), End - Begin};
-    return {S, Hashes[I]};
+    return {S, (uint32_t)Hashes[I]};
   }
 
   // Returns the SectionPiece at a given input section offset.
   SectionPiece *getSectionPiece(uint64_t Offset);
   const SectionPiece *getSectionPiece(uint64_t Offset) const;
 
   SyntheticSection *getParent() const;
 
+  std::vector<size_t> Hashes;
+
 private:
   void splitStrings(ArrayRef<uint8_t> A, size_t Size);
   void splitNonStrings(ArrayRef<uint8_t> A, size_t Size);
 
-  std::vector<uint32_t> Hashes;
 
   mutable llvm::DenseMap<uint64_t, uint64_t> OffsetMap;
   mutable llvm::once_flag InitOffsetMap;
 
   llvm::DenseSet<uint64_t> LiveOffsets;
 };
 
 struct EhSectionPiece {

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;
-  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(size_t Hash) {
+    return Hash >> (sizeof(size_t) * 8 - 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

 #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;
 }
 
 std::vector<InputSection *> elf::createCommonSections() {
   if (!Config->DefineCommon)
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 Parallelism =
+      std::min(PowerOf2Floor(std::thread::hardware_concurrency()), NumShards);
+
+  // Add section pieces to the builders.
+  parallelForEachN(0, Parallelism, [&](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->Hashes[I]);
+        if ((ShardId & (Parallelism - 1)) == ThreadId)
+          Sec->Pieces[I].OutputOff = Shards[ShardId].add(Sec->getData(I));
+      }
+    }
+  });
+
+  // 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->Hashes[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)

lld/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/test/ELF/compress-debug-sections.s

 # ZLIBFLAGS:         Name: .debug_str
 # ZLIBFLAGS-NEXT:    Type: SHT_PROGBITS
 # ZLIBFLAGS-NEXT:    Flags [
 # ZLIBFLAGS-NEXT:      SHF_COMPRESSED
 
 # RUN: llvm-dwarfdump %t1 -debug-str | \
 # RUN:   FileCheck %s --check-prefix=DEBUGSTR
 # DEBUGSTR:     .debug_str contents:
-# DEBUGSTR-NEXT:  AAAAAAAAAAAAAAAAAAAAAAAAAAA
 # DEBUGSTR-NEXT:  BBBBBBBBBBBBBBBBBBBBBBBBBBB
+# DEBUGSTR-NEXT:  AAAAAAAAAAAAAAAAAAAAAAAAAAA
 
 ## Test alias.
 # RUN: ld.lld %t.o -o %t2 --compress-debug-sections zlib
 # RUN: llvm-objdump -s %t2 | FileCheck %s --check-prefix=ZLIBCONTENT
 # RUN: llvm-readobj -s %t2 | FileCheck %s --check-prefix=ZLIBFLAGS
 
 # RUN: not ld.lld %t.o -o %t1 --compress-debug-sections=zlib-gabi 2>&1 | \
 # RUN:   FileCheck -check-prefix=ERR %s
 # ERR: unknown --compress-debug-sections value: zlib-gabi
 
 .section .debug_str,"MS",@progbits,1
 .Linfo_string0:
   .asciz "AAAAAAAAAAAAAAAAAAAAAAAAAAA"
 .Linfo_string1:
   .asciz "BBBBBBBBBBBBBBBBBBBBBBBBBBB"

lld/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:     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:     0000: 756E7369 676E6564 20636861 72006368  |unsigned char.ch|
+# DATA-NEXT:     0010: 61720073 686F7274 20756E73 69676E65  |ar.short unsigne|
+# DATA-NEXT:     0020: 6420696E 74006C6F 6E672075 6E736967  |d int.long unsig|
+# DATA-NEXT:     0030: 6E656420 696E7400 756E7369 676E6564  |ned int.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/test/ELF/debug-gc.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: ld.lld %t.o -o %t1 --gc-sections
 # RUN: llvm-objdump -s %t1 | FileCheck %s
 
 # CHECK:      Contents of section .debug_str:
-# CHECK-NEXT:  0000 41414100 42424200 43434300           AAA.BBB.CCC.
+# CHECK-NEXT:  0000 42424200 43434300 41414100           BBB.CCC.AAA.
 # CHECK:      Contents of section .foo:
 # CHECK-NEXT:  0000 2a000000
 # CHECK:      Contents of section .debug_info:
-# CHECK-NEXT:  0000 00000000 04000000
+# CHECK-NEXT:  0000 08000000 00000000
 
 .globl _start
 _start:
 
 .section .debug_str,"MS",@progbits,1
 .Linfo_string0:
   .asciz "AAA"
 .Linfo_string1:

lld/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/test/ELF/merge.s

 // CHECK-NEXT:    Address: 0x200120
 // CHECK-NEXT:    Offset: 0x120
 // CHECK-NEXT:    Size: 8
 // CHECK-NEXT:    Link: 0
 // CHECK-NEXT:    Info: 0
 // CHECK-NEXT:    AddressAlignment: 4
 // CHECK-NEXT:    EntrySize: 0
 // CHECK-NEXT:    SectionData (
-// CHECK-NEXT:      0000: 10000000 42000000
+// CHECK-NEXT:      0000: 42000000 10000000
 // CHECK-NEXT:    )
 
 
-// Address of the constant 0x10 = 0x200120 = 2097440
-// Address of the constant 0x42 = 0x200124 = 2097444
+// Address of the constant 0x42 = 0x200120 = 2097440
+// Address of the constant 0x10 = 0x200124 = 2097444
 
 // CHECK:      Symbols [
 
 // CHECK:        Name: bar
-// CHECK-NEXT:   Value: 0x200124
+// CHECK-NEXT:   Value: 0x200120
 // CHECK-NEXT:   Size: 0
 // CHECK-NEXT:   Binding: Loca
 // CHECK-NEXT:   Type: None
 // CHECK-NEXT:   Other: 0
 // CHECK-NEXT:   Section: .mysec
 
 // CHECK:        Name: zed
-// CHECK-NEXT:   Value: 0x200124
+// CHECK-NEXT:   Value: 0x200120
 // CHECK-NEXT:   Size: 0
 // CHECK-NEXT:   Binding: Local
 // CHECK-NEXT:   Type: None
 // CHECK-NEXT:   Other: 0
 // CHECK-NEXT:   Section: .mysec
 
 // CHECK:        Name: foo
-// CHECK-NEXT:   Value: 0x200124
+// CHECK-NEXT:   Value: 0x200120
 // CHECK-NEXT:   Size: 0
 // CHECK-NEXT:   Binding: Local
 // CHECK-NEXT:   Type: None
 // CHECK-NEXT:   Other [ (0x2)
 // CHECK-NEXT:     STV_HIDDEN
 // CHECK-NEXT:   ]
 // CHECK-NEXT:   Section: .mysec
 
  // CHECK: ]
 
         .text
         .globl  _start
 _start:
 // DISASM:      Disassembly of section .text:
 // DISASM-NEXT: _start:
 
         movl .mysec, %eax
-// addr(0x10) = 2097440
-// DISASM-NEXT:   movl    2097440, %eax
+// addr(0x10) = 2097444
+// DISASM-NEXT:   movl    2097444, %eax
 
         movl .mysec+7, %eax
-// addr(0x42) + 3 = 2097444 + 3 = 2097447
-// DISASM-NEXT:   movl    2097447, %eax
+// addr(0x42) + 3 = 2097440 + 3
+// DISASM-NEXT:   movl    2097443, %eax
 
         movl .mysec+8, %eax
-// addr(0x42) = 2097444
-// DISASM-NEXT:   movl    2097444, %eax
+// addr(0x42) = 2097440
+// DISASM-NEXT:   movl    2097440, %eax
 
         movl bar+7, %eax
-// addr(0x42) + 7 = 2097444 + 7 = 2097451
-// DISASM-NEXT:   movl    2097451, %eax
+// addr(0x42) + 7 = 2097440 + 7
+// DISASM-NEXT:   movl    2097447, %eax
 
         movl bar+8, %eax
-// addr(0x42) + 8 = 2097444 + 8 = 2097452
-// DISASM-NEXT:   movl    2097452, %eax
+// addr(0x42) + 8 = 2097440 + 8
+// DISASM-NEXT:   movl    2097448, %eax
 
         movl foo, %eax
-// addr(0x42) = 2097444
-// DISASM-NEXT:   movl    2097444, %eax
+// addr(0x42) = 2097440
+// DISASM-NEXT:   movl    2097440, %eax
 
         movl foo+7, %eax
-// addr(0x42) + 7 =  = 2097444 + 7 = 2097451
-// DISASM-NEXT:   movl    2097451, %eax
+// addr(0x42) + 7 =  = 2097440 + 7
+// DISASM-NEXT:   movl    2097447, %eax
 
         movl foo+8, %eax
-// addr(0x42) + 8 =  = 2097444 + 8 = 2097452
-// DISASM-NEXT:   movl    2097452, %eax
+// addr(0x42) + 8 =  = 2097440 + 8
+// DISASM-NEXT:   movl    2097448, %eax
 
 //  From the other file:  movl .mysec, %eax
-// addr(0x42) = 2097444
-// DISASM-NEXT:   movl    2097444, %eax
+// addr(0x42) = 2097440
+// DISASM-NEXT:   movl    2097440, %eax

lld/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:   }