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

[ant...@chromium.org]

Reviewers: Mads Ager, Kasper Lund, Søren Gjesse,

Description:
Force mark sweep instead of compact if size of map space is to big to allow
forward pointers encoding.


Please review this at http://codereview.chromium.org/507025

SVN Base: http://v8.googlecode.com/svn/branches/bleeding_edge/

Affected files:
M src/heap.h
M src/heap.cc
M src/mark-compact.cc
M src/spaces.h
M src/spaces.cc
M test/cctest/test-mark-compact.cc
M test/cctest/test-spaces.cc

[sgj...@chromium.org]

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.

http://codereview.chromium.org/507025

[sgj...@chromium.org]

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.

http://codereview.chromium.org/507025

[ant...@chromium.org]

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.

http://codereview.chromium.org/507025

[Kevin Millikin]

On Thu, Dec 17, 2009 at 11:18 PM, <ant...@chromium.org> wrote:

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

Hi Anton.  What you described would work as well, but it's three passes (one to reallocate maps and write forwarding addresses, one to adjust all map pointers in the heap, one to move maps).  You can do it in two passes using a variation of the "two finger" garbage collector, because all objects and holes in map space are the same size.

1. Count maps marked during the marking phase of a full collection.  If there are few enough maps that we can get under the encoding limit by compacting, choose to compact.

Instead of the normal sweep:

2. Compute the end address of the last live map after compaction.  You know how many maps there are and they're fixed size, so you can compute the page number and the offset in the page.

3. Use two pointers.  "to" starts at the beginning of map space.  "from" starts at the end address of the last map after compaction.  Sweep "to" to the first unmarked map, unmarking marked maps on the way.  Sweep "from" to the first marked map.  Copy this map to the hole pointed to by "to", unmark it (in its new location), write its forwarding address in its old location (tagged to distinguish it as a forwarded map---different from a live map and different from a marked non-map).

4. Continue until "to" reaches the original "from" pointer (the end of the last live map after compaction).

5. Sweep the heap normally to clear mark bits.  For objects that may contain map pointers, also sweep their body and update any forwarded maps.

6. Release unused map pages.

The advantage of the three pass approach is that it preserves order, but if we're doing mark sweeps we've already been allocating maps off the free list, so they are already not in allocation order.

[Søren Gjesse]

And Anton please go ahead with an implementation

/Søren

[Anton Muhin]

I can see now, Kevin, thanks.

yours,
anton.

> --
> v8-dev mailing list
> v8-...@googlegroups.com
> http://groups.google.com/group/v8-dev