I'd like to add addr field into EntryInfo struct.

I'd like to add addr field into EntryInfo struct.
This will give us the ability to keep entries_ list sorted by id.
And based on that fact we will be able to use it for:
1) GetNodeById method and drop sorted version of entries list in HeapSnapshot;
2) building heap stats;
3) doing the fill stage instead of second iteration over heap.

BUG=none
TEST=none
R=yurys

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

[mnaganov (inactive), 2012-04-10 13:50:13]

The description isn't very clear: "This will give us the ability to keep
entries_ list in sorted by id state."

 - what is "id state"? Did you mean simply "id"?

 - not sure, how does adding the 'addr' field help to keep the list sorted by
id. This is just happens because ids increase, and we add new entries to the
tail of the list.

Did you mean, that adding the 'addr' field will allow to do fast reverse lookups
from id to address, having that 'entries_' list is naturally sorted by id?

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

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.cc:1345: int
HeapObjectsMap::UpdateEntryInfoAddress(Address addr,
I don't see a clear reason for having EntryInfo lookup and address update in a
single function. I think, restricting the scope to only making a lookup will
make it more clean. Also this should simplify logic in MoveObject (see below).

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.cc:1372: UpdateEntryInfoAddress(to, to_hash, NULL);
Why are you making 2 map lookups here?

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

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.h:736: int UpdateEntryInfoAddress(Address addr, uint32_t
hash, Address new_addr);
hash -> addr_hash. Otherwise, it's not clear where it belongs to.

[yurys, 2012-04-10 14:03:35]

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

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.cc:1340: ASSERT((uint32_t)entries_->length() >=
entries_map_.occupancy());
Please use static_cast<uint32_t>

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.cc:1362: // 1. lookup for From address entry in the map
and update EntryInfo.addr.
From -> |from|, To -> |to|

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.cc:1372: UpdateEntryInfoAddress(to, to_hash, NULL);
This is an overhead, we should instead do
 entries_->at(entry_index).addr = to;
below line 1374, this way we will need 1 Lookup less.

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.cc:1385: ASSERT((uint32_t)entries_->length() >=
entries_map_.occupancy());
static_cast please.

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.cc:1396: ASSERT((uint32_t)entries_->length() >=
entries_map_.occupancy());
ditto

https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
src/profile-generator.cc:1425: ASSERT((uint32_t)entries_->length() ==
entries_map_.occupancy());
ditto.

[loislo, 2012-04-10 14:22:10]

On 2012/04/10 13:50:13, Mikhail Naganov (Chromium) wrote:
> The description isn't very clear: "This will give us the ability to keep
> entries_ list in sorted by id state."
> 
>  - what is "id state"? Did you mean simply "id"?

yep. I mean sorted by id

>  - not sure, how does adding the 'addr' field help to keep the list sorted by
> id. This is just happens because ids increase, and we add new entries to the
> tail of the list.

It was true only until the first call of RemoveDeadEntries
This method iterated over hash map and the new_entries list became unsorted.

> 
> Did you mean, that adding the 'addr' field will allow to do fast reverse
lookups
> from id to address, having that 'entries_' list is naturally sorted by id?

At this moment we are using HeapSnaphot entries list that also is unsorted and
we do sorting 
specially for GetNodeById.

> 
>
https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator.cc
> File src/profile-generator.cc (right):
> 
>
https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
> src/profile-generator.cc:1345: int
> HeapObjectsMap::UpdateEntryInfoAddress(Address addr,
> I don't see a clear reason for having EntryInfo lookup and address update in a
> single function. I think, restricting the scope to only making a lookup will
> make it more clean. Also this should simplify logic in MoveObject (see below).

It is a bit complex thing.
I have to update address in From EntryInfo because the object was moved.

Also I have to clean address in To EntryInfo because I use it RemoveDeadEntries
method.
If I have skipped the last step I would have removed this To address from the
entries_map because
To EntryInfo hasn't been marked as accessed.

> 
>
https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
> src/profile-generator.cc:1372: UpdateEntryInfoAddress(to, to_hash, NULL);
> Why are you making 2 map lookups here?

I can't avoid the first lookup for From address because I have no Remove method
which returns the value of removed entry.
I can't avoid second lookup for To address because I can't distinguish the case
when I got a new entry with NULL as the value and the case when I got an old
entry with 0 as entry_index.

I've plan to fix both the cases later.

> 
> https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator.h
> File src/profile-generator.h (right):
> 
>
https://chromiumcodereview.appspot.com/10031032/diff/1/src/profile-generator....
> src/profile-generator.h:736: int UpdateEntryInfoAddress(Address addr, uint32_t
> hash, Address new_addr);
> hash -> addr_hash. Otherwise, it's not clear where it belongs to.

[loislo, 2012-04-10 16:00:26]

comments addressed.
HashMap::Return is returning the value of removed element
A dummy element is inserted into entries_ list.

[yurys, 2012-04-10 16:46:35]

lgtm

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/profile-generat...
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/profile-generat...
src/profile-generator.cc:1319: entries_->Add(EntryInfo(0, NULL));
Could you add a comment that it is for simplifying HeapObjectsMap::MoveObject ?

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/profile-generat...
src/profile-generator.cc:1377: ASSERT(static_cast<uint32_t>(entries_->length())
> entries_map_.occupancy());
Comment on why it is strictly greater?

[alexeif, 2012-04-10 16:55:24]

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/profile-generat...
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/profile-generat...
src/profile-generator.cc:1388: ASSERT((uint32_t)entries_->length() >
entries_map_.occupancy());
still ditto ;-)

[mnaganov (inactive), 2012-04-10 21:12:04]

Overall looks good.

Please change in the description "to keep entries_ list in sorted by id state"
-> "to keep 'entries_' list sorted by id"

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/hashmap.h
File src/hashmap.h (right):

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/hashmap.h#newco...
src/hashmap.h:65: // Removes the entry with matching key.
Please update the comment.

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/profile-generat...
File src/profile-generator.cc (right):

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/profile-generat...
src/profile-generator.cc:1350: ASSERT(from != to);
I'm sure you will be hitting this assert. I think you should remove it.

https://chromiumcodereview.appspot.com/10031032/diff/6001/src/profile-generat...
src/profile-generator.cc:1373: ASSERT(entries_->length() == 1 ||
The first part seems to be superfluous, as if entries_ contains only the dummy
element, its id -- 0 will not exceed any other id.