Make StringTableBuilder to cache hash values.

[ruiu]

Summary

Make StringTableBuilder to cache hash values.

[ruiu]

This change seems to speed up LLD a bit. Not too bad for a small patch.

Time to link Clang (debug build):

w/o patch 6.3696 seconds
w/patch 6.2746 seconds (-1.5%)

[• rafael]

LGTM. There might be even more savings by adding methods that take a
CachedHash<StringRef> instead of a StringRef, but lets do this first.

[• rafael]

Note that you need to update lld too :-)

include/llvm/MC/StringTableBuilder.h

 
 /// \brief Utility for building string tables with deduplicated suffixes.
 class StringTableBuilder {
 public:
   enum Kind { ELF, WinCOFF, MachO, RAW };
 
 private:
   SmallString<256> StringTable;
-  DenseMap<StringRef, size_t> StringIndexMap;
+  DenseMap<CachedHash<StringRef>, size_t> StringIndexMap;
   size_t Size = 0;
   Kind K;
   unsigned Alignment;
 
   void finalizeStringTable(bool Optimize);
 
 public:
   StringTableBuilder(Kind K, unsigned Alignment = 1);
StringRef data() const {
     assert(isFinalized());
     return StringTable;
   }
 
   /// \brief Get the offest of a string in the string table. Can only be used
   /// after the table is finalized.
   size_t getOffset(StringRef S) const;
 
-  const DenseMap<StringRef, size_t> &getMap() const { return StringIndexMap; }
+  const DenseMap<CachedHash<StringRef>, size_t> &getMap() const {
+    return StringIndexMap;
+  }
+
   size_t getSize() const { return Size; }
   void clear();
 
 private:
   bool isFinalized() const {
     return !StringTable.empty();
   }
 };
 
 } // end llvm namespace
 
 #endif

lib/MC/StringTableBuilder.cpp

case ELF:
     Size = 1;
     break;
   case WinCOFF:
     Size = 4;
     break;
   }
 }
 
-typedef std::pair<StringRef, size_t> StringPair;
+typedef std::pair<CachedHash<StringRef>, size_t> StringPair;
 
 // Returns the character at Pos from end of a string.
 static int charTailAt(StringPair *P, size_t Pos) {
-  StringRef S = P->first;
+  StringRef S = P->first.Val;
   if (Pos >= S.size())
     return -1;
   return (unsigned char)S[S.size() - Pos - 1];
 }
 
 // Three-way radix quicksort. This is much faster than std::sort with strcmp
 // because it does not compare characters that we already know the same.
 static void multikey_qsort(StringPair **Begin, StringPair **End, int Pos) {
void StringTableBuilder::finalize() {
   finalizeStringTable(/*Optimize=*/true);
 }
 
 void StringTableBuilder::finalizeInOrder() {
   finalizeStringTable(/*Optimize=*/false);
 }
 
 void StringTableBuilder::finalizeStringTable(bool Optimize) {
-  typedef std::pair<StringRef, size_t> StringOffsetPair;
+  typedef std::pair<CachedHash<StringRef>, size_t> StringOffsetPair;
   std::vector<StringOffsetPair *> Strings;
   Strings.reserve(StringIndexMap.size());
   for (StringOffsetPair &P : StringIndexMap)
     Strings.push_back(&P);
 
   if (!Strings.empty()) {
     // If we're optimizing, sort by name. If not, sort by previously assigned
     // offset.
void StringTableBuilder::finalizeStringTable(bool Optimize) {
   case WinCOFF:
     // Make room to write the table size later.
     StringTable.append(4, '\x00');
     break;
   }
 
   StringRef Previous;
   for (StringOffsetPair *P : Strings) {
-    StringRef S = P->first;
+    StringRef S = P->first.Val;
     if (K == WinCOFF)
       assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
 
     if (Optimize && Previous.endswith(S)) {
       size_t Pos = StringTable.size() - S.size() - (K != RAW);
       if (!(Pos & (Alignment - 1))) {
         P->second = Pos;
         continue;