Split nodes and edges into separate arrays in heap profiler.

Split nodes and edges into separate arrays in heap profiler.

This allowed the following changes:
  - heap profiler now makes one pass less over the heap.
  - HeapEntriesMap does not allocate EntryInfo per each entry.
  - there's no need for an extra pass to set indexes before serialization.

As a result snapshot taking time has reduced up to 2x times.

Committed: https://code.google.com/p/v8/source/detail?r=11531

[mnaganov (inactive), 2012-05-03 15:44:31]

I like the simplification of the code and especially the speed boost!

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator-...
File src/profile-generator-inl.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator-...
src/profile-generator-inl.h:109: return this - &snapshot_->entries().first();
I'm not sure this will compile on all platforms. Have you checked Win64 for
example?

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator.cc
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1116: root_entry_(-1),
Please introduce a constant instead of the magic value.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1161: CHECK(root_entry_ == 0);
Are you using CHECKs here and below intentionally? They will remain in release
mode.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1204: children().Rewind(edges().length());
Perhaps, add a helper method to the 'List' class for this sequence of actions?

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1265: for (int i = 0; i < entries_.length(); ++i) {
I suppose, it will be a bit faster to set sorted_entries_ capacity by entries_
size before filling.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1281: entries_.capacity() * sizeof(HeapEntry) +
Perhaps, add an utility method to the 'List' class for this? It will also make
the code resilient to list item type changes.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator.h
File src/profile-generator.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:464: void Init(Type type, const char* name, int from,
int to);
You can make 'Init' to be a constructor now. The reason it was a separate
function is because we were calling it on a pre-allocated memory area. You still
need an empty constructor for List<HeapGraphEdge> though.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:466: void UpdateToEntry(HeapSnapshot* snapshot);
Perhaps, rename this method to "ReplaceToIndexWithEntry", the current name isn't
clear enough.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:493: // During entries population it uses |to_| field to
store index,
nit: During entries population |to_| is used for storing the index, afterwards
it is replaced with a pointer to the entry.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:495: int to_;
Perhaps, call this field 'to_index_' for clarity?

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:519: void Init(HeapSnapshot* snapshot,
Also can be converted into a constructor.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:538: int set_children_index(int index) {
This function isn't a trivial one-liner, so it needs to be named CamelCase and
to be moved into the .cc file (or -inl.h file if you think it needs to be
inlined).

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:544: int set_retainers_index(int index) {
ditto

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:586: HeapSnapshot* snapshot_;
Are you sure this reordering doesn't  affect entry size on Win64? MSVC loves to
add padding if wider values precede narrower ones. This was the reason why all
pointers had been put at the end.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:1138: static const int kEdgeFieldsCount = 3;
I would suggest providing a storage for this constant in the .cc file. As it is
used in expressions evaluated at runtime, some compilers might generate code
assuming that is has storage, and the program will fail to link.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:1140: static const int kNodeFieldsCount = 7;
ditto

[alexeif, 2012-05-07 11:04:35]

Thanks for the review! Please take a look.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator-...
File src/profile-generator-inl.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator-...
src/profile-generator-inl.h:109: return this - &snapshot_->entries().first();
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> I'm not sure this will compile on all platforms. Have you checked Win64 for
> example?
I'm not sure, as I don't have a Windows machine. I added a cast anyway.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator.cc
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1116: root_entry_(-1),
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> Please introduce a constant instead of the magic value.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1161: CHECK(root_entry_ == 0);
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> Are you using CHECKs here and below intentionally? They will remain in release
> mode.
I added them intentionally in places that are non performance critical. Is it
wrong? Is there a policy on ASSERT vs. CHECK usage?

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1204: children().Rewind(edges().length());
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> Perhaps, add a helper method to the 'List' class for this sequence of actions?

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1265: for (int i = 0; i < entries_.length(); ++i) {
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> I suppose, it will be a bit faster to set sorted_entries_ capacity by entries_
> size before filling.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1281: entries_.capacity() * sizeof(HeapEntry) +
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> Perhaps, add an utility method to the 'List' class for this? It will also make
> the code resilient to list item type changes.
I'm not sure this function is generic enough to be put into the list. I made it
static in the profile-generator.cc if you don't object.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator.h
File src/profile-generator.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:464: void Init(Type type, const char* name, int from,
int to);
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> You can make 'Init' to be a constructor now. The reason it was a separate
> function is because we were calling it on a pre-allocated memory area. You
still
> need an empty constructor for List<HeapGraphEdge> though.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:466: void UpdateToEntry(HeapSnapshot* snapshot);
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> Perhaps, rename this method to "ReplaceToIndexWithEntry", the current name
isn't
> clear enough.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:493: // During entries population it uses |to_| field to
store index,
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> nit: During entries population |to_| is used for storing the index, afterwards
> it is replaced with a pointer to the entry.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:495: int to_;
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> Perhaps, call this field 'to_index_' for clarity?

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:519: void Init(HeapSnapshot* snapshot,
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> Also can be converted into a constructor.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:538: int set_children_index(int index) {
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> This function isn't a trivial one-liner, so it needs to be named CamelCase and
> to be moved into the .cc file (or -inl.h file if you think it needs to be
> inlined).

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:544: int set_retainers_index(int index) {
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> ditto

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:586: HeapSnapshot* snapshot_;
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> Are you sure this reordering doesn't  affect entry size on Win64? MSVC loves
to
> add padding if wider values precede narrower ones. This was the reason why all
> pointers had been put at the end.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:1138: static const int kEdgeFieldsCount = 3;
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> I would suggest providing a storage for this constant in the .cc file. As it
is
> used in expressions evaluated at runtime, some compilers might generate code
> assuming that is has storage, and the program will fail to link.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.h:1140: static const int kNodeFieldsCount = 7;
On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> ditto

Done.

[mnaganov (inactive), 2012-05-08 12:05:20]

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator.cc
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1161: CHECK(root_entry_ == 0);
On 2012/05/07 11:04:35, alexeif wrote:
> On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> > Are you using CHECKs here and below intentionally? They will remain in
release
> > mode.
> I added them intentionally in places that are non performance critical. Is it
> wrong? Is there a policy on ASSERT vs. CHECK usage?

My feeling is that as V8 is geared towards speed, in release mode we don't do
any checks. Grepping for CHECK vs. ASSERT shows that CHECK is mostly used in
tests and for some reason in ARM code generators. Also remember that CHECK will
terminate execution. So unless you are thinking that there is some potential
problem, and you would like to get crash reports from live users to debug it, I
would stick to ASSERTs.

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/list.h
File src/list.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/list.h#newcode120
src/list.h:120: // Allocates space for 'length' elements.
nit: Please state that it also deletes current list contents.

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/profile-generat...
File src/profile-generator.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/profile-generat...
src/profile-generator.h:489: // During entries population |to_| is used for
storing the index,
nit: |to_| -> |to_index_|

https://chromiumcodereview.appspot.com/10353010/diff/7001/test/cctest/test-li...
File test/cctest/test-list.cc (right):

https://chromiumcodereview.appspot.com/10353010/diff/7001/test/cctest/test-li...
test/cctest/test-list.cc:138: CHECK_EQ(100, list.length());
Perhaps, also check that before allocate list[0] == 1, and afterwards is not?

[yurys, 2012-05-08 14:55:59]

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/profile-generat...
File src/profile-generator.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/profile-generat...
src/profile-generator.h:657: int root_entry_;
I'd rename these fields from *_entry_ to *_index_

[alexeif, 2012-05-09 12:38:06]

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator.cc
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10353010/diff/1/src/profile-generator....
src/profile-generator.cc:1161: CHECK(root_entry_ == 0);
On 2012/05/08 12:05:20, Mikhail Naganov (Chromium) wrote:
> On 2012/05/07 11:04:35, alexeif wrote:
> > On 2012/05/03 15:44:31, Mikhail Naganov (Chromium) wrote:
> > > Are you using CHECKs here and below intentionally? They will remain in
> release
> > > mode.
> > I added them intentionally in places that are non performance critical. Is
it
> > wrong? Is there a policy on ASSERT vs. CHECK usage?
> 
> My feeling is that as V8 is geared towards speed, in release mode we don't do
> any checks. Grepping for CHECK vs. ASSERT shows that CHECK is mostly used in
> tests and for some reason in ARM code generators. Also remember that CHECK
will
> terminate execution. So unless you are thinking that there is some potential
> problem, and you would like to get crash reports from live users to debug it,
I
> would stick to ASSERTs.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/list.h
File src/list.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/list.h#newcode120
src/list.h:120: // Allocates space for 'length' elements.
On 2012/05/08 12:05:20, Mikhail Naganov (Chromium) wrote:
> nit: Please state that it also deletes current list contents.

Done.

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/profile-generat...
File src/profile-generator.h (right):

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/profile-generat...
src/profile-generator.h:489: // During entries population |to_| is used for
storing the index,
On 2012/05/08 12:05:20, Mikhail Naganov (Chromium) wrote:
> nit: |to_| -> |to_index_|

Done.

https://chromiumcodereview.appspot.com/10353010/diff/7001/src/profile-generat...
src/profile-generator.h:657: int root_entry_;
On 2012/05/08 14:55:59, Yury Semikhatsky wrote:
> I'd rename these fields from *_entry_ to *_index_

Done.

https://chromiumcodereview.appspot.com/10353010/diff/7001/test/cctest/test-li...
File test/cctest/test-list.cc (right):

https://chromiumcodereview.appspot.com/10353010/diff/7001/test/cctest/test-li...
test/cctest/test-list.cc:138: CHECK_EQ(100, list.length());
On 2012/05/08 12:05:20, Mikhail Naganov (Chromium) wrote:
> Perhaps, also check that before allocate list[0] == 1, and afterwards is not?
The check for the first item being 1 after Add should be done in the test for
Add operation.
It doesn't make sense to do the check after Allocate because elements are not
initialized and contain garbage.

[mnaganov (inactive), 2012-05-09 14:10:00]

lgtm