Collects unused maps that are only kept alive by map transitions....

Collects unused maps that are only kept alive by map transitions.

If a map has descendents in the map transition tree that are alive,
it is kept.  Only maps such that they and all their descendants
have no live objects are collected.  This happens in mark-sweep and
mark-compact garbage collections.

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

[Kevin Millikin (Chromium), 2008-10-23 11:33:58]

Mostly minor comments below (plus the issue with remembered sets mentioned
offline).

http://codereview.chromium.org/8099/diff/1/4
File src/flag-definitions.h (right):

http://codereview.chromium.org/8099/diff/1/4#newcode246
Line 246: DEFINE_bool(collect_maps, true, "drop maps that seem abandoned during
GC")
Don't make this a debug only flag.

http://codereview.chromium.org/8099/diff/1/8
File src/mark-compact.cc (right):

http://codereview.chromium.org/8099/diff/1/8#newcode143
Line 143: Heap::map_space()->CreateBackPointers();
It might be more obvious to move this to MarkCompactCollector::CollectGarbage,
before the call to Prepare.

http://codereview.chromium.org/8099/diff/1/8#newcode455
Line 455: Object *object = Memory::Object_at(
Object* object ...

http://codereview.chromium.org/8099/diff/1/8#newcode457
Line 457: if (object->IsHeapObject()) {
We should try to avoid the situation where adding a field to maps breaks this
code.  Maybe we should consider putting the descriptors last and all the other
pointers together and looping over them (the pointers), then documenting why
that has to be the case in the layout part of class Map.

http://codereview.chromium.org/8099/diff/1/8#newcode478
Line 478: d->SetMark();
Consider moving this after the marking of the contents, and adding a comment
that pushing it will cause the *unmarked* children (only) to be recursively
marked.

http://codereview.chromium.org/8099/diff/1/8#newcode488
Line 488: // If the pair (details, value) at index 2i, 2i+1 is not
i, i+1 ?

http://codereview.chromium.org/8099/diff/1/8#newcode869
Line 869: Object* next = map;
For some reason, I think "parent" is a more evocative name....

http://codereview.chromium.org/8099/diff/1/8#newcode870
Line 870: MapWord next_map = map->map_word();  // No public or default
constructor.
Here, next_map_word (or parent_map_word), since it's not a map.

http://codereview.chromium.org/8099/diff/1/5
File src/mark-compact.h (right):

http://codereview.chromium.org/8099/diff/1/5#newcode202
Line 202: static void ClearDeadTransitions();
ClearNonLiveTransitions better fits the terminology used already.

http://codereview.chromium.org/8099/diff/1/2
File src/objects.cc (right):

http://codereview.chromium.org/8099/diff/1/2#newcode4051
Line 4051: #ifdef DEBUG
I think it's clearer to move the comment "Verify target." inside the #ifdef
DEBUG, and move the #endif to after all the asserts.

http://codereview.chromium.org/8099/diff/1/2#newcode4059
Line 4059: source_prototype->IsOddball());
Can it really be an oddball other than null?

http://codereview.chromium.org/8099/diff/1/2#newcode4064
Line 4064: // Point target back to source.
Explain why set_prototype is undesirable here ('this' is not a JS object or
null, and we can avoid the write barrier).

http://codereview.chromium.org/8099/diff/1/2#newcode4072
Line 4072: // DescriptorArray objects may be marked, so we must use
Is it more clear to say that live descriptor arrays (ie, the ones we consider
here) *will* be marked?

http://codereview.chromium.org/8099/diff/1/2#newcode4084
Line 4084: // check if the target is dead.  If so, null the descriptor.
I like non-live as the opposite of live (or simply unmarked).  It doesn't sound
so harsh :)

http://codereview.chromium.org/8099/diff/1/7
File src/spaces.cc (right):

http://codereview.chromium.org/8099/diff/1/7#newcode2025
Line 2025: HeapObjectIterator* iterator = new
HeapObjectIterator(Heap::map_space());
new HeapObjectIterator(this)

http://codereview.chromium.org/8099/diff/1/7#newcode2026
Line 2026: while (iterator->has_next_object()) {
has_next()

http://codereview.chromium.org/8099/diff/1/7#newcode2027
Line 2027: Object* next_object = iterator->next_object();
next()

http://codereview.chromium.org/8099/diff/1/3
File src/spaces.h (right):

http://codereview.chromium.org/8099/diff/1/3#newcode1456
Line 1456: void CreateBackPointers();
You might consider calling this "CreateParentPointers" to emphasize how it
affects the map-transition tree.  You might also consider making it a (static)
member function of the full garbage collector.

[William Hesse, 2008-10-23 12:51:21]

http://codereview.chromium.org/8099/diff/1/8
File src/mark-compact.cc (right):

http://codereview.chromium.org/8099/diff/1/8#newcode455
Line 455: Object *object = Memory::Object_at(
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> Object* object ...

Done.

http://codereview.chromium.org/8099/diff/1/8#newcode457
Line 457: if (object->IsHeapObject()) {
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> We should try to avoid the situation where adding a field to maps breaks this
> code.  Maybe we should consider putting the descriptors last and all the other
> pointers together and looping over them (the pointers), then documenting why
> that has to be the case in the layout part of class Map.

Yeah, maybe we should.

http://codereview.chromium.org/8099/diff/1/8#newcode478
Line 478: d->SetMark();
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> Consider moving this after the marking of the contents, and adding a comment
> that pushing it will cause the *unmarked* children (only) to be recursively
> marked.

Done.

http://codereview.chromium.org/8099/diff/1/8#newcode488
Line 488: // If the pair (details, value) at index 2i, 2i+1 is not
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> i, i+1 ?

Done.

http://codereview.chromium.org/8099/diff/1/8#newcode869
Line 869: Object* next = map;
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> For some reason, I think "parent" is a more evocative name....

Done.

http://codereview.chromium.org/8099/diff/1/8#newcode870
Line 870: MapWord next_map = map->map_word();  // No public or default
constructor.
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> Here, next_map_word (or parent_map_word), since it's not a map.

Done.

http://codereview.chromium.org/8099/diff/1/2
File src/objects.cc (right):

http://codereview.chromium.org/8099/diff/1/2#newcode4051
Line 4051: #ifdef DEBUG
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> I think it's clearer to move the comment "Verify target." inside the #ifdef
> DEBUG, and move the #endif to after all the asserts.

Done.

http://codereview.chromium.org/8099/diff/1/2#newcode4059
Line 4059: source_prototype->IsOddball());
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> Can it really be an oddball other than null?

Done.

http://codereview.chromium.org/8099/diff/1/2#newcode4064
Line 4064: // Point target back to source.
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> Explain why set_prototype is undesirable here ('this' is not a JS object or
> null, and we can avoid the write barrier).

Done.

http://codereview.chromium.org/8099/diff/1/2#newcode4072
Line 4072: // DescriptorArray objects may be marked, so we must use
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> Is it more clear to say that live descriptor arrays (ie, the ones we consider
> here) *will* be marked?

Done.

http://codereview.chromium.org/8099/diff/1/2#newcode4084
Line 4084: // check if the target is dead.  If so, null the descriptor.
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> I like non-live as the opposite of live (or simply unmarked).  It doesn't
sound
> so harsh :)

Done.

http://codereview.chromium.org/8099/diff/1/7
File src/spaces.cc (right):

http://codereview.chromium.org/8099/diff/1/7#newcode2025
Line 2025: HeapObjectIterator* iterator = new
HeapObjectIterator(Heap::map_space());
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> new HeapObjectIterator(this)

Done.  Actually, 
HeapObjectIterator iterator(Heap::map_space());
A stack object, not a memory leak.

http://codereview.chromium.org/8099/diff/1/7#newcode2026
Line 2026: while (iterator->has_next_object()) {
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> has_next()

Done.

http://codereview.chromium.org/8099/diff/1/3
File src/spaces.h (right):

http://codereview.chromium.org/8099/diff/1/3#newcode1456
Line 1456: void CreateBackPointers();
On 2008/10/23 11:33:58, Kevin Millikin wrote:
> You might consider calling this "CreateParentPointers" to emphasize how it
> affects the map-transition tree.  You might also consider making it a (static)
> member function of the full garbage collector.

Done.

[bak, 2008-10-23 13:43:54]

Otherwise LGTM,
  Lars

http://codereview.chromium.org/8099/diff/22/209
File src/mark-compact.cc (right):

http://codereview.chromium.org/8099/diff/22/209#newcode81
Line 81: if (FLAG_collect_maps) {
make this a one liner.

http://codereview.chromium.org/8099/diff/22/209#newcode142
Line 142: if (FLAG_collect_maps) {
One line

http://codereview.chromium.org/8099/diff/22/209#newcode457
Line 457: Object* object = Memory::Object_at(
Make abstraction instead of make three copies of the code.

   Mark(map->field_at(Map::kConstructorOffset))

or something.

http://codereview.chromium.org/8099/diff/22/209#newcode486
Line 486: if (d != Heap::empty_descriptor_array()) {
Top avoid the deep nested code in NewJSArrayWithElements,
please make a new function to handle the DescriptorArray.

http://codereview.chromium.org/8099/diff/22/209#newcode533
Line 533: if (map->instance_type() >= FIRST_JS_OBJECT_TYPE &&
This test should match the test IsJSObject.
>= FIRST_JS_OBJECT_TYPE is sufficient.

http://codereview.chromium.org/8099/diff/22/209#newcode781
Line 781: static int CountMarkedCallback(HeapObject* obj) {
Should this be wrapped in #ifdef DEBUG?

http://codereview.chromium.org/8099/diff/22/205
File src/objects.cc (right):

http://codereview.chromium.org/8099/diff/22/205#newcode4053
Line 4053: Object* target_prototype = target->prototype();
I do not understand why the "!= NULL" asserts are providing value.

[William Hesse, 2008-10-29 09:41:35]

http://codereview.chromium.org/8099/diff/22/209
File src/mark-compact.cc (right):

http://codereview.chromium.org/8099/diff/22/209#newcode81
Line 81: if (FLAG_collect_maps) {
On 2008/10/23 13:43:54, bak wrote:
> make this a one liner.

Done.

http://codereview.chromium.org/8099/diff/22/209#newcode142
Line 142: if (FLAG_collect_maps) {
On 2008/10/23 13:43:54, bak wrote:
> One line

Done.