Hash symbol names only once per global SymbolBody

[• rafael]

Summary

The DenseMap doesn't store hash results. This means that when it is resized it has to recompute them.

This patch is a small hack that wraps the StringRef in a struct that remembers the hash value. That way we can be sure it is only hashed once.

This gives at least a small speedup in every testcase. The largest win is in a fast link (no icf, no gc sections) of chromium. The link goes from 1.821525390 to 1.740146930 seconds.

[sanjoy]

Could this live in include/llvm/ADT/ instead? Maybe even in StringRef.h?

[ruiu]

This is a very good change -- simple and effective.

ELF/SymbolTable.h

25

Do you have to use DenseMapInfo<StringRef>::getHashValue? I'd just use llvm::hash_value.

30

The size of unsigned int depends on the hosting platform, not the target platform, so SymName would have different hashes on 32-bit and 64-bit. Does this code produces the identical binaries when cross-linking on different machines?

30

I'd name Hash instead of HashValue.

[ruiu]

Sanjoy,

How would you add this to StringRef? Do you want to add a new word to StringRef for a hash value or are you suggesting something else?

[sanjoy]

In D19025#398778, @ruiu wrote:

Sanjoy,

How would you add this to StringRef? Do you want to add a new word to StringRef for a hash value or are you suggesting something else?

I meant just moving the Symbol class (possibly renamed to something more generic) to somewhere in llvm/ADT so that it is easily discoverable. Given that StringRef s are immutable anyway (so s/StringRef/Symbol in a DenseMap etc. is always correct), this looks like it could be useful more generally.

I didn't mean to suggest we should change StringRef itself.

[ruiu]

That sounds like a reasonable plan.

[ruiu]

LGTM

[Eugene.Zelenko]

Committed in r266357.

ELF/MarkLive.cpp

template <class ELFT> void elf::markLive(SymbolTable<ELFT> *Symtab) {
   MarkSymbol(Symtab->find(Config->Init));
   MarkSymbol(Symtab->find(Config->Fini));
   for (StringRef S : Config->Undefined)
     MarkSymbol(Symtab->find(S));
 
   // Preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
   if (Config->Shared || Config->ExportDynamic) {
-    for (const std::pair<StringRef, Symbol *> &P : Symtab->getSymbols()) {
+    for (const std::pair<SymName, Symbol *> &P : Symtab->getSymbols()) {
       SymbolBody *B = P.second->Body;
       if (B->getVisibility() == STV_DEFAULT)
         MarkSymbol(B);
     }
   }
 
   // Preserve special sections and those which are specified in linker
   // script KEEP command.

ELF/SymbolTable.h

 #include "llvm/ADT/MapVector.h"
 
 namespace lld {
 namespace elf {
 class Lazy;
 template <class ELFT> class OutputSectionBase;
 struct Symbol;
 
+struct SymName {
+  SymName(StringRef Name) : Name(Name) {
+    HashValue = llvm::DenseMapInfo<StringRef>::getHashValue(Name);
+  }
+  SymName(StringRef Name, unsigned HashValue)
+      : Name(Name), HashValue(HashValue) {}
+  StringRef Name;
+  unsigned HashValue;
+};
+}
+}
+
+namespace llvm {
+template <> struct DenseMapInfo<lld::elf::SymName> {
+  static lld::elf::SymName getEmptyKey() {
+    StringRef N = DenseMapInfo<StringRef>::getEmptyKey();
+    return {N, 0};
+  }
+  static lld::elf::SymName getTombstoneKey() {
+    StringRef N = DenseMapInfo<StringRef>::getTombstoneKey();
+    return {N, 0};
+  }
+  static unsigned getHashValue(lld::elf::SymName Name) {
+    return Name.HashValue;
+  }
+  static bool isEqual(lld::elf::SymName A, lld::elf::SymName B) {
+    return A.Name == B.Name;
+  }
+};
+}
+
+namespace lld {
+namespace elf {
+
 // SymbolTable is a bucket of all known symbols, including defined,
 // undefined, or lazy symbols (the last one is symbols in archive
 // files whose archive members are not yet loaded).
 //
 // We put all symbols of all files to a SymbolTable, and the
 // SymbolTable selects the "best" symbols if there are name
 // conflicts. For example, obviously, a defined symbol is better than
 // an undefined symbol. Or, if there's a conflict between a lazy and a
 // undefined, it'll read an archive member to read a real definition
 // to replace the lazy symbol. The logic is implemented in resolve().
 template <class ELFT> class SymbolTable {
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::uint uintX_t;
 
 public:
   void addFile(std::unique_ptr<InputFile> File);
   void addCombinedLtoObject();
 
-  const llvm::MapVector<StringRef, Symbol *> &getSymbols() const {
+  const llvm::MapVector<SymName, Symbol *> &getSymbols() const {
     return Symtab;
   }
 
   const std::vector<std::unique_ptr<ObjectFile<ELFT>>> &getObjectFiles() const {
     return ObjectFiles;
   }
 
   const std::vector<std::unique_ptr<SharedFile<ELFT>>> &getSharedFiles() const {
private:
 
   // The order the global symbols are in is not defined. We can use an arbitrary
   // order, but it has to be reproducible. That is true even when cross linking.
   // The default hashing of StringRef produces different results on 32 and 64
   // bit systems so we use a MapVector. That is arbitrary, deterministic but
   // a bit inefficient.
   // FIXME: Experiment with passing in a custom hashing or sorting the symbols
   // once symbol resolution is finished.
-  llvm::MapVector<StringRef, Symbol *> Symtab;
+  llvm::MapVector<SymName, Symbol *> Symtab;
   llvm::BumpPtrAllocator Alloc;
 
   // Comdat groups define "link once" sections. If two comdat groups have the
   // same name, only one of them is linked, and the other is ignored. This set
   // is used to uniquify them.
   llvm::DenseSet<StringRef> ComdatGroups;
 
   // The symbol table owns all file objects.