Some more speedup to the dominators tree building in heap profiler.

src/profile-generator.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 3275 matching lines @@
 // Softw. Pract. Exper. 4 (2001), pp. 1-10.
 bool HeapSnapshotGenerator::BuildDominatorTree(
     const Vector<HeapEntry*>& entries,
     Vector<int>* dominators) {
   if (entries.length() == 0) return true;
   const int entries_length = entries.length(), root_index = entries_length - 1;
   static const int kNoDominator = -1;
   for (int i = 0; i < root_index; ++i) (*dominators)[i] = kNoDominator;
   (*dominators)[root_index] = root_index;
 
-  // We use time_stamps array to stamp entries with the iteration number
-  // when the dominance for the entry has been updated.
-  ScopedVector<int> time_stamps(entries_length);
-  for (int i = 0; i < entries_length; ++i) time_stamps[i] = -1;
+  // The affected array is used to mark those entries that may
+  // be affected because of dominators change among their retainers.
+  ScopedVector<bool> affected(entries_length);
+  for (int i = 0; i < entries_length; ++i) affected[i] = false;
   Vector<HeapGraphEdge> children = entries[root_index]->children();
   for (int i = 0; i < children.length(); ++i) {
-    // Mark the root direct children as affected on iteration zero.
-    time_stamps[children[i].to()->ordered_index()] = 0;
+    // Mark the root direct children as affected.
+    affected[children[i].to()->ordered_index()] = true;
   }
 
   int changed = 1;
-  int iteration = 0;
   const int base_progress_counter = progress_counter_;
   while (changed != 0) {
-    ++iteration;
     changed = 0;
     for (int i = root_index - 1; i >= 0; --i) {
       // If dominator of the entry has already been set to root,
       // then it can't propagate any further.
       if ((*dominators)[i] == root_index) continue;
-      // If no retainers of the entry had been updated on current
-      // or previous iteration, then this entry is not affected.
-      if (time_stamps[i] < iteration - 1) continue;
+      if (!affected[i]) continue;
+      affected[i] = false;
       int new_idom_index = kNoDominator;
       Vector<HeapGraphEdge*> rets = entries[i]->retainers();
       for (int j = 0; j < rets.length(); ++j) {
         if (rets[j]->type() == HeapGraphEdge::kShortcut) continue;
         int ret_index = rets[j]->From()->ordered_index();
         if (dominators->at(ret_index) != kNoDominator) {
           new_idom_index = new_idom_index == kNoDominator
               ? ret_index
               : Intersect(ret_index, new_idom_index, *dominators);
           // If idom has already reached the root, it doesn't make sense
           // to check other retainers.
           if (new_idom_index == root_index) break;
         }
       }
       if (new_idom_index != kNoDominator
           && dominators->at(i) != new_idom_index) {
         (*dominators)[i] = new_idom_index;
         ++changed;
         Vector<HeapGraphEdge> children = entries[i]->children();
         for (int j = 0; j < children.length(); ++j) {
-          time_stamps[children[j].to()->ordered_index()] = iteration;
+          affected[children[j].to()->ordered_index()] = true;
         }
       }
     }
     int remaining = entries_length - changed;
     ASSERT(remaining >= 0);
     progress_counter_ = base_progress_counter + remaining;
     if (!ProgressReport(true)) return false;
   }
   return true;
 }
@@ skipping 456 matching lines @@
 
 
 void HeapSnapshotJSONSerializer::SortHashMap(
     HashMap* map, List<HashMap::Entry*>* sorted_entries) {
   for (HashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p))
     sorted_entries->Add(p);
   sorted_entries->Sort(SortUsingEntryValue);
 }
 
 } }  // namespace v8::internal