Add usage and collision details to the hash table data structure in order to determine effectivenes…

runtime/vm/hash_table.h

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_HASH_TABLE_H_
 #define VM_HASH_TABLE_H_
 
 // Temporarily used when sorting the indices in EnumIndexHashTable.
 // TODO(koda): Remove these dependencies before using in production.
 #include <map>
@@ skipping 119 matching lines @@
     intptr_t num_entries = num_occupied + 1;
     return kFirstKeyIndex + (kEntrySize * num_entries);
   }
 
   // Initializes an empty table.
   void Initialize() const {
     ASSERT(data_->Length() >= ArrayLengthForNumOccupied(0));
     smi_handle_ = Smi::New(0);
     data_->SetAt(kOccupiedEntriesIndex, smi_handle_);
     data_->SetAt(kDeletedEntriesIndex, smi_handle_);
+
+NOT_IN_PRODUCT(
+    data_->SetAt(kNumGrowsIndex, smi_handle_);
+    data_->SetAt(kNumLT5LookupsIndex, smi_handle_);
+    data_->SetAt(kNumLT25LookupsIndex, smi_handle_);
+    data_->SetAt(kNumGT25LookupsIndex, smi_handle_);
+)  // !PRODUCT
+
     for (intptr_t i = kHeaderSize; i < data_->Length(); ++i) {
       data_->SetAt(i, Object::sentinel());
     }
   }
 
   // Returns whether 'key' matches any key in the table.
   template<typename Key>
   bool ContainsKey(const Key& key) const {
     return FindKey(key) != -1;
   }
 
   // Returns the entry that matches 'key', or -1 if none exists.
   template<typename Key>
   intptr_t FindKey(const Key& key) const {
     const intptr_t num_entries = NumEntries();
     ASSERT(NumOccupied() < num_entries);
     // TODO(koda): Add salt.
+    NOT_IN_PRODUCT(intptr_t collisions = 0;)
     uword hash = KeyTraits::Hash(key);
     intptr_t probe = hash % num_entries;
     // TODO(koda): Consider quadratic probing.
     while (true) {
       if (IsUnused(probe)) {
+        NOT_IN_PRODUCT(UpdateCollisions(collisions);)
         return -1;
       } else if (!IsDeleted(probe)) {
         key_handle_ = GetKey(probe);
         if (KeyTraits::IsMatch(key, key_handle_)) {
+          NOT_IN_PRODUCT(UpdateCollisions(collisions);)
           return probe;
         }
+        NOT_IN_PRODUCT(collisions += 1;)
       }
       // Advance probe.
       probe++;
       probe = (probe == num_entries) ? 0 : probe;
     }
     UNREACHABLE();
     return -1;
   }
 
   // Sets *entry to either:
   // - an occupied entry matching 'key', and returns true, or
   // - an unused/deleted entry where a matching key may be inserted,
   //   and returns false.
   template<typename Key>
   bool FindKeyOrDeletedOrUnused(const Key& key, intptr_t* entry) const {
     const intptr_t num_entries = NumEntries();
     ASSERT(entry != NULL);
     ASSERT(NumOccupied() < num_entries);
+    NOT_IN_PRODUCT(intptr_t collisions = 0;)
     uword hash = KeyTraits::Hash(key);
     intptr_t probe = hash % num_entries;
     intptr_t deleted = -1;
     // TODO(koda): Consider quadratic probing.
     while (true) {
       if (IsUnused(probe)) {
         *entry = (deleted != -1) ? deleted : probe;
+        NOT_IN_PRODUCT(UpdateCollisions(collisions);)
         return false;
       } else if (IsDeleted(probe)) {
         if (deleted == -1) {
           deleted = probe;
         }
       } else {
         key_handle_ = GetKey(probe);
         if (KeyTraits::IsMatch(key, key_handle_)) {
           *entry = probe;
+          NOT_IN_PRODUCT(UpdateCollisions(collisions);)
           return true;
         }
+        NOT_IN_PRODUCT(collisions += 1;)
       }
       // Advance probe.
       probe++;
       probe = (probe == num_entries) ? 0 : probe;
     }
     UNREACHABLE();
     return false;
   }
 
   // Sets the key of a previously unoccupied entry. This must not be the last
@@ skipping 58 matching lines @@
   intptr_t NumDeleted() const {
     return GetSmiValueAt(kDeletedEntriesIndex);
   }
   Object& KeyHandle() const {
     return key_handle_;
   }
   Smi& SmiHandle() const {
     return smi_handle_;
   }
 
+NOT_IN_PRODUCT(
+  intptr_t NumGrows() const {
+    return GetSmiValueAt(kNumGrowsIndex);
+  }
+  intptr_t NumLT5Collisions() const {
+    return GetSmiValueAt(kNumLT5LookupsIndex);
+  }
+  intptr_t NumLT25Collisions() const {
+    return GetSmiValueAt(kNumLT25LookupsIndex);
+  }
+  intptr_t NumGT25Collisions() const {
+    return GetSmiValueAt(kNumGT25LookupsIndex);
+  }
+  void UpdateGrowth() const {
+    AdjustSmiValueAt(kNumGrowsIndex, 1);
+  }
+  void UpdateCollisions(intptr_t collisions) const {
+    if (data_->raw()->IsVMHeapObject()) {
+      return;
+    }
+    if (collisions < 5) {
+      AdjustSmiValueAt(kNumLT5LookupsIndex, 1);
+    } else if (collisions < 25) {
+      AdjustSmiValueAt(kNumLT25LookupsIndex, 1);
+    } else {
+      AdjustSmiValueAt(kNumGT25LookupsIndex, 1);
+    }
+  }
+  void PrintStats() const {
+    if (!KeyTraits::ReportStats()) {
+      return;
+    }
+    OS::Print("Stats for %s table :\n"
+              " Size of table = %" Pd ",Number of Occupied entries = %" Pd "\n"
+              " Number of Grows = %" Pd "\n"
+              " Number of look ups with < 5 collisions = %" Pd "\n"
+              " Number of look ups with < 25 collisions = %" Pd "\n"
+              " Number of look ups with > 25 collisions = %" Pd "\n",
+              KeyTraits::Name(),
+              NumEntries(), NumOccupied(),
+              NumGrows(),
+              NumLT5Collisions(), NumLT25Collisions(), NumGT25Collisions());
+  }
+)  // !PRODUCT
+
  protected:
   static const intptr_t kOccupiedEntriesIndex = 0;
   static const intptr_t kDeletedEntriesIndex = 1;
+#if defined(PRODUCT)
   static const intptr_t kHeaderSize = kDeletedEntriesIndex + 1;
+#else
+  static const intptr_t kNumGrowsIndex = 2;
+  static const intptr_t kNumLT5LookupsIndex = 3;
+  static const intptr_t kNumLT25LookupsIndex = 4;
+  static const intptr_t kNumGT25LookupsIndex = 5;
+  static const intptr_t kHeaderSize = kNumGT25LookupsIndex + 1;
+#endif
   static const intptr_t kMetaDataIndex = kHeaderSize;
   static const intptr_t kFirstKeyIndex = kHeaderSize + kMetaDataSize;
   static const intptr_t kEntrySize = 1 + kPayloadSize;
 
   intptr_t KeyIndex(intptr_t entry) const {
     ASSERT(0 <= entry && entry < NumEntries());
     return kFirstKeyIndex + (kEntrySize * entry);
   }
 
   intptr_t PayloadIndex(intptr_t entry, intptr_t component) const {
@@ skipping 188 matching lines @@
     if (low <= current && current < high) {
       return;
     }
     double target = (low + high) / 2.0;
     intptr_t new_capacity = (1 + table.NumOccupied()) / target;
     Table new_table(New<Table>(
         new_capacity,
         table.data_->IsOld() ? Heap::kOld : Heap::kNew));
     Copy(table, new_table);
     *table.data_ = new_table.Release().raw();
+    NOT_IN_PRODUCT(table.UpdateGrowth(); table.PrintStats();)
   }
 
   // Serializes a table by concatenating its entries as an array.
   template<typename Table>
   static RawArray* ToArray(const Table& table, bool include_payload) {
     const intptr_t entry_size = include_payload ? (1 + Table::kPayloadSize) : 1;
     Array& result = Array::Handle(Array::New(table.NumOccupied() * entry_size));
     typename Table::Iterator it(&table);
     Object& obj = Object::Handle();
     intptr_t result_index = 0;
@@ skipping 207 matching lines @@
 class EnumIndexHashSet : public HashSet<EnumIndexHashTable<KeyTraits, 0> > {
  public:
   typedef HashSet<EnumIndexHashTable<KeyTraits, 0> > BaseSet;
   explicit EnumIndexHashSet(RawArray* data) : BaseSet(data) {}
   EnumIndexHashSet(Zone* zone, RawArray* data) : BaseSet(zone, data) {}
 };
 
 }  // namespace dart
 
 #endif  // VM_HASH_TABLE_H_