Add initial version of retainers heap profile.

Add initial version of retainers heap profile.

The profile is taken together with constructors profile. In theory, it
should represent a complete heap graph. However, this takes a lot of memory,
so it is reduced to a more compact, but still useful form. Namely:

 - objects are aggregated by their constructors, except for Array and Object
   instances, that are too hetereogeneous;

 - for Arrays and Objects, initially every instance is concerned, but then
   they are grouped together based on their retainer graph paths similarity (e.g.
   if two objects has the same retainer, they are considered equal);

Committed: http://code.google.com/p/v8/source/detail?r=2903

[Søren Thygesen Gjesse, 2009-09-16 10:35:18]

LGTM with comments.

Are all the classes in the heap-profile.h used outside heap-profile.cc otherwise
consider moving them to heap-profile.h.

I am looking forward to trying this out.

http://codereview.chromium.org/200132/diff/1/3
File src/heap-profiler.cc (right):

http://codereview.chromium.org/200132/diff/1/3#newcode78
Line 78: } else if ((*o)->IsFixedArray() && !insideArray_) {
Please comment on this logic. I assume you are traversing the properties and
elements of JSObjects here.

http://codereview.chromium.org/200132/diff/1/3#newcode110
Line 110: ConstructorHeapProfile::TreeConfig::kNoValue;
Initialize kNoValue to something.

http://codereview.chromium.org/200132/diff/1/3#newcode114
Line 114: : zscope_(DELETE_ON_EXIT) {
4 space indent of :.

http://codereview.chromium.org/200132/diff/1/3#newcode204
Line 204: if (this == &src) return *this;
Add {} to if statement.

http://codereview.chromium.org/200132/diff/1/3#newcode216
Line 216: if (cmp != 0) return cmp;
Add {} to if statements.

http://codereview.chromium.org/200132/diff/1/3#newcode221
Line 221: if (cmp != 0) return cmp;
Add {} to if statement.

http://codereview.chromium.org/200132/diff/1/3#newcode238
Line 238: if (!cluster.can_be_coarsed()) return;
Add {} to if statement.

http://codereview.chromium.org/200132/diff/1/3#newcode254
Line 254: if (currentSet_->Find(eq, &loc)) return;
Add {} to if statement.

http://codereview.chromium.org/200132/diff/1/3#newcode270
Line 270: if (last_eq_clusters == curr_eq_clusters) break;
Add {} to if statement.

http://codereview.chromium.org/200132/diff/1/3#newcode290
Line 290: if (!cluster.can_be_coarsed()) return JSObjectsCluster();
Add {} to if statement.

http://codereview.chromium.org/200132/diff/1/3#newcode329
Line 329: const JSObjectsCluster ClustersCoarser::ClusterEqualityConfig::kNoKey;
Initialize? (times 3)

http://codereview.chromium.org/200132/diff/1/3#newcode352
Line 352: if (constructor == Heap::Object_symbol() ||
Please add {}'s to if statement.

http://codereview.chromium.org/200132/diff/1/3#newcode415
Line 415: if (coarser_.HasAnEquivalent(cluster)) return;
Add {} to if statement.

http://codereview.chromium.org/200132/diff/1/3#newcode435
Line 435: ++retainers_printed_;  // avoid printing ellipsis next time.
Is there any way to add "(XXX more)" when done?

http://codereview.chromium.org/200132/diff/1/3#newcode446
Line 446: if (coarse_cluster_tree_->Insert(eq, &loc)) {
Please comment somewhere that the coarse_cluster_tree_ is used to avoid
repeatedly reporting of the same cluster - and maybe give it a different name.
Using a member variable for this type of temporary state is a bit confusing I
think.

http://codereview.chromium.org/200132/diff/1/4
File src/heap-profiler.h (right):

http://codereview.chromium.org/200132/diff/1/4#newcode91
Line 91: : constructor_(constructor), instance_(NULL) {}
4 space indent of : here (and two times just below)

http://codereview.chromium.org/200132/diff/1/4#newcode93
Line 93: : constructor_(reinterpret_cast<String*>(special)), instance_(NULL) {}
Casting 1 and 2 to String* seems a bit hackish. How about just allocating two
strings for this. They could perhaps be symbols with illegal JavaScript
identifier names.

http://codereview.chromium.org/200132/diff/1/4#newcode192
Line 192: static const int INITIAL_BACKREFS_LIST_CAPACITY = 2;
Please use kXxxYyy format for constants (times 3).

http://codereview.chromium.org/200132/diff/1/4#newcode228
Line 228: static const int MAX_RETAINERS_TO_PRINT = 50;
Please use kMaxRetainersToPrint.

http://codereview.chromium.org/200132/diff/1/12
File test/cctest/test-heap-profiler.cc (right):

http://codereview.chromium.org/200132/diff/1/12#newcode86
Line 86: if (ref1 != NULL) o_tree->Insert(*ref1, &loc);
Add {} to if statement.

http://codereview.chromium.org/200132/diff/1/12#newcode286
Line 286: if (pos != NULL) ++pos;
Add {} to if statement.

[mnaganov (inactive), 2009-09-16 13:33:52]

> Are all the classes in the heap-profile.h used outside heap profile.cc
otherwise
> consider moving them to heap-profile.h.

They are used (and tested) in unit tests.

http://codereview.chromium.org/200132/diff/1/3
File src/heap-profiler.cc (right):

http://codereview.chromium.org/200132/diff/1/3#newcode78
Line 78: } else if ((*o)->IsFixedArray() && !insideArray_) {
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Please comment on this logic. I assume you are traversing the properties and
> elements of JSObjects here.

Done. This also works for function contexts as well.

http://codereview.chromium.org/200132/diff/1/3#newcode110
Line 110: ConstructorHeapProfile::TreeConfig::kNoValue;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Initialize kNoValue to something.

It's a compound type with a default constructor. I believe, there is no need to
write anything else here.

http://codereview.chromium.org/200132/diff/1/3#newcode114
Line 114: : zscope_(DELETE_ON_EXIT) {
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> 4 space indent of :.

Done.

http://codereview.chromium.org/200132/diff/1/3#newcode204
Line 204: if (this == &src) return *this;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

I object. The style guide says "Short conditional statements may be written on
one line if this enhances readability. You may use this only when the line is
brief and the statement does not use the else clause."

I think, this is an exact case where having a one line increases readability.

http://codereview.chromium.org/200132/diff/1/3#newcode216
Line 216: if (cmp != 0) return cmp;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statements.

ditto.

http://codereview.chromium.org/200132/diff/1/3#newcode221
Line 221: if (cmp != 0) return cmp;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

ditto.

http://codereview.chromium.org/200132/diff/1/3#newcode238
Line 238: if (!cluster.can_be_coarsed()) return;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

ditto.

http://codereview.chromium.org/200132/diff/1/3#newcode254
Line 254: if (currentSet_->Find(eq, &loc)) return;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

ditto.

http://codereview.chromium.org/200132/diff/1/3#newcode270
Line 270: if (last_eq_clusters == curr_eq_clusters) break;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

ditto.

http://codereview.chromium.org/200132/diff/1/3#newcode290
Line 290: if (!cluster.can_be_coarsed()) return JSObjectsCluster();
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

ditto.

http://codereview.chromium.org/200132/diff/1/3#newcode329
Line 329: const JSObjectsCluster ClustersCoarser::ClusterEqualityConfig::kNoKey;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Initialize? (times 3)

All three are of type JSObjectsCluster, having a constructor w/o arguments.

http://codereview.chromium.org/200132/diff/1/3#newcode352
Line 352: if (constructor == Heap::Object_symbol() ||
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Please add {}'s to if statement.

Done.

http://codereview.chromium.org/200132/diff/1/3#newcode415
Line 415: if (coarser_.HasAnEquivalent(cluster)) return;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

Again, this is a short one.

http://codereview.chromium.org/200132/diff/1/3#newcode435
Line 435: ++retainers_printed_;  // avoid printing ellipsis next time.
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Is there any way to add "(XXX more)" when done?

To count w/o duplicates, we need actually to execute the whole code below, just
skipping printing. I'm limiting the number of objects here, because what we're
doing here is passing objects (with possible transformation) from one splay tree
to another, which is the worst case for the splay tree.

I'm adding a TODO here for this.

http://codereview.chromium.org/200132/diff/1/3#newcode446
Line 446: if (coarse_cluster_tree_->Insert(eq, &loc)) {
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Please comment somewhere that the coarse_cluster_tree_ is used to avoid
> repeatedly reporting of the same cluster - and maybe give it a different name.
> Using a member variable for this type of temporary state is a bit confusing I
> think.

Yes, I think I should use a dedicated helper class for that. The code would look
elegant using closures, but there are none in C++.

I think, I will rewrite this code anyway, I don't like it too. I'm adding a TODO
for myself.

http://codereview.chromium.org/200132/diff/1/4
File src/heap-profiler.h (right):

http://codereview.chromium.org/200132/diff/1/4#newcode91
Line 91: : constructor_(constructor), instance_(NULL) {}
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> 4 space indent of : here (and two times just below)

Done.

http://codereview.chromium.org/200132/diff/1/4#newcode93
Line 93: : constructor_(reinterpret_cast<String*>(special)), instance_(NULL) {}
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Casting 1 and 2 to String* seems a bit hackish. How about just allocating two
> strings for this. They could perhaps be symbols with illegal JavaScript
> identifier names.

A good idea. I've turned to use existing symbols that are illegal JS
identifiers, like ".code".

http://codereview.chromium.org/200132/diff/1/12
File test/cctest/test-heap-profiler.cc (right):

http://codereview.chromium.org/200132/diff/1/12#newcode86
Line 86: if (ref1 != NULL) o_tree->Insert(*ref1, &loc);
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

This is the short one.

http://codereview.chromium.org/200132/diff/1/12#newcode286
Line 286: if (pos != NULL) ++pos;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Add {} to if statement.

ditto.

[mnaganov (inactive), 2009-09-16 14:50:27]

http://codereview.chromium.org/200132/diff/1/4
File src/heap-profiler.h (right):

http://codereview.chromium.org/200132/diff/1/4#newcode192
Line 192: static const int INITIAL_BACKREFS_LIST_CAPACITY = 2;
On 2009/09/16 10:35:18, Søren Gjesse wrote:
> Please use kXxxYyy format for constants (times 3).

Oops, sorry, I've skipped this one and below. Will fix in the next commit.