[MLton-devel] generational gc design

[Stephen Weeks]

I thought I'd send a short note describing the design of the
generational GC that I am starting work on.

In summary, it will use 2-generations, with copying collection on the
nursery and either mark-compact or copying for the old generation,
based on heap size as it is now.  It will use card marking to record
intergenerational pointers.  I'll start with 256 heap bytes per card,
with one byte in the cardmap for each card to record the dirty bit.
It will use a crossing map to record which cards start with heap
objects, again with on byte per card to record the bit.  So, the space
overhead of the bitmaps will be under 1%.

The heap layout will be as follows (drawing is not to scale -- card
map and cross map are < 1% of the space)

 --------------------------------------------------------------------------
| card map | cross map |    old generation    |   to space   |   nursery   |
 --------------------------------------------------------------------------

The frontier and limit point to the nursery, and allocation and limit
checks are as always.  Each minor gc will copy from the nursery into to
space, appending on to the old generation.  After each minor gc, the
card map will be cleared, the cross map will be updated (for the new
cards in the old generation), and the remaining heap will be split in
half.  This will happen until the old generation fills some fraction
of the heap, say 9/10, at which point a major gc will occur.  The
major gc will use exactly the same strategy that we do now for
deciding between mark-compact and copying collection -- if the
estimated amount of live data plus the from space size fits in memory,
then do a copying GC, else do a mark-compact GC.

The only change to the mutator is that it needs to update the card map
upon pointer assignment into refs and arrays.  I'll add some code to
the SSA to RSSA translation to do this.  I think the update can be
done with a shift (of the address being stored into), a load (of a
value stored in gcState -- the card map base minus the shifted old
generation base), an add, and a store (into the card map).

I'll put the mutator changes in first, so that we can measure the time
and code space costs solely on the mutator.


-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel