[base] Optimise hashmaps with simple key equality

src/base/hashmap.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // The reason we write our own hash map instead of using unordered_map in STL,
 // is that STL containers use a mutex pool on debug build, which will lead to
 // deadlock when we are using async signal handler.
 
 #ifndef V8_BASE_HASHMAP_H_
 #define V8_BASE_HASHMAP_H_
@@ skipping 251 matching lines @@
           class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
     const Key& key, uint32_t hash) const {
   DCHECK(base::bits::IsPowerOfTwo32(capacity_));
   Entry* entry = map_ + (hash & (capacity_ - 1));
   const Entry* end = map_end();
   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_;
     }
   }
 
   return entry;
 }
 
 template <typename Key, typename Value, typename MatchFun,
@@ skipping 47 matching lines @@
       new_entry = FillEmptyEntry(new_entry, entry->key, entry->value,
                                  entry->hash, allocator);
       n--;
     }
   }
 
   // Delete old map.
   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;
 
  public:
   typedef bool (*MatchFun)(void*, void*);
 
   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;
 
 // 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
   STATIC_ASSERT(sizeof(Value*) == sizeof(void*));  // NOLINT
   struct value_type {
     Key* first;
     Value* second;
   };
 
   class Iterator {
@@ skipping 11 matching lines @@
         : map_(map), entry_(entry) {}
 
     const Base* map_;
     typename Base::Entry* entry_;
 
     friend 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); }
   Iterator find(Key* key, bool insert = false,
                 AllocationPolicy allocator = AllocationPolicy()) {
     if (insert) {
       return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
     }
     return Iterator(this, this->Lookup(key, key->Hash()));
   }
 };
 
 }  // namespace base
 }  // namespace v8
 
 #endif  // V8_BASE_HASHMAP_H_