llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-tablegen Author: Matt Arsenault (arsenm) <details> <summary>Changes</summary> We were sizing the table appropriately for the number of LibcallImpls, but many of those have identical names which were pushing up the collision count unnecessarily. This ends up decreasing the table size slightly, and makes it a bit faster. BM_LookupRuntimeLibcallByNameRandomCalls improves by ~25% and BM_LookupRuntimeLibcallByNameSampleData by ~5%. As a secondary change, align the table size up to the next power of 2. This makes the table larger than before, but improves the sample data benchmark by an additional 5%. --- Full diff: https://github.com/llvm/llvm-project/pull/153801.diff 1 Files Affected: - (modified) llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp (+32-27) ``````````diff diff --git a/llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp b/llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp index 1c5f38d0c24b8..05f2512e24a50 100644 --- a/llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp +++ b/llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp @@ -289,7 +289,6 @@ class RuntimeLibcallEmitter { /// Helper struct for the name hash table. struct LookupEntry { - StringRef FuncName; uint64_t Hash = 0; unsigned TableValue = 0; }; @@ -339,14 +338,17 @@ static void emitHashFunction(raw_ostream &OS) { /// Return the table size, maximum number of collisions for the set of hashes static std::pair<int, int> computePerfectHashParameters(ArrayRef<uint64_t> Hashes) { - const int SizeOverhead = 10; - const int NumHashes = Hashes.size(); + // Chosen based on experimentation with llvm/benchmarks/RuntimeLibcalls.cpp + const int SizeOverhead = 4; // Index derived from hash -> number of collisions. DenseMap<uint64_t, int> Table; + unsigned NumHashes = Hashes.size(); + for (int MaxCollisions = 1;; ++MaxCollisions) { - for (int N = NumHashes; N < SizeOverhead * NumHashes; ++N) { + for (unsigned N = NextPowerOf2(NumHashes - 1); N < SizeOverhead * NumHashes; + N <<= 1) { Table.clear(); bool NeedResize = false; @@ -367,22 +369,12 @@ computePerfectHashParameters(ArrayRef<uint64_t> Hashes) { static std::vector<LookupEntry> constructPerfectHashTable(ArrayRef<RuntimeLibcallImpl> Keywords, - ArrayRef<uint64_t> Hashes, int Size, int Collisions, - StringToOffsetTable &OffsetTable) { - DenseSet<StringRef> Seen; + ArrayRef<uint64_t> Hashes, + ArrayRef<unsigned> TableValues, int Size, + int Collisions, StringToOffsetTable &OffsetTable) { std::vector<LookupEntry> Lookup(Size * Collisions); - for (const RuntimeLibcallImpl &LibCallImpl : Keywords) { - StringRef ImplName = LibCallImpl.getLibcallFuncName(); - - // We do not want to add repeated entries for cases with the same name, only - // an entry for the first, with the name collision enum values immediately - // following. - if (!Seen.insert(ImplName).second) - continue; - - uint64_t HashValue = Hashes[LibCallImpl.getEnumVal() - 1]; - + for (auto [HashValue, TableValue] : zip(Hashes, TableValues)) { uint64_t Idx = (HashValue % static_cast<uint64_t>(Size)) * static_cast<uint64_t>(Collisions); @@ -390,8 +382,7 @@ constructPerfectHashTable(ArrayRef<RuntimeLibcallImpl> Keywords, for (int J = 0; J < Collisions; ++J) { LookupEntry &Entry = Lookup[Idx + J]; if (Entry.TableValue == 0) { - Entry.FuncName = ImplName; - Entry.TableValue = LibCallImpl.getEnumVal(); + Entry.TableValue = TableValue; Entry.Hash = HashValue; Found = true; break; @@ -399,7 +390,7 @@ constructPerfectHashTable(ArrayRef<RuntimeLibcallImpl> Keywords, } if (!Found) - reportFatalInternalError("failure to hash " + ImplName); + reportFatalInternalError("failure to hash"); } return Lookup; @@ -409,15 +400,25 @@ constructPerfectHashTable(ArrayRef<RuntimeLibcallImpl> Keywords, void RuntimeLibcallEmitter::emitNameMatchHashTable( raw_ostream &OS, StringToOffsetTable &OffsetTable) const { std::vector<uint64_t> Hashes(RuntimeLibcallImplDefList.size()); + std::vector<unsigned> TableValues(RuntimeLibcallImplDefList.size()); + DenseSet<StringRef> SeenFuncNames; size_t MaxFuncNameSize = 0; size_t Index = 0; + for (const RuntimeLibcallImpl &LibCallImpl : RuntimeLibcallImplDefList) { StringRef ImplName = LibCallImpl.getLibcallFuncName(); - MaxFuncNameSize = std::max(MaxFuncNameSize, ImplName.size()); - Hashes[Index++] = hash(ImplName); + if (SeenFuncNames.insert(ImplName).second) { + MaxFuncNameSize = std::max(MaxFuncNameSize, ImplName.size()); + TableValues[Index] = LibCallImpl.getEnumVal(); + Hashes[Index++] = hash(ImplName); + } } + // Trim excess elements from non-unique entries. + Hashes.resize(SeenFuncNames.size()); + TableValues.resize(SeenFuncNames.size()); + LLVM_DEBUG({ for (const RuntimeLibcallImpl &LibCallImpl : RuntimeLibcallImplDefList) { StringRef ImplName = LibCallImpl.getLibcallFuncName(); @@ -447,8 +448,9 @@ void RuntimeLibcallEmitter::emitNameMatchHashTable( "#endif\n"; auto [Size, Collisions] = computePerfectHashParameters(Hashes); - std::vector<LookupEntry> Lookup = constructPerfectHashTable( - RuntimeLibcallImplDefList, Hashes, Size, Collisions, OffsetTable); + std::vector<LookupEntry> Lookup = + constructPerfectHashTable(RuntimeLibcallImplDefList, Hashes, TableValues, + Size, Collisions, OffsetTable); LLVM_DEBUG(dbgs() << "Runtime libcall perfect hashing parameters: Size = " << Size << ", maximum collisions = " << Collisions << '\n'); @@ -464,10 +466,13 @@ void RuntimeLibcallEmitter::emitNameMatchHashTable( OS << " static constexpr uint16_t HashTableNameToEnum[" << Lookup.size() << "] = {\n"; - for (auto [FuncName, Hash, TableVal] : Lookup) { + for (auto [Hash, TableVal] : Lookup) { OS << " " << TableVal << ','; - if (TableVal != 0) + if (TableVal != 0) { + StringRef FuncName = + RuntimeLibcallImplDefList[TableVal].getLibcallFuncName(); OS << " // " << format_hex(Hash, 16) << ", " << FuncName; + } OS << '\n'; } `````````` </details> https://github.com/llvm/llvm-project/pull/153801 _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
