Add a CachedHash structure

[• rafael]

Summary

A DenseMap doesn't store the hashes, so it needs to recompute them when the table is resized.

In some applications the hashing cost is noticeable. That is the case for example in lld for symbol names (StringRef).

This patch adds a templated structure that can wraps any value that can go in a DenseMap and caches the hash.

[sanjoy]

This lgtm, but I'd be more comfortable if @dblaikie took a peek to see if there are any C++ gotchas here.

[• rafael]

ping

[• rafael]

Add assert and tests.

[dblaikie]

Looks good apart from some optional feedback - thanks!

include/llvm/ADT/DenseMapInfo.h

34–35

I think you can remove both of these constructors if you're going to use braced init anyway?

(though I guess maybe you need the first because you want implicit conversion from T -> CachedHash)

Also, any desire to make this do the right thing for movable types? I'd probably at least add the "Val(std::move(Val))" in the ctors (whichever ones you keep, if any). That still won't be great for expensive-to-move things, but they're less of a priority & hopefully we just fix them.

unittests/ADT/DenseMapTest.cpp

512

Could just write this as ++*X.Counter if you like. Up to you.

[• rafael]

Comment at: include/llvm/ADT/DenseMapInfo.h:34-35
@@ +33,4 @@
+template <typename T> struct CachedHash {
+ CachedHash(T Val) : Val(Val) { Hash = DenseMapInfo<T>::getHashValue(Val); }
+ CachedHash(T Val, unsigned Hash) : Val(Val), Hash(Hash) {}

+ T Val;

I think you can remove both of these constructors if you're going to use braced init anyway?

(though I guess maybe you need the first because you want implicit conversion from T -> CachedHash)

Correct. And once you have the first you need the second.

Also, any desire to make this do the right thing for movable types? I'd probably at least add the "Val(std::move(Val))" in the ctors (whichever ones you keep, if any). That still won't be great for expensive-to-move things, but they're less of a priority & hopefully we just fix them.

Done.

Comment at: unittests/ADT/DenseMapTest.cpp:512
@@ +511,3 @@
+ static unsigned getHashValue(const CachedHashTest &X) {
+ (*X.Counter)++;

+ return X.Val;

Could just write this as ++*X.Counter if you like. Up to you.

Done.

Cheers,
Rafael

[Eugene.Zelenko]

Committed in r266981.

include/llvm/ADT/DenseMapInfo.h

 template<typename T>
 struct DenseMapInfo {
   //static inline T getEmptyKey();
   //static inline T getTombstoneKey();
   //static unsigned getHashValue(const T &Val);
   //static bool isEqual(const T &LHS, const T &RHS);
 };
 
+template <typename T> struct CachedHash {
+  CachedHash(T Val) : Val(Val) { Hash = DenseMapInfo<T>::getHashValue(Val); }
+  CachedHash(T Val, unsigned Hash) : Val(Val), Hash(Hash) {}
+  T Val;
+  unsigned Hash;
+};
+
+// Provide DenseMapInfo for all CachedHash<T>.
+template <typename T> struct DenseMapInfo<CachedHash<T>> {
+  static CachedHash<T> getEmptyKey() {
+    T N = DenseMapInfo<T>::getEmptyKey();
+    return {N, 0};
+  }
+  static CachedHash<T> getTombstoneKey() {
+    T N = DenseMapInfo<T>::getTombstoneKey();
+    return {N, 0};
+  }
+  static unsigned getHashValue(CachedHash<T> Val) {
+    assert(!isEqual(Val, getEmptyKey()) && "Cannot hash the empty key!");
+    assert(!isEqual(Val, getTombstoneKey()) &&
+           "Cannot hash the tombstone key!");
+    return Val.Hash;
+  }
+  static bool isEqual(CachedHash<T> A, CachedHash<T> B) {
+    return DenseMapInfo<T>::isEqual(A.Val, B.Val);
+  }
+};
+
 // Provide DenseMapInfo for all pointers.
 template<typename T>
 struct DenseMapInfo<T*> {
   static inline T* getEmptyKey() {
     uintptr_t Val = static_cast<uintptr_t>(-1);
     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
     return reinterpret_cast<T*>(Val);
   }

unittests/ADT/DenseMapTest.cpp

TEST(DenseMapCustomTest, StringRefTest) {
   EXPECT_EQ(0, M.lookup(StringRef()));
   EXPECT_EQ(0, M.lookup(StringRef("a", 0)));
   M[""] = 42;
   EXPECT_EQ(42, M.lookup(""));
   EXPECT_EQ(42, M.lookup(StringRef()));
   EXPECT_EQ(42, M.lookup(StringRef("a", 0)));
 }
 
+struct CachedHashTest {
+  unsigned Val;
+  unsigned *Counter = nullptr;
+  CachedHashTest(unsigned Val) : Val(Val) {}
+  CachedHashTest(unsigned Val, unsigned *Counter)
+      : Val(Val), Counter(Counter) {}
+};
+}
+namespace llvm {
+template <> struct DenseMapInfo<CachedHashTest> {
+  static CachedHashTest getEmptyKey() { return ~0; }
+  static CachedHashTest getTombstoneKey() { return ~0U - 1; }
+  static unsigned getHashValue(const CachedHashTest &X) {
+    (*X.Counter)++;
+    return X.Val;
+  }
+  static bool isEqual(const CachedHashTest &LHS, const CachedHashTest &RHS) {
+    return LHS.Val == RHS.Val;
+  }
+};
+}
+namespace {
+
+TEST(DenseMapCustomTest, CachedHashTest) {
+  unsigned Counter = 0;
+  CachedHashTest Val(0, &Counter);
+  DenseMap<CachedHashTest, int> Map;
+
+  Map[Val] = 0;
+  ASSERT_EQ(1u, Counter);
+
+  Map.reserve(64);
+  ASSERT_EQ(2u, Counter);
+}
+
+// Like above, but now cache the hash.
+TEST(DenseMapCustomTest, CachedHashTest2) {
+  unsigned Counter = 0;
+  CachedHashTest Val(0, &Counter);
+  typedef CachedHash<CachedHashTest> Cached;
+  DenseMap<Cached, int> Map;
+
+  Map[Val] = 0;
+  ASSERT_EQ(1u, Counter);
+
+  Map.reserve(64);
+  ASSERT_EQ(1u, Counter);
+}
+
 // Key traits that allows lookup with either an unsigned or char* key;
 // In the latter case, "a" == 0, "b" == 1 and so on.
 struct TestDenseMapInfo {
   static inline unsigned getEmptyKey() { return ~0; }
   static inline unsigned getTombstoneKey() { return ~0U - 1; }
   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
   static unsigned getHashValue(const char* Val) {
     return (unsigned)(Val[0] - 'a') * 37U;