Cache modulo values for the .gnu.hash section.

[ruiu]

Summary

This change actually makes the linker slightly faster. My observation
is that, with this patch, link time of clang without debug is about 1%
faster.

[ruiu]

• Removed unrelated change.

[ruiu]

• clang-format

It seems this patch actually makes that test case 2% faster, which
isn't a negligible improvement.

[joerg]

Instead of computing and storing the modulus directly, it is likely better to precompute the inverse and use that to improve the performance of the operation in first place. Consider using fast_remainder32 and associated functions.

ELF/SyntheticSections.h

private:
 
   void writeBloomFilter(uint8_t *Buf);
   void writeHashTable(uint8_t *Buf);
 
   struct Entry {
     Symbol *Sym;
     size_t StrTabOffset;
     uint32_t Hash;
+    uint32_t BucketIdx;
   };
 
   std::vector<Entry> Symbols;
   size_t MaskWords;
   size_t NBuckets = 0;
   size_t Size = 0;
 };
 

ELF/SyntheticSections.cpp

for (const Entry &Sym : Symbols) {
     writeUint(Buf + I * Config->Wordsize, Val);
   }
 }
 
 void GnuHashTableSection::writeHashTable(uint8_t *Buf) {
   // Group symbols by hash value.
   std::vector<std::vector<Entry>> Syms(NBuckets);
   for (const Entry &Ent : Symbols)
-    Syms[Ent.Hash % NBuckets].push_back(Ent);
+    Syms[Ent.BucketIdx].push_back(Ent);
 
   // Write hash buckets. Hash buckets contain indices in the following
   // hash value table.
   uint32_t *Buckets = reinterpret_cast<uint32_t *>(Buf);
   for (size_t I = 0; I < NBuckets; ++I)
     if (!Syms[I].empty())
       write32(Buckets + I, Syms[I][0].Sym->DynsymIndex);
 
std::vector<SymbolTableEntry>::iterator Mid =
         // linker has to look them up, so they have to be in the hash table.
         if (auto *SS = dyn_cast<SharedSymbol>(S.Sym))
           return SS->CopyRelSec == nullptr && !SS->NeedsPltAddr;
         return !S.Sym->isDefined();
       });
   if (Mid == V.end())
     return;
 
-  for (SymbolTableEntry &Ent : llvm::make_range(Mid, V.end())) {
-    Symbol *B = Ent.Sym;
-    Symbols.push_back({B, Ent.StrTabOffset, hashGnu(B->getName())});
-  }
-
   // We chose load factor 4 for the on-disk hash table. For each hash
   // collision, the dynamic linker will compare a uint32_t hash value.
   // Since the integer comparison is quite fast, we believe we can make
   // the load factor even larger. 4 is just a conservative choice.
-  NBuckets = std::max<size_t>(Symbols.size() / 4, 1);
+  NBuckets = std::max<size_t>((V.end() - Mid) / 4, 1);
 
-  std::stable_sort(Symbols.begin(), Symbols.end(),
-                   [&](const Entry &L, const Entry &R) {
-                     return L.Hash % NBuckets < R.Hash % NBuckets;
-                   });
+  for (SymbolTableEntry &Ent : llvm::make_range(Mid, V.end())) {
+    Symbol *B = Ent.Sym;
+    uint32_t Hash = hashGnu(B->getName());
+    uint32_t BucketIdx = Hash % NBuckets;
+    Symbols.push_back({B, Ent.StrTabOffset, Hash, BucketIdx});
+  }
+
+  std::stable_sort(
+      Symbols.begin(), Symbols.end(),
+      [](const Entry &L, const Entry &R) { return L.BucketIdx < R.BucketIdx; });
 
   V.erase(Mid, V.end());
   for (const Entry &Ent : Symbols)
     V.push_back({Ent.Sym, Ent.StrTabOffset});
 }
 
 HashTableSection::HashTableSection()
     : SyntheticSection(SHF_ALLOC, SHT_HASH, 4, ".hash") {