New heap profiler: implement fast retaining sizes approximation.

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);

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

[mnaganov (inactive), 2010-11-19 16:56:27]

http://codereview.chromium.org/5154007/diff/1/src/profile-generator-inl.h
File src/profile-generator-inl.h (right):

http://codereview.chromium.org/5154007/diff/1/src/profile-generator-inl.h#new...
src/profile-generator-inl.h:126: void HeapEntriesMap::UpdateEntries(Visitor*
visitor) {
Just moved this code down to match classes declaration order.

[Søren Thygesen Gjesse, 2010-11-22 09:49:48]

LGTM

How expensive is the dominator and approx. size calculation when taking the
snapshot?

http://codereview.chromium.org/5154007/diff/1/include/v8-profiler.h
File include/v8-profiler.h (right):

http://codereview.chromium.org/5154007/diff/1/include/v8-profiler.h#newcode318
include/v8-profiler.h:318: * Returns a dominator node. This is the node that
participates in every
is the -> is a?

[mnaganov (inactive), 2010-11-22 16:43:56]

Algorithmic complexity for dominators calculation is O(N + E * D) for each
iteration, (N is number of nodes, E is number of edges, D is size of largest
dominators set). The number of iterations is about 6 for Gmail.

Size calculation is indeed not so effective. It takes about 200 iterations for
Gmail. I will fix that. Thanks for turning my attention to this issue.

http://codereview.chromium.org/5154007/diff/1/include/v8-profiler.h
File include/v8-profiler.h (right):

http://codereview.chromium.org/5154007/diff/1/include/v8-profiler.h#newcode318
include/v8-profiler.h:318: * Returns a dominator node. This is the node that
participates in every
On 2010/11/22 09:49:48, Søren Gjesse wrote:
> is the -> is a?

Done.