[MLton-devel] Stop-and-copy / mark-compact switch criterion

[Stephen Weeks]

Good timing -- I am currently working on the heap resizing code,
addressing the problem you mention and thinking about the interaction
with the generational GC too. I will send out an email in the next few
days summarizing the approach.  But here's an answer for now.

> However what I was trying to do was to address a behaviour that I
> found surprizing: during a self compile with gc-messages on on a
> 1Gb machine, there are first stop-and-copy GCs (first third on the
> run), followed by a transcient allocation peak which causes a
> switch to mark-compact.

I have seen this behavior too and agree it is bad.

> I think I found a better way to improve the switch criterion: in
> fact the precursor to the S&C vs. M&C decision lies in
> computeSemiSize(...). This routine nominally assigns a desired
> heap size of LIVE_RATIO*live ( = 8*live).
> 
> I am not sure this is always optimal as I think that this code
> indirectly forces the GC mode to mark-compact as soon as heap/live
> <= 9 (where heap = size of RAM * ramslop). 

I agree that this is the problem.  In fact, computeSemiSize did a much
better job up to revision 1.53 (before the mark-compact gc), and I
introduced this problem in revision 1.54 when I turned on the
mark-compact gc.  Here is computeSemiSize from 1.53.

------------------------------------------------------------
static W32 computeSemiSize (GC_state s, W64 live) {
	W32 res;

	if (live <= s->liveThresh1)
		res = min (live * LIVE_RATIO, s->halfMem);
	else if (live <= s->liveThresh2)
	        res = min (s->ramSlop * s->totalRam - live, s->halfMem);
	else if (live <= s->liveThresh3)
		res = live * LIVE_RATIO_MIN;
	else
		res = s->totalRam + s->totalSwap;
	if (s->maxHeap > 0 and res > s->maxHeap / 2)
		res = s->maxHeap / 2;
	return roundPage (s, res);
}

where:

LIVE_RATIO_MIN = 1.25
LIVE_RATIO = 8
s->liveThresh1 = s->ramSlop * s->totalRam / (1 + LIVE_RATIO);
s->liveThresh2 = s->ramSlop * s->totalRam / (1 + LIVE_RATIO_MIN);
s->liveThresh3 = (s->totalRam + s->totalSwap) / LIVE_RATIO_MIN;
------------------------------------------------------------

The important point is that when liveThresh1 < live <= liveThresh2,
the heap size was chosen so that live + size = ram.  This is the same
thing your computeSemiSize does when heap/live >= cutoff.  I agree
that this is a good thing to do.  In fact, in my working version, I
have corrected the problem by going back to a variant of the old
computeHeapSize, renamed "heapDesiredSize".  Here's what I currently
have (where s->ram = s->ramSlop * s->totalRam).

------------------------------------------------------------
static W32 heapDesiredSize (GC_state s, W64 live) {
	W32 res;

	if (s->useFixedHeap)
		res = s->fixedHeapSize;
        else if (live * (s->liveRatio + 1) <= s->ram)
		/* Cheney copying fits in RAM with desired liveRatio. */
		res = live * s->liveRatio;
	else if (live * 3 <= s->ram)
		/* Cheney copying fits in RAM with a live ratio between 3 and
		 * s->liveRatio.
		 */
		res = s->ram - live;
	else if (live * 1.5 <= s->ram)
		/* Mark compact fits in ram with a live ratio between 1.5 and 3.
		 */
		res = s->ram;
	else
		/* Require a live ratio of 1.5. */
		res = live * 1.5;
	if (DEBUG_RESIZING)
		fprintf (stderr, "%u = heapDesiredSize (%llu)\n",
				(uint)res, live);
	return res;
}
------------------------------------------------------------

So, I chose k = 3 (close to your 2.5), and explicitly made res + live
= ram.  Furthermore, if we switch to mark-compact gc, then we go ahead
and use all of ram, or even more if the live ratio would drop too
low.  Here's the code that decides whether to use copying or
mark-compact gc.

        if (not s->useFixedHeap
 		and s->heap.size < s->ram
		and heapCreate (s, &s->heap2,
					(W64)s->bytesLive + totalBytesRequested,
					s->heap.oldGenSize))
		cheneyCopy (s);
	else
		markCompact (s);

The test "s->heap.size < s->ram" is what says to try and use copying
GC (because heapDesiredSize chose the size as less than ram).

I'll do a checkin soon and send out an email describing the approach
as well as how I handle the generational stuff.


-------------------------------------------------------
This sf.net email is sponsored by: OSDN - Tired of that same old
cell phone?  Get a new here for FREE!
https://www.inphonic.com/r.asp?r=sourceforge1&refcode1=vs3390
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel