Index: llvm/lib/Support/StringRef.cpp
===================================================================
--- llvm/lib/Support/StringRef.cpp
+++ llvm/lib/Support/StringRef.cpp
@@ -202,7 +202,7 @@
     return npos;
   for (size_t i = Length - N + 1, e = 0; i != e;) {
     --i;
-    if (substr(i, N).equals(Str))
+    if (*(Data + i) == *(Str.Data) && substr(i, N).equals(Str))
       return i;
   }
   return npos;
Index: llvm/tools/dsymutil/MachODebugMapParser.cpp
===================================================================
--- llvm/tools/dsymutil/MachODebugMapParser.cpp
+++ llvm/tools/dsymutil/MachODebugMapParser.cpp
@@ -14,6 +14,7 @@
 #include "llvm/Support/Path.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
+#include <unordered_map>
 #include <vector>
 
 namespace {
@@ -51,6 +52,12 @@
   BinaryHolder BinHolder;
   /// Map of the binary symbol addresses.
   StringMap<uint64_t> MainBinarySymbolAddresses;
+
+  /// Binary symbol addresses to names map, to speedup
+  /// `getMainBinarySymbolNames`;
+  std::unordered_map<uint64_t, std::vector<StringRef>>
+      MainBinaryAddresses2NamesMap;
+
   StringRef MainBinaryStrings;
   /// The constructed DebugMap.
   std::unique_ptr<DebugMap> Result;
@@ -533,11 +540,16 @@
 /// Get all symbol names in the main binary for the given value.
 std::vector<StringRef>
 MachODebugMapParser::getMainBinarySymbolNames(uint64_t Value) {
-  std::vector<StringRef> Names;
-  for (const auto &Entry : MainBinarySymbolAddresses) {
-    if (Entry.second == Value)
-      Names.push_back(Entry.first());
+
+  auto result = MainBinaryAddresses2NamesMap.find(Value);
+  if (result != MainBinaryAddresses2NamesMap.end()) {
+    return result->second;
   }
+
+  /// used by `loadMainBinarySymbols`
+  std::vector<StringRef> Names;
+  MainBinaryAddresses2NamesMap[Value] = Names;
+
   return Names;
 }
 
@@ -547,6 +559,8 @@
     const MachOObjectFile &MainBinary) {
   section_iterator Section = MainBinary.section_end();
   MainBinarySymbolAddresses.clear();
+  MainBinaryAddresses2NamesMap.clear();
+
   for (const auto &Sym : MainBinary.symbols()) {
     Expected<SymbolRef::Type> TypeOrErr = Sym.getType();
     if (!TypeOrErr) {
@@ -588,10 +602,14 @@
     if (Name.size() == 0 || Name[0] == '\0')
       continue;
     // Override only if the new key is global.
-    if (Extern)
+    if (Extern) {
       MainBinarySymbolAddresses[Name] = Addr;
-    else
-      MainBinarySymbolAddresses.try_emplace(Name, Addr);
+      getMainBinarySymbolNames(Addr).push_back(Name);
+    } else {
+      if (MainBinarySymbolAddresses.try_emplace(Name, Addr).second) {
+        getMainBinarySymbolNames(Addr).push_back(Name);
+      }
+    }
   }
 }