Index: ELF/InputSection.h
===================================================================
--- ELF/InputSection.h
+++ ELF/InputSection.h
@@ -160,11 +160,13 @@
 // be found by looking at the next one) and put the hash in a side table.
 struct SectionPiece {
   SectionPiece(size_t Off, bool Live = false)
-      : InputOff(Off), OutputOff(-1), Live(Live || !Config->GcSections) {}
+      : InputOff(Off), Live(Live || !Config->GcSections), OutputOff(-1),
+        First(false) {}
 
-  size_t InputOff;
-  ssize_t OutputOff : 8 * sizeof(ssize_t) - 1;
+  size_t InputOff : 8 * sizeof(size_t) - 1;
   size_t Live : 1;
+  ssize_t OutputOff : 8 * sizeof(ssize_t) - 1;
+  size_t First : 1;
 };
 static_assert(sizeof(SectionPiece) == 2 * sizeof(size_t),
               "SectionPiece is too big");
Index: ELF/OutputSections.h
===================================================================
--- ELF/OutputSections.h
+++ ELF/OutputSections.h
@@ -16,12 +16,14 @@
 #include "lld/Core/LLVM.h"
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Object/ELF.h"
+#include <functional>
 
 namespace lld {
 namespace elf {
 
 class SymbolBody;
 struct EhSectionPiece;
+struct SectionPiece;
 template <class ELFT> class EhInputSection;
 template <class ELFT> class InputSection;
 template <class ELFT> class InputSectionBase;
@@ -142,9 +144,12 @@
 private:
   void finalizeTailMerge();
   void finalizeNoTailMerge();
+  void forEachPiece(
+      std::function<void(SectionPiece &Piece, llvm::CachedHashStringRef S)> Fn);
 
   llvm::StringTableBuilder Builder;
   std::vector<MergeInputSection<ELFT> *> Sections;
+  size_t StringAlignment;
 };
 
 struct CieRecord {
Index: ELF/OutputSections.cpp
===================================================================
--- ELF/OutputSections.cpp
+++ ELF/OutputSections.cpp
@@ -21,6 +21,7 @@
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/SHA1.h"
+#include <atomic>
 
 using namespace llvm;
 using namespace llvm::dwarf;
@@ -470,10 +471,21 @@
 MergeOutputSection<ELFT>::MergeOutputSection(StringRef Name, uint32_t Type,
                                              uintX_t Flags, uintX_t Alignment)
     : OutputSectionBase(Name, Type, Flags),
-      Builder(StringTableBuilder::RAW, Alignment) {}
+      Builder(StringTableBuilder::RAW, Alignment), StringAlignment(Alignment) {
+  assert(Alignment != 0 && isPowerOf2_64(Alignment));
+}
 
 template <class ELFT> void MergeOutputSection<ELFT>::writeTo(uint8_t *Buf) {
-  Builder.write(Buf);
+  if (shouldTailMerge()) {
+    Builder.write(Buf);
+    return;
+  }
+
+  // Builder is not used for sharded string table construction.
+  forEachPiece([&](SectionPiece &Piece, CachedHashStringRef S) {
+    if (Piece.First)
+      memcpy(Buf + Piece.OutputOff, S.val().data(), S.size());
+  });
 }
 
 template <class ELFT>
@@ -524,11 +536,68 @@
   this->Size = Builder.getSize();
 }
 
+static size_t align2(size_t Val, size_t Alignment) {
+  return (Val + Alignment - 1) & ~(Alignment - 1);
+}
+
+// Call Fn for each section piece.
+template <class ELFT>
+void MergeOutputSection<ELFT>::forEachPiece(
+    std::function<void(SectionPiece &Piece, CachedHashStringRef S)> Fn) {
+  for (MergeInputSection<ELFT> *Sec : Sections)
+    for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
+      if (Sec->Pieces[I].Live)
+        Fn(Sec->Pieces[I], Sec->getData(I));
+}
+
 template <class ELFT> void MergeOutputSection<ELFT>::finalize() {
-  if (shouldTailMerge())
+  if (shouldTailMerge()) {
     finalizeTailMerge();
-  else
-    finalizeNoTailMerge();
+    return;
+  }
+
+  const int NumShards = 16;
+  DenseMap<CachedHashStringRef, size_t> OffsetMap[NumShards];
+  size_t ShardSize[NumShards];
+
+  // Construct NumShards number of string tables in parallel.
+  parallel_for(0, NumShards, [&](int Idx) {
+    size_t Offset = 0;
+    forEachPiece([&](SectionPiece &Piece, CachedHashStringRef S) {
+      if (S.hash() % NumShards != Idx)
+        return;
+
+      size_t Off = align2(Offset, StringAlignment);
+      auto P = OffsetMap[Idx].insert({S, Off});
+      if (P.second) {
+        Piece.First = true;
+        Piece.OutputOff = Off;
+        Offset = Off + S.size();
+      } else {
+        Piece.OutputOff = P.first->second;
+      }
+    });
+    ShardSize[Idx] = Offset;
+  });
+
+  // Piece.OutputOff was set independently, so we need to fix it.
+  // First, we compute starting offset in the string table for each shard.
+  size_t ShardOffset[NumShards];
+  ShardOffset[0] = 0;
+  for (int I = 1; I != NumShards; ++I)
+    ShardOffset[I] = ShardOffset[I - 1] + ShardSize[I - 1];
+
+  // Add a shard starting offset to each section piece.
+  parallel_for_each(Sections.begin(), Sections.end(),
+                    [&](MergeInputSection<ELFT> *Sec) {
+                      for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
+                        if (Sec->Pieces[I].Live)
+                          Sec->Pieces[I].OutputOff +=
+                              ShardOffset[Sec->getData(I).hash() % NumShards];
+                    });
+
+  // Set the size of this output section.
+  this->Size = ShardOffset[NumShards - 1] + ShardSize[NumShards - 1];
 }
 
 template <class ELFT>