[base] Optimise hashmaps with simple key equality

src/base/hashmap.h

Index: src/base/hashmap.h
diff --git a/src/base/hashmap.h b/src/base/hashmap.h
index d8151861cbe070457560602aab02768927d60b93..54038c5ef350d00423b0d36607e964b96b77a9bc 100644
--- a/src/base/hashmap.h
+++ b/src/base/hashmap.h
@@ -269,7 +269,7 @@ TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
   DCHECK(map_ <= entry && entry < end);
 
   DCHECK(occupancy_ < capacity_);  // Guarantees loop termination.
-  while (entry->exists() && (hash != entry->hash || !match_(key, entry->key))) {
+  while (entry->exists() && !match_(hash, entry->hash, key, entry->key)) {
     entry++;
     if (entry >= end) {
       entry = map_;
@@ -337,12 +337,31 @@ void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize(
   AllocationPolicy::Delete(map);
 }
 
+// Match function which compares hashes before executing a (potentially
+// expensive) key comparison.
+template <typename Key, typename MatchFun>
+struct HashEqualityThenKeyMatcher {
+  explicit HashEqualityThenKeyMatcher(MatchFun match) : match_(match) {}
+
+  bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1,
+                  const Key& key2) const {
+    return hash1 == hash2 && match_(key1, key2);
+  }
+
+ private:
+  MatchFun match_;
+};
+
+// Hashmap<void*, void*> which takes a custom key comparison function pointer.
 template <typename AllocationPolicy>
 class CustomMatcherTemplateHashMapImpl
-    : public TemplateHashMapImpl<void*, void*, bool (*)(void*, void*),
-                                 AllocationPolicy> {
-  typedef TemplateHashMapImpl<void*, void*, bool (*)(void*, void*),
-                              AllocationPolicy>
+    : public TemplateHashMapImpl<
+          void*, void*,
+          HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
+          AllocationPolicy> {
+  typedef TemplateHashMapImpl<
+      void*, void*, HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
+      AllocationPolicy>
       Base;
 
  public:
@@ -351,24 +370,35 @@ class CustomMatcherTemplateHashMapImpl
   CustomMatcherTemplateHashMapImpl(
       MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity,
       AllocationPolicy allocator = AllocationPolicy())
-      : Base(capacity, match, allocator) {}
+      : Base(capacity, HashEqualityThenKeyMatcher<void*, MatchFun>(match),
+             allocator) {}
 };
 
 typedef CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy>
     CustomMatcherHashMap;
 
+// Match function which compares keys directly by equality.
+template <typename Key>
+struct KeyEqualityMatcher {
+  bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1,
+                  const Key& key2) const {
+    return key1 == key2;
+  }
+};
+
+// Hashmap<void*, void*> which compares the key pointers directly.
 template <typename AllocationPolicy>
 class PointerTemplateHashMapImpl
-    : public TemplateHashMapImpl<void*, void*, std::equal_to<void*>,
+    : public TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
                                  AllocationPolicy> {
-  typedef TemplateHashMapImpl<void*, void*, std::equal_to<void*>,
+  typedef TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
                               AllocationPolicy>
       Base;
 
  public:
   PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity,
                              AllocationPolicy allocator = AllocationPolicy())
-      : Base(capacity, std::equal_to<void*>(), allocator) {}
+      : Base(capacity, KeyEqualityMatcher<void*>(), allocator) {}
 };
 
 typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap;
@@ -376,8 +406,13 @@ typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap;
 // A hash map for pointer keys and values with an STL-like interface.
 template <class Key, class Value, class MatchFun, class AllocationPolicy>
 class TemplateHashMap
-    : private TemplateHashMapImpl<void*, void*, MatchFun, AllocationPolicy> {
-  typedef TemplateHashMapImpl<void*, void*, MatchFun, AllocationPolicy> Base;
+    : private TemplateHashMapImpl<void*, void*,
+                                  HashEqualityThenKeyMatcher<void*, MatchFun>,
+                                  AllocationPolicy> {
+  typedef TemplateHashMapImpl<void*, void*,
+                              HashEqualityThenKeyMatcher<void*, MatchFun>,
+                              AllocationPolicy>
+      Base;
 
  public:
   STATIC_ASSERT(sizeof(Key*) == sizeof(void*));    // NOLINT
@@ -409,7 +444,8 @@ class TemplateHashMap
 
   TemplateHashMap(MatchFun match,
                   AllocationPolicy allocator = AllocationPolicy())
-      : Base(Base::kDefaultHashMapCapacity, match, allocator) {}
+      : Base(Base::kDefaultHashMapCapacity,
+             HashEqualityThenKeyMatcher<void*, MatchFun>(match), allocator) {}
 
   Iterator begin() const { return Iterator(this, this->Start()); }
   Iterator end() const { return Iterator(this, nullptr); }