[base] Decrease probing in hashmap

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 66 matching lines @@
 
   // Iteration
   //
   // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) {
   //   ...
   // }
   //
   // If entries are inserted during iteration, the effect of
   // calling Next() is undefined.
   Entry* Start() const;
-  Entry* Next(Entry* p) const;
+  Entry* Next(Entry* entry) const;
 
   // Some match functions defined for convenience.
   // TODO(leszeks): This isn't really matching pointers, so the name doesn't
   // really make sense, but we should remove this entirely and template the map
   // on the matching function.
   static bool PointersMatch(typename MatchFunHelper<Key>::KeyRef key1,
                             typename MatchFunHelper<Key>::KeyRef key2) {
     return key1 == key2;
   }
 
  private:
   MatchFun match_;
   Entry* map_;
   uint32_t capacity_;
   uint32_t occupancy_;
   AllocationPolicy allocator_;
 
   Entry* map_end() const { return map_ + capacity_; }
   Entry* Probe(const Key& key, uint32_t hash) const;
+  Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value,
+                        uint32_t hash);
   void Initialize(uint32_t capacity);
   void Resize();
 };
 
 template <typename Key>
 struct MatchFunHelper {
   typedef const Key& KeyRef;
   typedef bool (*Fun)(KeyRef key1, KeyRef key2);
 };
 
@@ skipping 15 matching lines @@
 
 template <typename Key, typename Value, class AllocationPolicy>
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::~TemplateHashMapImpl() {
   allocator_.Delete(map_);
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Lookup(const Key& key,
                                                           uint32_t hash) const {
-  Entry* p = Probe(key, hash);
-  return p->exists() ? p : nullptr;
+  Entry* entry = Probe(key, hash);
+  return entry->exists() ? entry : nullptr;
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::LookupOrInsert(
     const Key& key, uint32_t hash) {
   // Find a matching entry.
-  Entry* p = Probe(key, hash);
-  if (p->exists()) {
-    return p;
+  Entry* entry = Probe(key, hash);
+  if (entry->exists()) {
+    return entry;
   }
 
-  return InsertNew(key, hash);
+  return FillEmptyEntry(entry, key, Value(), hash);
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::InsertNew(const Key& key,
                                                              uint32_t hash) {
-  // Find a matching entry.
-  Entry* p = Probe(key, hash);
-  DCHECK(!p->exists());
-
-  // No entry found; construct one in-place in the empty slot using placement
-  // new.
-  new (p) Entry(key, Value(), hash);
-  occupancy_++;
-
-  // Grow the map if we reached >= 80% occupancy.
-  if (occupancy_ + occupancy_ / 4 >= capacity_) {
-    Resize();
-    p = Probe(key, hash);
-  }
-
-  return p;
+  Entry* entry = Probe(key, hash);
+  return FillEmptyEntry(entry, key, Value(), hash);
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key,
                                                                 uint32_t hash) {
   // Lookup the entry for the key to remove.
   Entry* p = Probe(key, hash);
   if (!p->exists()) {
     // Key not found nothing to remove.
     return nullptr;
@@ skipping 47 matching lines @@
   // Clear the entry which is allowed to en emptied.
   p->clear();
   occupancy_--;
   return value;
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Clear() {
   // Mark all entries as empty.
   const Entry* end = map_end();
-  for (Entry* p = map_; p < end; p++) {
-    p->clear();
+  for (Entry* entry = map_; entry < end; entry++) {
+    entry->clear();
   }
   occupancy_ = 0;
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Start() const {
   return Next(map_ - 1);
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* p) const {
+TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* entry) const {
   const Entry* end = map_end();
-  DCHECK(map_ - 1 <= p && p < end);
-  for (p++; p < end; p++) {
-    if (p->exists()) {
-      return p;
+  DCHECK(map_ - 1 <= entry && entry < end);
+  for (entry++; entry < end; entry++) {
+    if (entry->exists()) {
+      return entry;
     }
   }
   return nullptr;
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key,
                                                          uint32_t hash) const {
   DCHECK(base::bits::IsPowerOfTwo32(capacity_));
-  Entry* p = map_ + (hash & (capacity_ - 1));
+  Entry* entry = map_ + (hash & (capacity_ - 1));
   const Entry* end = map_end();
-  DCHECK(map_ <= p && p < end);
+  DCHECK(map_ <= entry && entry < end);
 
   DCHECK(occupancy_ < capacity_);  // Guarantees loop termination.
-  while (p->exists() && (hash != p->hash || !match_(key, p->key))) {
-    p++;
-    if (p >= end) {
-      p = map_;
+  while (entry->exists() && (hash != entry->hash || !match_(key, entry->key))) {
+    entry++;
+    if (entry >= end) {
+      entry = map_;
     }
   }
 
-  return p;
+  return entry;
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, AllocationPolicy>::FillEmptyEntry(
+    Entry* entry, const Key& key, const Value& value, uint32_t hash) {
+  DCHECK(!entry->exists());
+
+  new (entry) Entry(key, value, hash);
+  occupancy_++;
+
+  // Grow the map if we reached >= 80% occupancy.
+  if (occupancy_ + occupancy_ / 4 >= capacity_) {
+    Resize();
+    entry = Probe(key, hash);
+  }
+
+  return entry;
+}
+
+template <typename Key, typename Value, class AllocationPolicy>
 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize(
     uint32_t capacity) {
   DCHECK(base::bits::IsPowerOfTwo32(capacity));
   map_ = reinterpret_cast<Entry*>(allocator_.New(capacity * sizeof(Entry)));
   if (map_ == nullptr) {
     FATAL("Out of memory: HashMap::Initialize");
     return;
   }
   capacity_ = capacity;
   Clear();
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize() {
   Entry* map = map_;
   uint32_t n = occupancy_;
 
   // Allocate larger map.
   Initialize(capacity_ * 2);
 
   // Rehash all current entries.
-  for (Entry* p = map; n > 0; p++) {
-    if (p->exists()) {
-      Entry* entry = LookupOrInsert(p->key, p->hash);
-      entry->value = p->value;
+  for (Entry* entry = map; n > 0; entry++) {
+    if (entry->exists()) {
+      Entry* new_entry = Probe(entry->key, entry->hash);
+      new_entry =
+          FillEmptyEntry(new_entry, entry->key, entry->value, entry->hash);
       n--;
     }
   }
 
   // Delete old map.
   allocator_.Delete(map);
 }
 
 // A hash map for pointer keys and values with an STL-like interface.
 template <class Key, class Value, class AllocationPolicy>
@@ skipping 45 matching lines @@
       return Iterator(this, this->LookupOrInsert(key, key->Hash()));
     }
     return Iterator(this, this->Lookup(key, key->Hash()));
   }
 };
 
 }  // namespace base
 }  // namespace v8
 
 #endif  // V8_BASE_HASHMAP_H_