llunak created this revision.
llunak added reviewers: clayborg, chandlerc.
Herald added subscribers: dexonsmith, hiraditya.
Herald added a project: All.
llunak requested review of this revision.
Herald added projects: LLDB, LLVM.
Herald added subscribers: llvm-commits, lldb-commits.
Pool::GetConstCStringWithStringRef() may call djbHash() up to 3 times for the
same string: First from Pool::hash() when deciding which StringMap in the pool
to use, then from read-locked StringMap::find() and then possibly from
StringMap::insert() if insertion is needed.
If LLDB's index cache is enabled and everything is cached, calls to djbHash()
are ~30% of the total CPU time here when I profile lldb start. Modifying
StringMap to allow explicitly passing in a precomputed hash and calling
djbHash() just once reduces startup CPU time by ~19%.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D122974
Files:
lldb/source/Utility/ConstString.cpp
llvm/include/llvm/ADT/StringMap.h
llvm/lib/Support/StringMap.cpp
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,11 @@
/// 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,
+ unsigned FullHashValue) {
// 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 +135,9 @@
/// 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, unsigned FullHashValue) const {
if (NumBuckets == 0)
return -1; // Really empty table?
- unsigned FullHashValue = djbHash(Key, 0);
unsigned BucketNo = FullHashValue & (NumBuckets - 1);
unsigned *HashTable = getHashTable(TheTable, NumBuckets);
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 <initializer_list>
#include <iterator>
@@ -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, unsigned 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, unsigned 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,8 @@
bool empty() const { return NumItems == 0; }
unsigned size() const { return NumItems; }
+ static unsigned hash(StringRef Key) { return llvm::djbHash(Key, 0); }
+
void swap(StringMapImpl &Other) {
std::swap(TheTable, Other.TheTable);
std::swap(NumBuckets, Other.NumBuckets);
@@ -215,15 +226,19 @@
StringMapKeyIterator<ValueTy>(end()));
}
- iterator find(StringRef Key) {
- int Bucket = FindKey(Key);
+ iterator find(StringRef Key) { return find(Key, hash(Key)); }
+
+ iterator find(StringRef Key, unsigned 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, unsigned FullHashValue) const {
+ int Bucket = FindKey(Key, FullHashValue);
if (Bucket == -1)
return end();
return const_iterator(TheTable + Bucket, true);
@@ -294,7 +309,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<iterator, bool> insert(std::pair<StringRef, ValueTy> 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<iterator, bool> insert(std::pair<StringRef, ValueTy> KV,
+ unsigned 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 +348,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 <typename... ArgsTy>
- std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
- unsigned BucketNo = LookupBucketFor(Key);
+ std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&...Args) {
+ return try_emplace_with_hash(Key, hash(Key), std::forward<ArgsTy>(Args)...);
+ }
+
+ template <typename... ArgsTy>
+ std::pair<iterator, bool> try_emplace_with_hash(StringRef Key,
+ unsigned 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: lldb/source/Utility/ConstString.cpp
===================================================================
--- lldb/source/Utility/ConstString.cpp
+++ lldb/source/Utility/ConstString.cpp
@@ -100,11 +100,12 @@
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);
+ const uint8_t h = hash(string_hash);
{
llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
- auto it = m_string_pools[h].m_string_map.find(string_ref);
+ auto it = m_string_pools[h].m_string_map.find(string_ref, string_hash);
if (it != m_string_pools[h].m_string_map.end())
return it->getKeyData();
}
@@ -112,7 +113,8 @@
llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
StringPoolEntryType &entry =
*m_string_pools[h]
- .m_string_map.insert(std::make_pair(string_ref, nullptr))
+ .m_string_map
+ .insert(std::make_pair(string_ref, nullptr), string_hash)
.first;
return entry.getKeyData();
}
@@ -125,12 +127,14 @@
const char *demangled_ccstr = nullptr;
{
- const uint8_t h = hash(demangled);
+ const uint32_t demangled_hash = StringPool::hash(demangled);
+ const uint8_t h = hash(demangled_hash);
llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].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;
+ StringPoolEntryType &entry =
+ *map.try_emplace_with_hash(demangled, demangled_hash).first;
entry.second = mangled_ccstr;
@@ -172,7 +176,10 @@
protected:
uint8_t hash(const llvm::StringRef &s) const {
- uint32_t h = llvm::djbHash(s);
+ return hash(StringPool::hash(s));
+ }
+
+ uint8_t hash(uint32_t h) const {
return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
}
_______________________________________________
lldb-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
