From 8f7bcdf3c65b9a47e35653d525135beb18f3ac25 Mon Sep 17 00:00:00 2001 From: Jonas Devlieghere Date: Mon, 26 Feb 2018 12:05:18 +0000 Subject: [PATCH] Revert "[Support] Replace HashString with djbHash." It looks like some of our tests depend on the ordering of hashed values. I'm reverting my changes while I try to reproduce and fix this locally. Failing builds: lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/18388 lab.llvm.org:8011/builders/clang-cmake-x86_64-sde-avx512-linux/builds/6743 lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/15607 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@326082 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/StringExtras.h | 13 +++++++++++++ lib/Support/StringMap.cpp | 39 +++++++++++++++++++-------------------- 2 files changed, 32 insertions(+), 20 deletions(-) diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index 45f667797b3..60652f8c55c 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -232,6 +232,19 @@ void SplitString(StringRef Source, SmallVectorImpl &OutFragments, StringRef Delimiters = " \t\n\v\f\r"); +/// HashString - Hash function for strings. +/// +/// This is the Bernstein hash function. +// +// FIXME: Investigate whether a modified bernstein hash function performs +// better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx +// X*33+c -> X*33^c +inline unsigned HashString(StringRef Str, unsigned Result = 0) { + for (StringRef::size_type i = 0, e = Str.size(); i != e; ++i) + Result = Result * 33 + (unsigned char)Str[i]; + return Result; +} + /// Returns the English suffix for an ordinal integer (-st, -nd, -rd, -th). inline StringRef getOrdinalSuffix(unsigned Val) { // It is critically important that we do this perfectly for diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp index dc7d563eb99..9382c3ce29e 100644 --- a/lib/Support/StringMap.cpp +++ b/lib/Support/StringMap.cpp @@ -14,7 +14,6 @@ #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/Compiler.h" -#include "llvm/Support/DJB.h" #include "llvm/Support/MathExtras.h" #include @@ -33,7 +32,7 @@ static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { ItemSize = itemSize; - + // If a size is specified, initialize the table with that many buckets. if (InitSize) { // The table will grow when the number of entries reach 3/4 of the number of @@ -42,7 +41,7 @@ StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { init(getMinBucketToReserveForEntries(InitSize)); return; } - + // Otherwise, initialize it with zero buckets to avoid the allocation. TheTable = nullptr; NumBuckets = 0; @@ -57,7 +56,7 @@ void StringMapImpl::init(unsigned InitSize) { unsigned NewNumBuckets = InitSize ? InitSize : 16; NumItems = 0; NumTombstones = 0; - + TheTable = static_cast( std::calloc(NewNumBuckets+1, sizeof(StringMapEntryBase **) + sizeof(unsigned))); @@ -83,7 +82,7 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { init(16); HTSize = NumBuckets; } - unsigned FullHashValue = djbHash(Name); + unsigned FullHashValue = HashString(Name); unsigned BucketNo = FullHashValue & (HTSize-1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); @@ -99,11 +98,11 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { HashTable[FirstTombstone] = FullHashValue; return FirstTombstone; } - + HashTable[BucketNo] = FullHashValue; return BucketNo; } - + if (BucketItem == getTombstoneVal()) { // Skip over tombstones. However, remember the first one we see. if (FirstTombstone == -1) FirstTombstone = BucketNo; @@ -112,7 +111,7 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { // case here is that we are only looking at the buckets (for item info // being non-null and for the full hash value) not at the items. This // is important for cache locality. - + // Do the comparison like this because Name isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; @@ -121,10 +120,10 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { return BucketNo; } } - + // Okay, we didn't find the item. Probe to the next bucket. BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); - + // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. ++ProbeAmt; @@ -137,7 +136,7 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { int StringMapImpl::FindKey(StringRef Key) const { unsigned HTSize = NumBuckets; if (HTSize == 0) return -1; // Really empty table? - unsigned FullHashValue = djbHash(Key); + unsigned FullHashValue = HashString(Key); unsigned BucketNo = FullHashValue & (HTSize-1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); @@ -147,7 +146,7 @@ int StringMapImpl::FindKey(StringRef Key) const { // If we found an empty bucket, this key isn't in the table yet, return. if (LLVM_LIKELY(!BucketItem)) return -1; - + if (BucketItem == getTombstoneVal()) { // Ignore tombstones. } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { @@ -155,7 +154,7 @@ int StringMapImpl::FindKey(StringRef Key) const { // case here is that we are only looking at the buckets (for item info // being non-null and for the full hash value) not at the items. This // is important for cache locality. - + // Do the comparison like this because NameStart isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; @@ -164,10 +163,10 @@ int StringMapImpl::FindKey(StringRef Key) const { return BucketNo; } } - + // Okay, we didn't find the item. Probe to the next bucket. BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); - + // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. ++ProbeAmt; @@ -188,7 +187,7 @@ void StringMapImpl::RemoveKey(StringMapEntryBase *V) { StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { int Bucket = FindKey(Key); if (Bucket == -1) return nullptr; - + StringMapEntryBase *Result = TheTable[Bucket]; TheTable[Bucket] = getTombstoneVal(); --NumItems; @@ -242,13 +241,13 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { NewBucketNo = NewBucket; continue; } - + // Otherwise probe for a spot. unsigned ProbeSize = 1; do { NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); } while (NewTableArray[NewBucket]); - + // Finally found a slot. Fill it in. NewTableArray[NewBucket] = Bucket; NewHashArray[NewBucket] = FullHash; @@ -256,9 +255,9 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { NewBucketNo = NewBucket; } } - + free(TheTable); - + TheTable = NewTableArray; NumBuckets = NewSize; NumTombstones = 0; -- 2.11.0