Index: lldb/source/Utility/ConstString.cpp =================================================================== --- lldb/source/Utility/ConstString.cpp +++ lldb/source/Utility/ConstString.cpp @@ -77,10 +77,10 @@ return 0; } - StringPoolValueType GetMangledCounterpart(const char *ccstr) const { + StringPoolValueType GetMangledCounterpart(const char *ccstr) { if (ccstr != nullptr) { - const uint8_t h = hash(llvm::StringRef(ccstr)); - llvm::sys::SmartScopedReader rlock(m_string_pools[h].m_mutex); + const PoolEntry &pool = selectPool(llvm::StringRef(ccstr)); + llvm::sys::SmartScopedReader rlock(pool.m_mutex); return GetStringMapEntryFromKeyData(ccstr).getValue(); } return nullptr; @@ -100,19 +100,20 @@ const char *GetConstCStringWithStringRef(const llvm::StringRef &string_ref) { if (string_ref.data()) { - const uint8_t h = hash(string_ref); + const uint32_t string_hash = StringPool::hash(string_ref); + PoolEntry &pool = selectPool(string_hash); { - llvm::sys::SmartScopedReader rlock(m_string_pools[h].m_mutex); - auto it = m_string_pools[h].m_string_map.find(string_ref); - if (it != m_string_pools[h].m_string_map.end()) + llvm::sys::SmartScopedReader rlock(pool.m_mutex); + auto it = pool.m_string_map.find(string_ref, string_hash); + if (it != pool.m_string_map.end()) return it->getKeyData(); } - llvm::sys::SmartScopedWriter wlock(m_string_pools[h].m_mutex); + llvm::sys::SmartScopedWriter wlock(pool.m_mutex); StringPoolEntryType &entry = - *m_string_pools[h] - .m_string_map.insert(std::make_pair(string_ref, nullptr)) + *pool.m_string_map + .insert(std::make_pair(string_ref, nullptr), string_hash) .first; return entry.getKeyData(); } @@ -125,12 +126,14 @@ const char *demangled_ccstr = nullptr; { - const uint8_t h = hash(demangled); - llvm::sys::SmartScopedWriter wlock(m_string_pools[h].m_mutex); + const uint32_t demangled_hash = StringPool::hash(demangled); + PoolEntry &pool = selectPool(demangled_hash); + llvm::sys::SmartScopedWriter wlock(pool.m_mutex); // Make or update string pool entry with the mangled counterpart - StringPool &map = m_string_pools[h].m_string_map; - StringPoolEntryType &entry = *map.try_emplace(demangled).first; + StringPool &map = pool.m_string_map; + StringPoolEntryType &entry = + *map.try_emplace_with_hash(demangled, demangled_hash).first; entry.second = mangled_ccstr; @@ -141,8 +144,8 @@ { // Now assign the demangled const string as the counterpart of the // mangled const string... - const uint8_t h = hash(llvm::StringRef(mangled_ccstr)); - llvm::sys::SmartScopedWriter wlock(m_string_pools[h].m_mutex); + PoolEntry &pool = selectPool(llvm::StringRef(mangled_ccstr)); + llvm::sys::SmartScopedWriter wlock(pool.m_mutex); GetStringMapEntryFromKeyData(mangled_ccstr).setValue(demangled_ccstr); } @@ -171,11 +174,6 @@ } protected: - uint8_t hash(const llvm::StringRef &s) const { - uint32_t h = llvm::djbHash(s); - return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff; - } - struct PoolEntry { mutable llvm::sys::SmartRWMutex m_mutex; StringPool m_string_map; @@ -183,6 +181,14 @@ }; std::array m_string_pools; + + PoolEntry &selectPool(const llvm::StringRef &s) { + return selectPool(StringPool::hash(s)); + } + + PoolEntry &selectPool(uint32_t h) { + return m_string_pools[((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff]; + } }; // Frameworks and dylibs aren't supposed to have global C++ initializers so we Index: llvm/include/llvm/ADT/StringMap.h =================================================================== --- llvm/include/llvm/ADT/StringMap.h +++ llvm/include/llvm/ADT/StringMap.h @@ -17,6 +17,7 @@ #include "llvm/ADT/StringMapEntry.h" #include "llvm/ADT/iterator.h" #include "llvm/Support/AllocatorBase.h" +#include "llvm/Support/DJB.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include #include @@ -60,12 +61,20 @@ /// specified bucket will be non-null. Otherwise, it will be null. In either /// case, the FullHashValue field of the bucket will be set to the hash value /// of the string. - unsigned LookupBucketFor(StringRef Key); + unsigned LookupBucketFor(StringRef Key) { + return LookupBucketFor(Key, hash(Key)); + } + + /// Overload that explicitly takes precomputed hash(Key). + unsigned LookupBucketFor(StringRef Key, uint32_t FullHashValue); /// FindKey - Look up the bucket that contains the specified key. If it exists /// in the map, return the bucket number of the key. Otherwise return -1. /// This does not modify the map. - int FindKey(StringRef Key) const; + int FindKey(StringRef Key) const { return FindKey(Key, hash(Key)); } + + /// Overload that explicitly takes precomputed hash(Key). + int FindKey(StringRef Key, uint32_t FullHashValue) const; /// RemoveKey - Remove the specified StringMapEntry from the table, but do not /// delete it. This aborts if the value isn't in the table. @@ -94,6 +103,13 @@ bool empty() const { return NumItems == 0; } unsigned size() const { return NumItems; } + /// Returns the hash value that will be used for the given string. + /// This allows precomputing the value and passing it explicitly + /// to some of the functions. + /// The implementation of this function is not guaranteed to be stable + /// and may change. + static uint32_t hash(StringRef Key) { return llvm::djbHash(Key, 0); } + void swap(StringMapImpl &Other) { std::swap(TheTable, Other.TheTable); std::swap(NumBuckets, Other.NumBuckets); @@ -215,15 +231,19 @@ StringMapKeyIterator(end())); } - iterator find(StringRef Key) { - int Bucket = FindKey(Key); + iterator find(StringRef Key) { return find(Key, hash(Key)); } + + iterator find(StringRef Key, uint32_t FullHashValue) { + int Bucket = FindKey(Key, FullHashValue); if (Bucket == -1) return end(); return iterator(TheTable + Bucket, true); } - const_iterator find(StringRef Key) const { - int Bucket = FindKey(Key); + const_iterator find(StringRef Key) const { return find(Key, hash(Key)); } + + const_iterator find(StringRef Key, uint32_t FullHashValue) const { + int Bucket = FindKey(Key, FullHashValue); if (Bucket == -1) return end(); return const_iterator(TheTable + Bucket, true); @@ -294,7 +314,13 @@ /// if and only if the insertion takes place, and the iterator component of /// the pair points to the element with key equivalent to the key of the pair. std::pair insert(std::pair KV) { - return try_emplace(KV.first, std::move(KV.second)); + return try_emplace_with_hash(KV.first, hash(KV.first), + std::move(KV.second)); + } + + std::pair insert(std::pair KV, + uint32_t FullHashValue) { + return try_emplace_with_hash(KV.first, FullHashValue, std::move(KV.second)); } /// Inserts elements from range [first, last). If multiple elements in the @@ -327,8 +353,15 @@ /// if and only if the insertion takes place, and the iterator component of /// the pair points to the element with key equivalent to the key of the pair. template - std::pair try_emplace(StringRef Key, ArgsTy &&... Args) { - unsigned BucketNo = LookupBucketFor(Key); + std::pair try_emplace(StringRef Key, ArgsTy &&...Args) { + return try_emplace_with_hash(Key, hash(Key), std::forward(Args)...); + } + + template + std::pair try_emplace_with_hash(StringRef Key, + uint32_t FullHashValue, + ArgsTy &&...Args) { + unsigned BucketNo = LookupBucketFor(Key, FullHashValue); StringMapEntryBase *&Bucket = TheTable[BucketNo]; if (Bucket && Bucket != getTombstoneVal()) return std::make_pair(iterator(TheTable + BucketNo, false), Index: llvm/lib/Support/StringMap.cpp =================================================================== --- llvm/lib/Support/StringMap.cpp +++ llvm/lib/Support/StringMap.cpp @@ -11,7 +11,6 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/StringMap.h" -#include "llvm/Support/DJB.h" #include "llvm/Support/MathExtras.h" using namespace llvm; @@ -80,11 +79,14 @@ /// specified bucket will be non-null. Otherwise, it will be null. In either /// case, the FullHashValue field of the bucket will be set to the hash value /// of the string. -unsigned StringMapImpl::LookupBucketFor(StringRef Name) { +unsigned StringMapImpl::LookupBucketFor(StringRef Name, + uint32_t FullHashValue) { +#ifdef EXPENSIVE_CHECKS + assert(FullHashValue == hash(Name)); +#endif // Hash table unallocated so far? if (NumBuckets == 0) init(16); - unsigned FullHashValue = djbHash(Name, 0); unsigned BucketNo = FullHashValue & (NumBuckets - 1); unsigned *HashTable = getHashTable(TheTable, NumBuckets); @@ -136,10 +138,12 @@ /// FindKey - Look up the bucket that contains the specified key. If it exists /// in the map, return the bucket number of the key. Otherwise return -1. /// This does not modify the map. -int StringMapImpl::FindKey(StringRef Key) const { +int StringMapImpl::FindKey(StringRef Key, uint32_t FullHashValue) const { if (NumBuckets == 0) return -1; // Really empty table? - unsigned FullHashValue = djbHash(Key, 0); +#ifdef EXPENSIVE_CHECKS + assert(FullHashValue == hash(Key)); +#endif unsigned BucketNo = FullHashValue & (NumBuckets - 1); unsigned *HashTable = getHashTable(TheTable, NumBuckets);