Move young independent handles to the end of the global handle's list.

Move young independent handles to the end of the global handle's list.

This allows to reduce that pressure on scavenge: when searching for objects weakly reachable through independent handles it only has to iterate over a tail of the handle's list.

The downside of this CL is that handle's list is now double linked.

[antonm, 2011-05-23 19:44:19]

DBC

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc
File src/global-handles.cc (right):

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode114
src/global-handles.cc:114: void
GlobalHandles::Node::ClearWeakness(GlobalHandles* global_handles) {
do we want to persist independence related state across MakeWeak/ClearWeakness
calls, maybe they should reset independence flags?

And shouldn't clearweakness move the handler out of the suffix as it's not
collectible anymore?

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode221
src/global-handles.cc:221: } else if (first_deallocated()) {
just FYI:  I recently thought about it, and chances really are we don't need
both free and deallocated since we allocate the stuff from the pool anyway.  I
should have probably cleaned it up before.  In any event it may compensate for
newly added complexity.

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode226
src/global-handles.cc:226: if (head() != NULL) head()->set_prev(result);
nit: mixed style: it's (first_free()) in old code vs. if (head() != NULL),
probably should be unified

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode272
src/global-handles.cc:272: if (node->is_in_independent_tail_) {
is it possible for this to be true?  if node wasn't independent, it should not
have belonged to independent tail unless there is a bug, no?

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode347
src/global-handles.cc:347: if (!current->independent_) continue;
shouldn't it always hold: ASSERT(current->independent_)?  At least the name
suggests that :)

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode361
src/global-handles.cc:361: if (!current->independent_) continue;
ditto

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode420
src/global-handles.cc:420: node->is_in_independent_tail_ = false;
is it mandatory here?  apparently you overwrite it later anyway.

http://codereview.chromium.org/7062004/diff/1/src/global-handles.h
File src/global-handles.h (right):

http://codereview.chromium.org/7062004/diff/1/src/global-handles.h#newcode355
src/global-handles.h:355: State state_ : 4;  // Need one more bit for MSVC as it
treats enums as signed.
nit: apparently more than 80 chars (or my browser is wrong).

http://codereview.chromium.org/7062004/diff/1/src/global-handles.h#newcode397
src/global-handles.h:397: void set_head(Node* value) {
it might be more easier to reason about this code if you introduce reset_head
which is called on tear down and assume that value != NULL in set_head itself

http://codereview.chromium.org/7062004/diff/1/src/global-handles.h#newcode402
src/global-handles.h:402: !value->independent_) {
given that set_head is invoked from ::Create, is it fine for value->independent_
to be true?  And this flag should be reset by following Initialize, no?

http://codereview.chromium.org/7062004/diff/1/src/global-handles.h#newcode411
src/global-handles.h:411: // This list forms a suffix of the whole list of
nodes.
in veryfyheap, can we assert this?  or overall, do some more verification?

http://codereview.chromium.org/7062004/diff/1/src/global-handles.h#newcode428
src/global-handles.h:428: 
nit: extra blank line?

[Vyacheslav Egorov (Chromium), 2011-05-23 20:08:15]

Thanks for looking at this, Anton. 

See my comments inline.

Both Vitaly and me don't like the increasing complexity of the code, so VItaly
is trying to see if there is a better approach. I tried/thought about several
last week but they really do not play well (single linked list is really not
very flexible data structure).

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc
File src/global-handles.cc (right):

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode114
src/global-handles.cc:114: void
GlobalHandles::Node::ClearWeakness(GlobalHandles* global_handles) {
On 2011/05/23 19:44:19, antonm wrote:
> do we want to persist independence related state across MakeWeak/ClearWeakness
> calls, maybe they should reset independence flags?
>

I think independence is more a property of an object not a property of a handle
so I don't think ClearWeak should clean it. 

It's just an unfortunate design tradeoff that independence became property of a
handle.
 
> And shouldn't clearweakness move the handler out of the suffix as it's not
> collectible anymore?

The invariant of the tail is: if object is young and independent it's in the
tail. But converse of the invariant does not have to hold. I will update the
comments to make it more clear.

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode221
src/global-handles.cc:221: } else if (first_deallocated()) {
On 2011/05/23 19:44:19, antonm wrote:
> just FYI:  I recently thought about it, and chances really are we don't need
> both free and deallocated since we allocate the stuff from the pool anyway.  I
> should have probably cleaned it up before.  In any event it may compensate for
> newly added complexity.

Well if we can remove "free" stuff than I don't need a double linked list --- a
single linked list will suffice. 

If there is not "reuse" in the middle of the list then the following assumption
will hold --- a handle is mark as independent soon after creation so we can find
it's "prev" by linear search. 

What do you think, Vitaly?

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode272
src/global-handles.cc:272: if (node->is_in_independent_tail_) {
On 2011/05/23 19:44:19, antonm wrote:
> is it possible for this to be true?  if node wasn't independent, it should not
> have belonged to independent tail unless there is a bug, no?

Yes it is. If the handle is destroyed and reused without GC in between.

Also see the comment about invariant of the tail above.

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode347
src/global-handles.cc:347: if (!current->independent_) continue;
On 2011/05/23 19:44:19, antonm wrote:
> shouldn't it always hold: ASSERT(current->independent_)?  At least the name
> suggests that :)

It was an assertion initially but... see above :-)

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode361
src/global-handles.cc:361: if (!current->independent_) continue;
On 2011/05/23 19:44:19, antonm wrote:
> ditto

ditto :-)

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode420
src/global-handles.cc:420: node->is_in_independent_tail_ = false;
On 2011/05/23 19:44:19, antonm wrote:
> is it mandatory here?  apparently you overwrite it later anyway.

there is one callsite that calls UnlinkNode directly (see line 475).

[antonm, 2011-05-24 10:58:38]

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc
File src/global-handles.cc (right):

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode114
src/global-handles.cc:114: void
GlobalHandles::Node::ClearWeakness(GlobalHandles* global_handles) {
I am more concerned with is_in_independent_tail_

On 2011/05/23 20:08:15, Vyacheslav Egorov wrote:
> On 2011/05/23 19:44:19, antonm wrote:
> > do we want to persist independence related state across
MakeWeak/ClearWeakness
> > calls, maybe they should reset independence flags?
> >
> 
> I think independence is more a property of an object not a property of a
handle
> so I don't think ClearWeak should clean it. 
> 
> It's just an unfortunate design tradeoff that independence became property of
a
> handle.
>  
> > And shouldn't clearweakness move the handler out of the suffix as it's not
> > collectible anymore?
> 
> The invariant of the tail is: if object is young and independent it's in the
> tail. But converse of the invariant does not have to hold. I will update the
> comments to make it more clear.

I thought it need to be weak as well.  I am probably misinterpreting your CL,
but I thought the whole idea was to traverse the smaller set.  And all you need
is to traverse weak independent handles.  Hence all my questions :)

> 
> 
>

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode221
src/global-handles.cc:221: } else if (first_deallocated()) {
Not free, but deallocated.

On 2011/05/23 20:08:15, Vyacheslav Egorov wrote:
> On 2011/05/23 19:44:19, antonm wrote:
> > just FYI:  I recently thought about it, and chances really are we don't need
> > both free and deallocated since we allocate the stuff from the pool anyway. 
I
> > should have probably cleaned it up before.  In any event it may compensate
for
> > newly added complexity.
> 
> Well if we can remove "free" stuff than I don't need a double linked list ---
a
> single linked list will suffice. 
> 
> If there is not "reuse" in the middle of the list then the following
assumption
> will hold --- a handle is mark as independent soon after creation so we can
find
> it's "prev" by linear search. 
> 
> What do you think, Vitaly?

http://codereview.chromium.org/7062004/diff/1/src/global-handles.cc#newcode420
src/global-handles.cc:420: node->is_in_independent_tail_ = false;
Maybe it should go to this callsite then, but it's a nit.

On 2011/05/23 20:08:15, Vyacheslav Egorov wrote:
> On 2011/05/23 19:44:19, antonm wrote:
> > is it mandatory here?  apparently you overwrite it later anyway.
> 
> there is one callsite that calls UnlinkNode directly (see line 475).