[ADT] Compare strings' hashes first before comparing their values.

[jlebar]

Summary

We already have the hashes in hand, and comparing hashes should be much
more discriminatory than comparing the StringRefs' sizes.

[• rafael]

LGTM. I was finally able to benchmark it. It had no significant impact one way or the other, probably because the tables in use are fairly large.

This might help in smaller tables where collisions are more likely.

[jlebar]

Thanks a lot for the review, Rafael.

llvm/trunk/include/llvm/ADT/CachedHashString.h

template <> struct DenseMapInfo<CachedHashStringRef> {
   }
   static unsigned getHashValue(const CachedHashStringRef &S) {
     assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
     assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
     return S.hash();
   }
   static bool isEqual(const CachedHashStringRef &LHS,
                       const CachedHashStringRef &RHS) {
-    return DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val());
+    return LHS.hash() == RHS.hash() &&
+           DenseMapInfo<StringRef>::isEqual(LHS.val(), RHS.val());
   }
 };
 
 /// A container which contains a string, which it owns, plus a precomputed hash.
 ///
 /// We do not null-terminate the string.
 class CachedHashString {
   friend struct DenseMapInfo<CachedHashString>;