Index: lld/trunk/ELF/InputSection.cpp
===================================================================
--- lld/trunk/ELF/InputSection.cpp
+++ lld/trunk/ELF/InputSection.cpp
@@ -384,11 +384,6 @@
 template <class ELFT, class RelTy>
 void InputSection::copyRelocations(uint8_t *Buf, ArrayRef<RelTy> Rels) {
   InputSectionBase *RelocatedSection = getRelocatedSection();
-
-  // Loop is slow and have complexity O(N*M), where N - amount of
-  // relocations and M - amount of symbols in symbol table.
-  // That happens because getSymbolIndex(...) call below performs
-  // simple linear search.
   for (const RelTy &Rel : Rels) {
     uint32_t Type = Rel.getType(Config->IsMips64EL);
     SymbolBody &Body = this->getFile<ELFT>()->getRelocTargetSym(Rel);
Index: lld/trunk/ELF/SyntheticSections.h
===================================================================
--- lld/trunk/ELF/SyntheticSections.h
+++ lld/trunk/ELF/SyntheticSections.h
@@ -418,6 +418,10 @@
   std::vector<SymbolTableEntry> Symbols;
 
   StringTableSection &StrTabSec;
+
+  llvm::once_flag OnceFlag;
+  llvm::DenseMap<SymbolBody *, size_t> SymbolIndexMap;
+  llvm::DenseMap<OutputSection *, size_t> SectionIndexMap;
 };
 
 template <class ELFT>
Index: lld/trunk/ELF/SyntheticSections.cpp
===================================================================
--- lld/trunk/ELF/SyntheticSections.cpp
+++ lld/trunk/ELF/SyntheticSections.cpp
@@ -1355,18 +1355,24 @@
 }
 
 size_t SymbolTableBaseSection::getSymbolIndex(SymbolBody *Body) {
-  auto I = llvm::find_if(Symbols, [&](const SymbolTableEntry &E) {
-    if (E.Symbol == Body)
-      return true;
-    // This is used for -r, so we have to handle multiple section
-    // symbols being combined.
-    if (Body->Type == STT_SECTION && E.Symbol->Type == STT_SECTION)
-      return Body->getOutputSection() == E.Symbol->getOutputSection();
-    return false;
+  // Initializes symbol lookup tables lazily. This is used only
+  // for -r or -emit-relocs.
+  llvm::call_once(OnceFlag, [&] {
+    SymbolIndexMap.reserve(Symbols.size());
+    size_t I = 0;
+    for (const SymbolTableEntry &E : Symbols) {
+      if (E.Symbol->Type == STT_SECTION)
+        SectionIndexMap[E.Symbol->getOutputSection()] = ++I;
+      else
+        SymbolIndexMap[E.Symbol] = ++I;
+    }
   });
-  if (I == Symbols.end())
-    return 0;
-  return I - Symbols.begin() + 1;
+
+  // Section symbols are mapped based on their output sections
+  // to maintain their semantics.
+  if (Body->Type == STT_SECTION)
+    return SectionIndexMap.lookup(Body->getOutputSection());
+  return SymbolIndexMap.lookup(Body);
 }
 
 template <class ELFT>