[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..8b2e42e482bb42832f0762b7774361dc04eb16b1 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,11 +337,38 @@ 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 HashKeyComp {

[rmcilroy, 2016/09/30 16:07:15]

Not sure on the name, how about HashEqualityThenKeyMatcher (bit of a mouthful
but I can't come up with anything better.

[Leszek Swirski, 2016/10/03 14:33:27]

Neither could I, so done.

+  explicit HashKeyComp(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_;
+};
+
+// Match function which compares keys directly by equality.
+template <typename Key>
+struct KeyEqual {

[rmcilroy, 2016/09/30 16:07:15]

nit - KeyEqualityMatcher (also move down to just about where it's first used in
PointerTemplateHashMapImpl)

[Leszek Swirski, 2016/10/03 14:33:27]

Done.

+  bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1,
+                  const Key& key2) const {
+    return key1 == key2;
+  }
+};
+
+// Hashmap<void*, void*> which takes a custom key comparison function pointer.
 template <typename AllocationPolicy>
 class CustomMatcherTemplateHashMapImpl
-    : public TemplateHashMapImpl<void*, void*, bool (*)(void*, void*),
+    : public TemplateHashMapImpl<void*, void*,
+                                 HashKeyComp<void*, bool (*)(void*, void*)>,
                                  AllocationPolicy> {
-  typedef TemplateHashMapImpl<void*, void*, bool (*)(void*, void*),
+  typedef TemplateHashMapImpl<void*, void*,
+                              HashKeyComp<void*, bool (*)(void*, void*)>,
                               AllocationPolicy>
       Base;
 
@@ -351,24 +378,24 @@ class CustomMatcherTemplateHashMapImpl
   CustomMatcherTemplateHashMapImpl(
       MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity,
       AllocationPolicy allocator = AllocationPolicy())
-      : Base(capacity, match, allocator) {}
+      : Base(capacity, HashKeyComp<void*, MatchFun>(match), allocator) {}
 };
 
 typedef CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy>
     CustomMatcherHashMap;
 
+// 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*, KeyEqual<void*>,
                                  AllocationPolicy> {
-  typedef TemplateHashMapImpl<void*, void*, std::equal_to<void*>,
-                              AllocationPolicy>
+  typedef TemplateHashMapImpl<void*, void*, KeyEqual<void*>, AllocationPolicy>
       Base;
 
  public:
   PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity,
                              AllocationPolicy allocator = AllocationPolicy())
-      : Base(capacity, std::equal_to<void*>(), allocator) {}
+      : Base(capacity, KeyEqual<void*>(), allocator) {}
 };
 
 typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap;
@@ -376,8 +403,11 @@ 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*, HashKeyComp<void*, MatchFun>,
+                                  AllocationPolicy> {
+  typedef TemplateHashMapImpl<void*, void*, HashKeyComp<void*, MatchFun>,
+                              AllocationPolicy>
+      Base;
 
  public:
   STATIC_ASSERT(sizeof(Key*) == sizeof(void*));    // NOLINT
@@ -409,7 +439,8 @@ class TemplateHashMap
 
   TemplateHashMap(MatchFun match,
                   AllocationPolicy allocator = AllocationPolicy())
-      : Base(Base::kDefaultHashMapCapacity, match, allocator) {}
+      : Base(Base::kDefaultHashMapCapacity, HashKeyComp<void*, MatchFun>(match),
+             allocator) {}
 
   Iterator begin() const { return Iterator(this, this->Start()); }
   Iterator end() const { return Iterator(this, nullptr); }