ld.lld: poor man's concurrent hash map

gistfile1.txt

From 088ff7744ff15adc524f21431a5206d6f82f493b Mon Sep 17 00:00:00 2001
From: Fangrui Song
Date: Thu, 13 Jan 2022 17:05:28 -0800
Subject: [PATCH] DO NOT SUBMIT! Poor man's concurrent hash map

---
 lld/ELF/SyntheticSections.cpp      | 25 +++++++++----------------
 lld/ELF/SyntheticSections.h        |  2 +-
 lld/include/lld/Common/SpinMutex.h | 28 ++++++++++++++++++++++++++++
 3 files changed, 38 insertions(+), 17 deletions(-)
 create mode 100644 lld/include/lld/Common/SpinMutex.h

diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index f41459dc70d4..0717a6b56169 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -25,6 +25,7 @@
 #include "lld/Common/DWARF.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
+#include "lld/Common/SpinMutex.h"
 #include "lld/Common/Strings.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/SetOperations.h"
@@ -3300,23 +3301,15 @@ void MergeNoTailSection::finalizeContents() {
   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 = PowerOf2Floor(
-      std::min<size_t>(hardware_concurrency(parallel::strategy.ThreadsRequested)
-                           .compute_thread_count(),
-                       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)
-          sec->pieces[i].outputOff = shards[shardId].add(sec->getData(i));
-      }
+  SpinMutex mutexes[numShards];
+  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 = getShardId(sec->pieces[i].hash);
+      std::lock_guard<SpinMutex> guard(mutexes[shardId]);
+      sec->pieces[i].outputOff = shards[shardId].add(sec->getData(i));
     }
   });
 
diff --git a/lld/ELF/SyntheticSections.h b/lld/ELF/SyntheticSections.h
index 3090cf1aae14..1db9c6fad7cf 100644
--- a/lld/ELF/SyntheticSections.h
+++ b/lld/ELF/SyntheticSections.h
@@ -969,7 +969,7 @@ private:
   size_t size;
 
   // String table contents
-  constexpr static size_t numShards = 32;
+  constexpr static size_t numShards = 128;
   SmallVector<llvm::StringTableBuilder, 0> shards;
   size_t shardOffsets[numShards];
 };
diff --git a/lld/include/lld/Common/SpinMutex.h b/lld/include/lld/Common/SpinMutex.h
new file mode 100644
index 000000000000..24682bd657ab
--- /dev/null
+++ b/lld/include/lld/Common/SpinMutex.h
@@ -0,0 +1,28 @@
+#ifndef LLD_COMMON_SPINMUTEX_H
+#define LLD_COMMON_SPINMUTEX_H
+
+#include <atomic>
+
+
+namespace lld {
+namespace elf {
+
+struct alignas(64) SpinMutex {
+  std::atomic<bool> flag{false};
+
+  void lock() {
+    for (;;) {
+      if (!flag.exchange(true, std::memory_order_acquire))
+        return;
+      do __builtin_ia32_pause(), __builtin_ia32_pause(), __builtin_ia32_pause(), __builtin_ia32_pause();
+      while (flag.load(std::memory_order_relaxed));
+    }
+  }
+
+  void unlock() { flag.store(false, std::memory_order_release); }
+};
+
+} // namespace elf
+} // namespace lld
+
+#endif
-- 
2.34