Switch the new COFF linker's symbol table to use a DenseMap of StringRefs. This uses the LLVM hashing rather than the standard library and a closed addressed hash table rather than chaining.

[chandlerc]

Summary

This improves the Windows self-link of LLD by 4.4% (averaged over 10
runs, with well under 1% of variance on each).

There is still some room to improve here. Two things I clearly see in
the profile:

1. This is one of the biggest stress tests for the LLVM hashing code. It actually consumes something like 3-4% of the link time after the change.
2. The way that StringRef keys are handled in the DenseMap interface is pretty suboptimal. We pay the price of checking for empty and tombstone keys when we could only possibly be looking for a normal key. But fixing this requires invasive API changes.

So there is still some headroom here.

[ruiu]

LGTM. Nice.

One thing I want to mention is that the hash table used for the symbol table is append-only. We never remove any item from the hash table. All newly inserted keys are unique, so once a key-value pair is inserted, they will never change. Not sure if it helps you optimize it more (probably not), but that's an interesting property of the symbol table compared to other generic hash table uses.

COFF/SymbolTable.h

 //===- SymbolTable.h ------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_COFF_SYMBOL_TABLE_H
 #define LLD_COFF_SYMBOL_TABLE_H
 
 #include "InputFiles.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/Support/Allocator.h"
-#include <unordered_map>
 
 namespace llvm {
 struct LTOCodeGenerator;
 }
 
 namespace lld {
 namespace coff {
 
public:
   std::error_code rename(StringRef From, StringRef To);
 
 private:
   std::error_code resolve(SymbolBody *Body);
   std::error_code resolveLazy(StringRef Name);
   std::error_code addMemberFile(Lazy *Body);
   ErrorOr<ObjectFile *> createLTOObject(llvm::LTOCodeGenerator *CG);
 
-  std::unordered_map<StringRef, Symbol *> Symtab;
+  llvm::DenseMap<StringRef, Symbol *> Symtab;
   std::vector<std::unique_ptr<InputFile>> Files;
   size_t FileIdx = 0;
   std::vector<ArchiveFile *> ArchiveFiles;
   std::vector<BitcodeFile *> BitcodeFiles;
   std::unique_ptr<MemoryBuffer> LTOMB;
   llvm::BumpPtrAllocator Alloc;
 
   // This variable is incremented every time Symtab is updated.
   size_t Version = 0;
 };
 
 } // namespace coff
 } // namespace lld
 
 #endif