Force mark sweep if size of map space is to big to allow forward pointers enc...

Force mark sweep instead of compcation if size of map space is too big to allow forward pointers encoding.


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

[Søren Thygesen Gjesse, 2009-12-17 14:35:02]

LGTM

- even though this is a somewhat scary path...

Maybe we should consider putting this behind a flag but have it default to true.
This makes it easy to turn it off for testing.

The problematic part is that we will never compact the heap again nor free any
pages after map space has out-grown the size where map pointers cannot be
encoded.

We should consider adding compacting of map space (in a new CL) if the number of
live maps after a mark-sweep is below the threshold. Kevin has a idea of how to
do this:

1. Move maps into the first pages of the map space leaving a forwarding pointer
in the moved maps. This can be done using one pointer starting at the beginning
of map space and another pointer starting at the end. Sweeping backwards is
possible as we know exactly the what is in map space, however the linked list of
pages adds some complications.

2. Sweep the heap to make map pointers pointing to a forwarded map point to the
new location.

3. Free all the unused pages of map space.

[Søren Thygesen Gjesse, 2009-12-17 14:48:12]

On 2009/12/17 14:35:02, Søren Gjesse wrote:
> LGTM
> 
> - even though this is a somewhat scary path...
> 
> Maybe we should consider putting this behind a flag but have it default to
true.
> This makes it easy to turn it off for testing.
> 
> The problematic part is that we will never compact the heap again nor free any
> pages after map space has out-grown the size where map pointers cannot be
> encoded.
> 
> We should consider adding compacting of map space (in a new CL) if the number
of
> live maps after a mark-sweep is below the threshold. Kevin has a idea of how
to
> do this:
> 
> 1. Move maps into the first pages of the map space leaving a forwarding
pointer
> in the moved maps. This can be done using one pointer starting at the
beginning
> of map space and another pointer starting at the end. Sweeping backwards is
> possible as we know exactly the what is in map space, however the linked list
of
> pages adds some complications.
> 
> 2. Sweep the heap to make map pointers pointing to a forwarded map point to
the
> new location.
> 
> 3. Free all the unused pages of map space.

After talking to Kevin again the backwards scan is not required. The number of
live maps gives the number of pages of map pages required to hold all live maps.
Skip past these to find the first page from which to start relocating maps. This
page and the rest of the pages in teh map space will be free after the map
compaction.

[antonm, 2009-12-17 22:18:16]

Thanks a lot for comments, Søren.

On 2009/12/17 14:48:12, Søren Gjesse wrote:
> On 2009/12/17 14:35:02, Søren Gjesse wrote:
> > LGTM
> > 
> > - even though this is a somewhat scary path...

Agree.

> > 
> > Maybe we should consider putting this behind a flag but have it default to
> true.
> > This makes it easy to turn it off for testing.

Flag added.  Besides that I had to drop unit tests as they now (with bigger map
space) take almost eternity to finish (due to forced GC when we allocated too
much).  I did however run them artificially reducing the number of bits in map
index encoding.

> > The problematic part is that we will never compact the heap again nor free
any
> > pages after map space has out-grown the size where map pointers cannot be
> > encoded.
> > 
> > We should consider adding compacting of map space (in a new CL) if the
number
> of
> > live maps after a mark-sweep is below the threshold. Kevin has a idea of how
> to
> > do this:

Sure.

> > 1. Move maps into the first pages of the map space leaving a forwarding
> pointer
> > in the moved maps. This can be done using one pointer starting at the
> beginning
> > of map space and another pointer starting at the end. Sweeping backwards is
> > possible as we know exactly the what is in map space, however the linked
list
> of
> > pages adds some complications.
> > 
> > 2. Sweep the heap to make map pointers pointing to a forwarded map point to
> the
> > new location.
> > 
> > 3. Free all the unused pages of map space.
> 
> After talking to Kevin again the backwards scan is not required. The number of
> live maps gives the number of pages of map pages required to hold all live
maps.
> Skip past these to find the first page from which to start relocating maps.
This
> page and the rest of the pages in teh map space will be free after the map
> compaction.

Am I missing something or we could do almost a normal compact, almost as we
actually can compact across pages when compacting maps only?

It might be precisely what you and Kevin are suggesting, so let's me reformulate
how I see it:

After forced mark sweep if number of live maps dropped below some threshold we
do:

1) create backpointers once again (or probably not restore them);
2) compact using a normal bump allocation maps starting from the first page of
map space and writing forwarding address as a normal address (setting some low
bits, e.g. mark bit to be able to iterate live maps later) into a map field;
3) iterate through all the objects in the heap and for all the object adjust map
pointer and for maps prototype field as well (maybe transitions, but not sure,
hopefully backpointers should be enough) + restore meta_map;
4) move live maps to their forwarding allocations;
5) restore transitions;
6) release tail pages.

Does that sound correct?

Anyway, I'd love to implement this map compaction.