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

runtime/vm/hash_table.h

Index: runtime/vm/hash_table.h
diff --git a/runtime/vm/hash_table.h b/runtime/vm/hash_table.h
index f4eb3758ff36dec5345dc16977adff755131c13f..15317a17fa45d720af013076fb89fe779e63d276 100644
--- a/runtime/vm/hash_table.h
+++ b/runtime/vm/hash_table.h
@@ -137,6 +137,14 @@ class HashTable : public ValueObject {
     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());
     }
@@ -154,17 +162,21 @@ class HashTable : public ValueObject {
     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++;
@@ -183,6 +195,7 @@ class HashTable : public ValueObject {
     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;
@@ -190,6 +203,7 @@ class HashTable : public ValueObject {
     while (true) {
       if (IsUnused(probe)) {
         *entry = (deleted != -1) ? deleted : probe;
+        NOT_IN_PRODUCT(UpdateCollisions(collisions);)
         return false;
       } else if (IsDeleted(probe)) {
         if (deleted == -1) {
@@ -199,8 +213,10 @@ class HashTable : public ValueObject {
         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++;
@@ -279,10 +295,63 @@ class HashTable : public ValueObject {
     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;
@@ -491,6 +560,7 @@ class HashTables : public AllStatic {
         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.