Add --dump-megamorphic-stats. Lower megamorphic cache load factor to 50%.

runtime/vm/megamorphic_cache_table.cc

Index: runtime/vm/megamorphic_cache_table.cc
diff --git a/runtime/vm/megamorphic_cache_table.cc b/runtime/vm/megamorphic_cache_table.cc
index 3a55d5a36badb11e43328d1861e21f1af12d725c..9b80f80127846d75e950c02f9a23d9dc5837c748 100644
--- a/runtime/vm/megamorphic_cache_table.cc
+++ b/runtime/vm/megamorphic_cache_table.cc
@@ -91,14 +91,64 @@ void MegamorphicCacheTable::PrintSizes(Isolate* isolate) {
   const GrowableObjectArray& table = GrowableObjectArray::Handle(
       isolate->object_store()->megamorphic_cache_table());
   if (table.IsNull()) return;
+  intptr_t max_size = 0;
   for (intptr_t i = 0; i < table.Length(); i++) {
     cache ^= table.At(i);
     buckets = cache.buckets();
     size += MegamorphicCache::InstanceSize();
     size += Array::InstanceSize(buckets.Length());
+    if (buckets.Length() > max_size) {
+      max_size = buckets.Length();
+    }
   }
   OS::Print("%" Pd " megamorphic caches using %" Pd "KB.\n",
             table.Length(), size / 1024);
+
+  intptr_t* probe_counts = new intptr_t[max_size];
+  intptr_t entry_count = 0;
+  intptr_t max_probe_count = 0;
+  for (intptr_t i = 0; i < max_size; i++) {
+    probe_counts[i] = 0;
+  }
+  for (intptr_t i = 0; i < table.Length(); i++) {
+    cache ^= table.At(i);
+    buckets = cache.buckets();
+    intptr_t mask = cache.mask();
+    intptr_t capacity = mask + 1;
+    for (intptr_t j = 0; j < capacity; j++) {
+      intptr_t class_id =
+          Smi::Value(Smi::RawCast(cache.GetClassId(buckets, j)));
+      if (class_id != kIllegalCid) {
+        intptr_t probe_count = 0;
+        intptr_t probe_index =
+            (class_id * MegamorphicCache::kSpreadFactor) & mask;
+        intptr_t probe_cid;
+        while (true) {
+          probe_count++;
+          probe_cid =
+              Smi::Value(Smi::RawCast(cache.GetClassId(buckets, probe_index)));
+          if (probe_cid == class_id) {
+            break;
+          }
+          probe_index = (probe_index + 1) & mask;
+        }
+        probe_counts[probe_count]++;
+        if (probe_count > max_probe_count) {
+          max_probe_count = probe_count;
+        }
+        entry_count++;
+      }
+    }
+  }
+  intptr_t cumulative_entries = 0;
+  for (intptr_t i = 0; i <= max_probe_count; i++) {

[Ivan Posva, 2016/05/25 17:27:53]

0->1 as 0 probes have a low likelihood at succeeding.

+    cumulative_entries += probe_counts[i];
+    OS::Print("Megamorphic probe %" Pd ": %" Pd " (%lf)\n",
+              i, probe_counts[i],
+              static_cast<double>(cumulative_entries) /
+              static_cast<double>(entry_count));
+  }
+  delete probe_counts;
 }
 
 }  // namespace dart