Revision: 5867
Author: [email protected]
Date: Mon Nov 22 06:00:40 2010
Log: New heap profiler: implement fast retaining sizes approximation.
Approximation is done by building a dominators tree for the heap graph.
Dominator nodes and retained sizes are serialized into JSON.
Removed:
- reachable size (it is useless, after all);
- HeapEntryCalculatedData (size is now stored in the node, retaining
paths in a hash map);
Review URL: http://codereview.chromium.org/5154007
http://code.google.com/p/v8/source/detail?r=5867
Modified:
/branches/bleeding_edge/include/v8-profiler.h
/branches/bleeding_edge/src/api.cc
/branches/bleeding_edge/src/profile-generator-inl.h
/branches/bleeding_edge/src/profile-generator.cc
/branches/bleeding_edge/src/profile-generator.h
/branches/bleeding_edge/src/utils.h
/branches/bleeding_edge/test/cctest/test-heap-profiler.cc
=======================================
--- /branches/bleeding_edge/include/v8-profiler.h Thu Nov 18 02:49:34 2010
+++ /branches/bleeding_edge/include/v8-profiler.h Mon Nov 22 06:00:40 2010
@@ -282,16 +282,19 @@
/** Returns node's own size, in bytes. */
int GetSelfSize() const;
- /** Returns node's network (self + reachable nodes) size, in bytes. */
- int GetReachableSize() const;
-
/**
* Returns node's retained size, in bytes. That is, self + sizes of
* the objects that are reachable only from this object. In other
* words, the size of memory that will be reclaimed having this node
* collected.
+ *
+ * Exact retained size calculation has O(N) (number of nodes)
+ * computational complexity, while approximate has O(1). It is
+ * assumed that initially heap profiling tools provide approximate
+ * sizes for all nodes, and then exact sizes are calculated for the
+ * most 'interesting' nodes.
*/
- int GetRetainedSize() const;
+ int GetRetainedSize(bool exact) const;
/** Returns child nodes count of the node. */
int GetChildrenCount() const;
@@ -310,6 +313,12 @@
/** Returns a retaining path by index. */
const HeapGraphPath* GetRetainingPath(int index) const;
+
+ /**
+ * Returns a dominator node. This is the node that participates in every
+ * path from the snapshot root to the current node.
+ */
+ const HeapGraphNode* GetDominatorNode() const;
};
=======================================
--- /branches/bleeding_edge/src/api.cc Thu Nov 18 02:38:25 2010
+++ /branches/bleeding_edge/src/api.cc Mon Nov 22 06:00:40 2010
@@ -4763,15 +4763,9 @@
}
-int HeapGraphNode::GetReachableSize() const {
- IsDeadCheck("v8::HeapSnapshot::GetReachableSize");
- return ToInternal(this)->ReachableSize();
-}
-
-
-int HeapGraphNode::GetRetainedSize() const {
+int HeapGraphNode::GetRetainedSize(bool exact) const {
IsDeadCheck("v8::HeapSnapshot::GetRetainedSize");
- return ToInternal(this)->RetainedSize();
+ return ToInternal(this)->RetainedSize(exact);
}
@@ -4812,6 +4806,12 @@
return reinterpret_cast<const HeapGraphPath*>(
ToInternal(this)->GetRetainingPaths()->at(index));
}
+
+
+const HeapGraphNode* HeapGraphNode::GetDominatorNode() const {
+ IsDeadCheck("v8::HeapSnapshot::GetDominatorNode");
+ return reinterpret_cast<const
HeapGraphNode*>(ToInternal(this)->dominator());
+}
const HeapGraphNode* HeapSnapshotsDiff::GetAdditionsRoot() const {
=======================================
--- /branches/bleeding_edge/src/profile-generator-inl.h Thu Nov 18 02:38:25
2010
+++ /branches/bleeding_edge/src/profile-generator-inl.h Mon Nov 22 06:00:40
2010
@@ -103,22 +103,6 @@
void CodeMap::DeleteCode(Address addr) {
tree_.Remove(addr);
}
-
-
-template<class Visitor>
-void HeapEntriesMap::UpdateEntries(Visitor* visitor) {
- for (HashMap::Entry* p = entries_.Start();
- p != NULL;
- p = entries_.Next(p)) {
- EntryInfo* entry_info = reinterpret_cast<EntryInfo*>(p->value);
- entry_info->entry = visitor->GetEntry(
- reinterpret_cast<HeapObject*>(p->key),
- entry_info->children_count,
- entry_info->retainers_count);
- entry_info->children_count = 0;
- entry_info->retainers_count = 0;
- }
-}
CodeEntry* ProfileGenerator::EntryForVMState(StateTag tag) {
@@ -136,6 +120,22 @@
default: return NULL;
}
}
+
+
+template<class Visitor>
+void HeapEntriesMap::UpdateEntries(Visitor* visitor) {
+ for (HashMap::Entry* p = entries_.Start();
+ p != NULL;
+ p = entries_.Next(p)) {
+ EntryInfo* entry_info = reinterpret_cast<EntryInfo*>(p->value);
+ entry_info->entry = visitor->GetEntry(
+ reinterpret_cast<HeapObject*>(p->key),
+ entry_info->children_count,
+ entry_info->retainers_count);
+ entry_info->children_count = 0;
+ entry_info->retainers_count = 0;
+ }
+}
} } // namespace v8::internal
=======================================
--- /branches/bleeding_edge/src/profile-generator.cc Thu Nov 18 02:38:25
2010
+++ /branches/bleeding_edge/src/profile-generator.cc Mon Nov 22 06:00:40
2010
@@ -869,12 +869,13 @@
snapshot_ = snapshot;
type_ = type;
painted_ = kUnpainted;
- calculated_data_index_ = kNoCalculatedData;
name_ = name;
id_ = id;
self_size_ = self_size;
+ retained_size_ = 0;
children_count_ = children_count;
retainers_count_ = retainers_count;
+ dominator_ = NULL;
}
@@ -904,30 +905,16 @@
}
-int HeapEntry::ReachableSize() {
- if (calculated_data_index_ == kNoCalculatedData) {
- calculated_data_index_ = snapshot_->AddCalculatedData();
- }
- return snapshot_->GetCalculatedData(
- calculated_data_index_).ReachableSize(this);
-}
-
-
-int HeapEntry::RetainedSize() {
- if (calculated_data_index_ == kNoCalculatedData) {
- calculated_data_index_ = snapshot_->AddCalculatedData();
- }
- return snapshot_->GetCalculatedData(
- calculated_data_index_).RetainedSize(this);
+int HeapEntry::RetainedSize(bool exact) {
+ if (exact && (retained_size_ & kExactRetainedSizeTag) == 0) {
+ CalculateExactRetainedSize();
+ }
+ return retained_size_ & (~kExactRetainedSizeTag);
}
List<HeapGraphPath*>* HeapEntry::GetRetainingPaths() {
- if (calculated_data_index_ == kNoCalculatedData) {
- calculated_data_index_ = snapshot_->AddCalculatedData();
- }
- return snapshot_->GetCalculatedData(
- calculated_data_index_).GetRetainingPaths(this);
+ return snapshot_->GetRetainingPaths(this);
}
@@ -965,8 +952,7 @@
void HeapEntry::Print(int max_depth, int indent) {
- OS::Print("%6d %6d %6d [%llu] ",
- self_size(), ReachableSize(), RetainedSize(), id_);
+ OS::Print("%6d %6d [%llu] ", self_size(), RetainedSize(false), id_);
if (type() != kString) {
OS::Print("%s %.40s\n", TypeAsString(), name_);
} else {
@@ -1036,44 +1022,6 @@
}
-static void DeleteHeapGraphPath(HeapGraphPath** path_ptr) {
- delete *path_ptr;
-}
-
-void HeapEntryCalculatedData::Dispose() {
- if (retaining_paths_ != NULL)
retaining_paths_->Iterate(DeleteHeapGraphPath);
- delete retaining_paths_;
-}
-
-
-int HeapEntryCalculatedData::ReachableSize(HeapEntry* entry) {
- if (reachable_size_ == kUnknownSize) CalculateSizes(entry);
- return reachable_size_;
-}
-
-
-int HeapEntryCalculatedData::RetainedSize(HeapEntry* entry) {
- if (retained_size_ == kUnknownSize) CalculateSizes(entry);
- return retained_size_;
-}
-
-
-class ReachableSizeCalculator {
- public:
- ReachableSizeCalculator()
- : reachable_size_(0) {
- }
-
- int reachable_size() const { return reachable_size_; }
-
- void Apply(HeapEntry* entry) {
- reachable_size_ += entry->self_size();
- }
-
- private:
- int reachable_size_;
-};
-
class RetainedSizeCalculator {
public:
RetainedSizeCalculator()
@@ -1092,20 +1040,17 @@
int retained_size_;
};
-void HeapEntryCalculatedData::CalculateSizes(HeapEntry* entry) {
+void HeapEntry::CalculateExactRetainedSize() {
// To calculate retained size, first we paint all reachable nodes in
- // one color (and calculate reachable size as a byproduct), then we
- // paint (or re-paint) all nodes reachable from other nodes with a
- // different color. Then we consider only nodes painted with the
- // first color for calculating the retained size.
- entry->snapshot()->ClearPaint();
- ReachableSizeCalculator rch_size_calc;
- entry->ApplyAndPaintAllReachable(&rch_size_calc);
- reachable_size_ = rch_size_calc.reachable_size();
+ // one color, then we paint (or re-paint) all nodes reachable from
+ // other nodes with a different color. Then we sum up self sizes of
+ // nodes painted with the first color.
+ snapshot()->ClearPaint();
+ PaintAllReachable();
List<HeapEntry*> list(10);
- HeapEntry* root = entry->snapshot()->root();
- if (entry != root) {
+ HeapEntry* root = snapshot()->root();
+ if (this != root) {
list.Add(root);
root->paint_reachable_from_others();
}
@@ -1115,7 +1060,7 @@
for (int i = 0; i < children.length(); ++i) {
if (children[i].type() == HeapGraphEdge::kShortcut) continue;
HeapEntry* child = children[i].to();
- if (child != entry && child->not_painted_reachable_from_others()) {
+ if (child != this && child->not_painted_reachable_from_others()) {
list.Add(child);
child->paint_reachable_from_others();
}
@@ -1123,8 +1068,10 @@
}
RetainedSizeCalculator ret_size_calc;
- entry->snapshot()->IterateEntries(&ret_size_calc);
+ snapshot()->IterateEntries(&ret_size_calc);
retained_size_ = ret_size_calc.reained_size();
+ ASSERT((retained_size_ & kExactRetainedSizeTag) == 0);
+ retained_size_ |= kExactRetainedSizeTag;
}
@@ -1162,32 +1109,28 @@
};
-List<HeapGraphPath*>* HeapEntryCalculatedData::GetRetainingPaths(
- HeapEntry* entry) {
- if (retaining_paths_ == NULL) retaining_paths_ = new
List<HeapGraphPath*>(4);
- if (retaining_paths_->length() == 0 && entry->retainers().length() != 0)
{
- CachedHeapGraphPath path;
- FindRetainingPaths(entry, &path);
- }
- return retaining_paths_;
+List<HeapGraphPath*>* HeapEntry::CalculateRetainingPaths() {
+ List<HeapGraphPath*>* retaining_paths = new List<HeapGraphPath*>(4);
+ CachedHeapGraphPath path;
+ FindRetainingPaths(&path, retaining_paths);
+ return retaining_paths;
}
-void HeapEntryCalculatedData::FindRetainingPaths(
- HeapEntry* entry,
- CachedHeapGraphPath* prev_path) {
- Vector<HeapGraphEdge*> retainers = entry->retainers();
- for (int i = 0; i < retainers.length(); ++i) {
- HeapGraphEdge* ret_edge = retainers[i];
+void HeapEntry::FindRetainingPaths(CachedHeapGraphPath* prev_path,
+ List<HeapGraphPath*>* retaining_paths) {
+ Vector<HeapGraphEdge*> rets = retainers();
+ for (int i = 0; i < rets.length(); ++i) {
+ HeapGraphEdge* ret_edge = rets[i];
if (prev_path->ContainsNode(ret_edge->From())) continue;
- if (ret_edge->From() != entry->snapshot()->root()) {
+ if (ret_edge->From() != snapshot()->root()) {
CachedHeapGraphPath path(*prev_path);
path.Add(ret_edge);
- FindRetainingPaths(ret_edge->From(), &path);
+ ret_edge->From()->FindRetainingPaths(&path, retaining_paths);
} else {
HeapGraphPath* ret_path = new HeapGraphPath(*prev_path->path());
ret_path->Set(0, ret_edge);
- retaining_paths_->Add(ret_path);
+ retaining_paths->Add(ret_path);
}
}
}
@@ -1247,12 +1190,12 @@
template <> struct SnapshotSizeConstants<4> {
static const int kExpectedHeapGraphEdgeSize = 12;
- static const int kExpectedHeapEntrySize = 32;
+ static const int kExpectedHeapEntrySize = 36;
};
template <> struct SnapshotSizeConstants<8> {
static const int kExpectedHeapGraphEdgeSize = 24;
- static const int kExpectedHeapEntrySize = 40;
+ static const int kExpectedHeapEntrySize = 48;
};
} // namespace
@@ -1268,7 +1211,8 @@
root_entry_(NULL),
gc_roots_entry_(NULL),
raw_entries_(NULL),
- entries_sorted_(false) {
+ entries_sorted_(false),
+ retaining_paths_(HeapEntry::Match) {
STATIC_ASSERT(
sizeof(HeapGraphEdge) ==
SnapshotSizeConstants<sizeof(void*)>::kExpectedHeapGraphEdgeSize);
// NOLINT
@@ -1278,13 +1222,20 @@
}
-static void DisposeCalculatedData(HeapEntryCalculatedData* cdata) {
- cdata->Dispose();
+static void DeleteHeapGraphPath(HeapGraphPath** path_ptr) {
+ delete *path_ptr;
}
HeapSnapshot::~HeapSnapshot() {
DeleteArray(raw_entries_);
- calculated_data_.Iterate(DisposeCalculatedData);
+ for (HashMap::Entry* p = retaining_paths_.Start();
+ p != NULL;
+ p = retaining_paths_.Next(p)) {
+ List<HeapGraphPath*>* list =
+ reinterpret_cast<List<HeapGraphPath*>*>(p->value);
+ list->Iterate(DeleteHeapGraphPath);
+ delete list;
+ }
}
@@ -1398,12 +1349,6 @@
void HeapSnapshot::ClearPaint() {
entries_.Iterate(HeapEntryClearPaint);
}
-
-
-int HeapSnapshot::AddCalculatedData() {
- calculated_data_.Add(HeapEntryCalculatedData());
- return calculated_data_.length() - 1;
-}
HeapEntry* HeapSnapshot::AddEntry(HeapObject* object,
@@ -1430,6 +1375,144 @@
entry->Init(this, type, name, id, size, children_count, retainers_count);
return entry;
}
+
+
+void HeapSnapshot::FillReversePostorderIndexes(Vector<HeapEntry*>*
entries) {
+ ClearPaint();
+ int current_entry = 0;
+ List<HeapEntry*> nodes_to_visit;
+ nodes_to_visit.Add(root());
+ root()->paint_reachable();
+ while (!nodes_to_visit.is_empty()) {
+ HeapEntry* entry = nodes_to_visit.last();
+ Vector<HeapGraphEdge> children = entry->children();
+ bool has_new_edges = false;
+ for (int i = 0; i < children.length(); ++i) {
+ if (children[i].type() == HeapGraphEdge::kShortcut) continue;
+ HeapEntry* child = children[i].to();
+ if (!child->painted_reachable()) {
+ nodes_to_visit.Add(child);
+ child->paint_reachable();
+ has_new_edges = true;
+ }
+ }
+ if (!has_new_edges) {
+ entry->set_ordered_index(current_entry);
+ entries->at(current_entry++) = entry;
+ nodes_to_visit.RemoveLast();
+ }
+ }
+ entries->Truncate(current_entry);
+}
+
+
+static int Intersect(int i1, int i2, const Vector<HeapEntry*>& dominators)
{
+ int finger1 = i1, finger2 = i2;
+ while (finger1 != finger2) {
+ while (finger1 < finger2) finger1 =
dominators[finger1]->ordered_index();
+ while (finger2 < finger1) finger2 =
dominators[finger2]->ordered_index();
+ }
+ return finger1;
+}
+
+// The algorithm is based on the article:
+// K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
+// Softw. Pract. Exper. 4 (2001), pp. 1–10.
+void HeapSnapshot::BuildDominatorTree(const Vector<HeapEntry*>& entries,
+ Vector<HeapEntry*>* dominators) {
+ if (entries.length() == 0) return;
+ const int root_index = entries.length() - 1;
+ for (int i = 0; i < root_index; ++i) dominators->at(i) = NULL;
+ dominators->at(root_index) = entries[root_index];
+ bool changed = true;
+ while (changed) {
+ changed = false;
+ for (int i = root_index - 1; i >= 0; --i) {
+ HeapEntry* new_idom = NULL;
+ Vector<HeapGraphEdge*> rets = entries[i]->retainers();
+ int j = 0;
+ for (; j < rets.length(); ++j) {
+ if (rets[j]->type() == HeapGraphEdge::kShortcut) continue;
+ HeapEntry* ret = rets[j]->From();
+ if (dominators->at(ret->ordered_index()) != NULL) {
+ new_idom = ret;
+ break;
+ }
+ }
+ for (++j; j < rets.length(); ++j) {
+ if (rets[j]->type() == HeapGraphEdge::kShortcut) continue;
+ HeapEntry* ret = rets[j]->From();
+ if (dominators->at(ret->ordered_index()) != NULL) {
+ new_idom = entries[Intersect(ret->ordered_index(),
+ new_idom->ordered_index(),
+ *dominators)];
+ }
+ }
+ if (new_idom != NULL && dominators->at(i) != new_idom) {
+ dominators->at(i) = new_idom;
+ changed = true;
+ }
+ }
+ }
+}
+
+
+void HeapSnapshot::SetEntriesDominators() {
+ // This array is used for maintaining reverse postorder of nodes.
+ ScopedVector<HeapEntry*> ordered_entries(entries_.length());
+ FillReversePostorderIndexes(&ordered_entries);
+ ScopedVector<HeapEntry*> dominators(ordered_entries.length());
+ BuildDominatorTree(ordered_entries, &dominators);
+ for (int i = 0; i < ordered_entries.length(); ++i) {
+ ASSERT(dominators[i] != NULL);
+ ordered_entries[i]->set_dominator(dominators[i]);
+ }
+ // For nodes unreachable from root, set dominator to itself.
+ for (int i = 0; i < entries_.length(); ++i) {
+ HeapEntry* entry = entries_[i];
+ if (entry->dominator() == NULL) entry->set_dominator(entry);
+ }
+}
+
+
+void HeapSnapshot::ApproximateRetainedSizes() {
+ SetEntriesDominators();
+ // As for the dominators tree we only know parent nodes, not
+ // children, to sum up total sizes we traverse the tree level by
+ // level upwards, starting from leaves.
+ for (int i = 0; i < entries_.length(); ++i) {
+ HeapEntry* entry = entries_[i];
+ entry->set_retained_size(entry->self_size());
+ entry->set_leaf();
+ }
+ while (true) {
+ bool onlyLeaves = true;
+ for (int i = 0; i < entries_.length(); ++i) {
+ HeapEntry *entry = entries_[i], *dominator = entry->dominator();
+ if (!entry->is_processed() && dominator != entry) {
+ dominator->set_non_leaf();
+ onlyLeaves = false;
+ }
+ }
+ if (onlyLeaves) break;
+
+ for (int i = 0; i < entries_.length(); ++i) {
+ HeapEntry *entry = entries_[i], *dominator = entry->dominator();
+ if (entry->is_leaf() && dominator != entry) {
+ dominator->add_retained_size(entry->retained_size());
+ }
+ }
+
+ // Mark all current leaves as processed, reset non-leaves back to
leaves.
+ for (int i = 0; i < entries_.length(); ++i) {
+ HeapEntry* entry = entries_[i];
+ if (entry->is_leaf())
+ entry->set_processed();
+ else if (entry->is_non_leaf())
+ entry->set_leaf();
+ }
+ }
+}
HeapEntry* HeapSnapshot::GetNextEntryToInit() {
@@ -1449,6 +1532,16 @@
HeapSnapshotsDiff* HeapSnapshot::CompareWith(HeapSnapshot* snapshot) {
return collection_->CompareSnapshots(this, snapshot);
}
+
+
+List<HeapGraphPath*>* HeapSnapshot::GetRetainingPaths(HeapEntry* entry) {
+ HashMap::Entry* p =
+ retaining_paths_.Lookup(entry, HeapEntry::Hash(entry), true);
+ if (p->value == NULL) {
+ p->value = entry->CalculateRetainingPaths();
+ }
+ return reinterpret_cast<List<HeapGraphPath*>*>(p->value);
+}
template<class T>
@@ -1896,6 +1989,8 @@
}
SetRootGcRootsReference();
Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG);
+
+ snapshot_->ApproximateRetainedSizes();
}
@@ -2471,6 +2566,10 @@
writer_->AddNumber(entry->id());
writer_->AddCharacter(',');
writer_->AddNumber(entry->self_size());
+ writer_->AddCharacter(',');
+ writer_->AddNumber(entry->RetainedSize(false));
+ writer_->AddCharacter(',');
+ writer_->AddNumber(GetNodeId(entry->dominator()));
Vector<HeapGraphEdge> children = entry->children();
writer_->AddCharacter(',');
writer_->AddNumber(children.length());
@@ -2494,6 +2593,8 @@
"," JSON_S("name")
"," JSON_S("id")
"," JSON_S("self_size")
+ "," JSON_S("retained_size")
+ "," JSON_S("dominator")
"," JSON_S("children_count")
"," JSON_S("children"))
"," JSON_S("types") ":" JSON_A(
@@ -2510,6 +2611,8 @@
"," JSON_S("number")
"," JSON_S("number")
"," JSON_S("number")
+ "," JSON_S("number")
+ "," JSON_S("number")
"," JSON_O(
JSON_S("fields") ":" JSON_A(
JSON_S("type")
@@ -2529,7 +2632,8 @@
#undef JSON_O
#undef JSON_A
- const int node_fields_count = 5; //
type,name,id,self_size,children_count.
+ const int node_fields_count = 7;
+ // type,name,id,self_size,retained_size,dominator,children_count.
const int edge_fields_count = 3; // type,name|index,to_node.
List<HashMap::Entry*> sorted_nodes;
SortHashMap(&nodes_, &sorted_nodes);
=======================================
--- /branches/bleeding_edge/src/profile-generator.h Thu Nov 18 02:38:25 2010
+++ /branches/bleeding_edge/src/profile-generator.h Mon Nov 22 06:00:40 2010
@@ -528,12 +528,19 @@
const char* name() { return name_; }
uint64_t id() { return id_; }
int self_size() { return self_size_; }
+ int retained_size() { return retained_size_; }
+ void add_retained_size(int size) { retained_size_ += size; }
+ void set_retained_size(int value) { retained_size_ = value; }
+ int ordered_index() { return ordered_index_; }
+ void set_ordered_index(int value) { ordered_index_ = value; }
Vector<HeapGraphEdge> children() {
return Vector<HeapGraphEdge>(children_arr(), children_count_); }
Vector<HeapGraphEdge*> retainers() {
return Vector<HeapGraphEdge*>(retainers_arr(), retainers_count_); }
List<HeapGraphPath*>* GetRetainingPaths();
+ HeapEntry* dominator() { return dominator_; }
+ void set_dominator(HeapEntry* entry) { dominator_ = entry; }
void clear_paint() { painted_ = kUnpainted; }
bool painted_reachable() { return painted_ == kPainted; }
@@ -550,6 +557,13 @@
template<class Visitor>
void ApplyAndPaintAllReachable(Visitor* visitor);
void PaintAllReachable();
+
+ bool is_leaf() { return painted_ == kLeaf; }
+ void set_leaf() { painted_ = kLeaf; }
+ bool is_non_leaf() { return painted_ == kNonLeaf; }
+ void set_non_leaf() { painted_ = kNonLeaf; }
+ bool is_processed() { return painted_ == kProcessed; }
+ void set_processed() { painted_ = kProcessed; }
void SetIndexedReference(HeapGraphEdge::Type type,
int child_index,
@@ -564,14 +578,19 @@
void SetUnidirElementReference(int child_index, int index, HeapEntry*
entry);
int EntrySize() { return EntriesSize(1, children_count_,
retainers_count_); }
- int ReachableSize();
- int RetainedSize();
+ int RetainedSize(bool exact);
+ List<HeapGraphPath*>* CalculateRetainingPaths();
void Print(int max_depth, int indent);
static int EntriesSize(int entries_count,
int children_count,
int retainers_count);
+ static uint32_t Hash(HeapEntry* entry) {
+ return ComputeIntegerHash(
+ static_cast<uint32_t>(reinterpret_cast<uintptr_t>(entry)));
+ }
+ static bool Match(void* entry1, void* entry2) { return entry1 == entry2;
}
private:
HeapGraphEdge* children_arr() {
@@ -580,56 +599,40 @@
HeapGraphEdge** retainers_arr() {
return reinterpret_cast<HeapGraphEdge**>(children_arr() +
children_count_);
}
+ void CalculateExactRetainedSize();
+ void FindRetainingPaths(CachedHeapGraphPath* prev_path,
+ List<HeapGraphPath*>* retaining_paths);
const char* TypeAsString();
unsigned painted_: 2;
unsigned type_: 3;
- // The calculated data is stored in HeapSnapshot in
HeapEntryCalculatedData
- // entries. See AddCalculatedData and GetCalculatedData.
- int calculated_data_index_: 27;
- int self_size_;
- int children_count_;
+ int children_count_: 27;
int retainers_count_;
+ int self_size_;
+ union {
+ int ordered_index_; // Used during dominator tree building.
+ int retained_size_; // At that moment, there is no retained size yet.
+ };
+ HeapEntry* dominator_;
HeapSnapshot* snapshot_;
const char* name_;
uint64_t id_;
+ // Paints used for exact retained sizes calculation.
static const unsigned kUnpainted = 0;
static const unsigned kPainted = 1;
static const unsigned kPaintedReachableFromOthers = 2;
- static const int kNoCalculatedData = -1;
+ // Paints used for approximate retained sizes calculation.
+ static const unsigned kLeaf = 0;
+ static const unsigned kNonLeaf = 1;
+ static const unsigned kProcessed = 2;
+
+ static const int kExactRetainedSizeTag = 1;
DISALLOW_COPY_AND_ASSIGN(HeapEntry);
};
-class HeapEntryCalculatedData {
- public:
- HeapEntryCalculatedData()
- : retaining_paths_(NULL),
- reachable_size_(kUnknownSize),
- retained_size_(kUnknownSize) {
- }
- void Dispose();
-
- List<HeapGraphPath*>* GetRetainingPaths(HeapEntry* entry);
- int ReachableSize(HeapEntry* entry);
- int RetainedSize(HeapEntry* entry);
-
- private:
- void CalculateSizes(HeapEntry* entry);
- void FindRetainingPaths(HeapEntry* entry, CachedHeapGraphPath*
prev_path);
-
- List<HeapGraphPath*>* retaining_paths_;
- int reachable_size_;
- int retained_size_;
-
- static const int kUnknownSize = -1;
-
- // Allow generated copy constructor and assignment operator.
-};
-
-
class HeapGraphPath {
public:
HeapGraphPath()
@@ -687,12 +690,10 @@
int size,
int children_count,
int retainers_count);
- int AddCalculatedData();
- HeapEntryCalculatedData& GetCalculatedData(int index) {
- return calculated_data_[index];
- }
+ void ApproximateRetainedSizes();
void ClearPaint();
HeapSnapshotsDiff* CompareWith(HeapSnapshot* snapshot);
+ List<HeapGraphPath*>* GetRetainingPaths(HeapEntry* entry);
List<HeapEntry*>* GetSortedEntriesList();
template<class Visitor>
void IterateEntries(Visitor* visitor) { entries_.Iterate(visitor); }
@@ -710,6 +711,10 @@
int children_count,
int retainers_count);
HeapEntry* GetNextEntryToInit();
+ void BuildDominatorTree(const Vector<HeapEntry*>& entries,
+ Vector<HeapEntry*>* dominators);
+ void FillReversePostorderIndexes(Vector<HeapEntry*>* entries);
+ void SetEntriesDominators();
HeapSnapshotsCollection* collection_;
Type type_;
@@ -720,7 +725,7 @@
char* raw_entries_;
List<HeapEntry*> entries_;
bool entries_sorted_;
- List<HeapEntryCalculatedData> calculated_data_;
+ HashMap retaining_paths_;
#ifdef DEBUG
int raw_entries_size_;
#endif
=======================================
--- /branches/bleeding_edge/src/utils.h Mon Nov 15 05:23:30 2010
+++ /branches/bleeding_edge/src/utils.h Mon Nov 22 06:00:40 2010
@@ -325,6 +325,8 @@
ASSERT(0 <= index && index < length_);
return start_[index];
}
+
+ T& at(int i) const { return operator[](i); }
T& first() { return start_[0]; }
=======================================
--- /branches/bleeding_edge/test/cctest/test-heap-profiler.cc Thu Nov 18
02:38:25 2010
+++ /branches/bleeding_edge/test/cctest/test-heap-profiler.cc Mon Nov 22
06:00:40 2010
@@ -565,18 +565,21 @@
const v8::HeapGraphNode* x =
GetProperty(global, v8::HeapGraphEdge::kShortcut, "x");
CHECK_NE(NULL, x);
- const v8::HeapGraphNode* x_prototype =
- GetProperty(x, v8::HeapGraphEdge::kProperty, "__proto__");
- CHECK_NE(NULL, x_prototype);
const v8::HeapGraphNode* x1 =
GetProperty(x, v8::HeapGraphEdge::kProperty, "a");
CHECK_NE(NULL, x1);
const v8::HeapGraphNode* x2 =
GetProperty(x, v8::HeapGraphEdge::kProperty, "b");
CHECK_NE(NULL, x2);
- CHECK_EQ(x->GetSelfSize() * 3, x->GetRetainedSize());
- CHECK_EQ(x1->GetSelfSize(), x1->GetRetainedSize());
- CHECK_EQ(x2->GetSelfSize(), x2->GetRetainedSize());
+
+ // Test approximate sizes.
+ CHECK_EQ(x->GetSelfSize() * 3, x->GetRetainedSize(false));
+ CHECK_EQ(x1->GetSelfSize(), x1->GetRetainedSize(false));
+ CHECK_EQ(x2->GetSelfSize(), x2->GetRetainedSize(false));
+ // Test exact sizes.
+ CHECK_EQ(x->GetSelfSize() * 3, x->GetRetainedSize(true));
+ CHECK_EQ(x1->GetSelfSize(), x1->GetRetainedSize(true));
+ CHECK_EQ(x2->GetSelfSize(), x2->GetRetainedSize(true));
}
@@ -962,6 +965,67 @@
CHECK_EQ(0, a_from_b->GetChildrenCount()); // Retains nothing.
CHECK(IsNodeRetainedAs(a_from_b, 1)); // B has 1 ref to A.
}
+
+
+TEST(HeapEntryDominator) {
+ // The graph looks like this:
+ //
+ // -> node1
+ // a |^
+ // -> node5 ba
+ // a v|
+ // node6 -> node2
+ // b a |^
+ // -> node4 ba
+ // b v|
+ // -> node3
+ //
+ // The dominator for all nodes is node6.
+
+ v8::HandleScope scope;
+ LocalContext env;
+
+ CompileRun(
+ "function X(a, b) { this.a = a; this.b = b; }\n"
+ "node6 = new X(new X(new X()), new X(new X(),new X()));\n"
+ "(function(){\n"
+ "node6.a.a.b = node6.b.a; // node1 -> node2\n"
+ "node6.b.a.a = node6.a.a; // node2 -> node1\n"
+ "node6.b.a.b = node6.b.b; // node2 -> node3\n"
+ "node6.b.b.a = node6.b.a; // node3 -> node2\n"
+ "})();");
+
+ const v8::HeapSnapshot* snapshot =
+ v8::HeapProfiler::TakeSnapshot(v8::String::New("dominators"));
+
+ const v8::HeapGraphNode* global = GetGlobalObject(snapshot);
+ CHECK_NE(NULL, global);
+ const v8::HeapGraphNode* node6 =
+ GetProperty(global, v8::HeapGraphEdge::kShortcut, "node6");
+ CHECK_NE(NULL, node6);
+ const v8::HeapGraphNode* node5 =
+ GetProperty(node6, v8::HeapGraphEdge::kProperty, "a");
+ CHECK_NE(NULL, node5);
+ const v8::HeapGraphNode* node4 =
+ GetProperty(node6, v8::HeapGraphEdge::kProperty, "b");
+ CHECK_NE(NULL, node4);
+ const v8::HeapGraphNode* node3 =
+ GetProperty(node4, v8::HeapGraphEdge::kProperty, "b");
+ CHECK_NE(NULL, node3);
+ const v8::HeapGraphNode* node2 =
+ GetProperty(node4, v8::HeapGraphEdge::kProperty, "a");
+ CHECK_NE(NULL, node2);
+ const v8::HeapGraphNode* node1 =
+ GetProperty(node5, v8::HeapGraphEdge::kProperty, "a");
+ CHECK_NE(NULL, node1);
+
+ CHECK_EQ(node6, node1->GetDominatorNode());
+ CHECK_EQ(node6, node2->GetDominatorNode());
+ CHECK_EQ(node6, node3->GetDominatorNode());
+ CHECK_EQ(node6, node4->GetDominatorNode());
+ CHECK_EQ(node6, node5->GetDominatorNode());
+}
+
namespace {
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
