From 87d02e0dfd760de38d092ef69f8a9164f28f2221 Mon Sep 17 00:00:00 2001 From: Erik Desjardins Date: Sun, 19 Feb 2023 13:47:09 -0500 Subject: Recommit "[Support] change StringMap hash function from djbHash to xxHash" This reverts commit 37eb9d13f891f7656f811516e765b929b169afe0. Test failures have been fixed: - ubsan failure fixed by 72eac42f21c0f45a27f3eaaff9364cbb5189b9e4 - warn-unsafe-buffer-usage-fixits-local-var-span.cpp fixed by 03cc52dfd1dbb4a59b479da55e87838fb93d2067 (wasn't related) - test-output-format.ll failure was spurious, build failed at https://lab.llvm.org/buildbot/#/builders/54/builds/3545 (b4431b2d945b6fc19b1a55ac6ce969a8e06e1e93) but passed at https://lab.llvm.org/buildbot/#/builders/54/builds/3546 (5ae99be0377248c74346096dc475af254a3fc799) which is before my revert https://github.com/llvm/llvm-project/compare/b4431b2d945b6fc19b1a55ac6ce969a8e06e1e93...5ae99be0377248c74346096dc475af254a3fc799 Original commit message: Depends on https://reviews.llvm.org/D142861. Alternative to https://reviews.llvm.org/D137601. xxHash is much faster than djbHash. This makes a simple Rust test case with a large constant string 10% faster to compile. Previous attempts at changing this hash function (e.g. https://reviews.llvm.org/D97396) had to be reverted due to breaking tests that depended on iteration order. No additional tests fail with this patch compared to `main` when running `check-all` with `-DLLVM_ENABLE_PROJECTS="all"` (on a Linux host), so I hope I found everything that needs to be changed. Differential Revision: https://reviews.llvm.org/D142862 --- llvm/lib/Support/StringMap.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'llvm/lib/Support/StringMap.cpp') diff --git a/llvm/lib/Support/StringMap.cpp b/llvm/lib/Support/StringMap.cpp index 9b2f96fca2cd..cf8f0930459d 100644 --- a/llvm/lib/Support/StringMap.cpp +++ b/llvm/lib/Support/StringMap.cpp @@ -11,8 +11,8 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/StringMap.h" -#include "llvm/Support/DJB.h" #include "llvm/Support/MathExtras.h" +#include "llvm/Support/xxhash.h" using namespace llvm; @@ -84,7 +84,7 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { // Hash table unallocated so far? if (NumBuckets == 0) init(16); - unsigned FullHashValue = djbHash(Name, 0); + unsigned FullHashValue = xxHash64(Name); unsigned BucketNo = FullHashValue & (NumBuckets - 1); unsigned *HashTable = getHashTable(TheTable, NumBuckets); @@ -139,7 +139,7 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { int StringMapImpl::FindKey(StringRef Key) const { if (NumBuckets == 0) return -1; // Really empty table? - unsigned FullHashValue = djbHash(Key, 0); + unsigned FullHashValue = xxHash64(Key); unsigned BucketNo = FullHashValue & (NumBuckets - 1); unsigned *HashTable = getHashTable(TheTable, NumBuckets); -- cgit v1.2.3