[m-dev.] MR_GC_check

[Zoltan Somogyi]

On 04-Mar-2003, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> Yes.  If you check in the procedure prologue (inside the loop for
> directlyrecursive tail calls, if any) it is not necessary to check before
> directly recursive calls.

Unfortunately, this is not quite true. Consider

p(...) :-
	<construct cell 1>
	q(...)
	( ... ->
		<construct cell 2>
	;
		...
	).

Even if the heap has room for both cells when entering p, the construction
of cell 2 can run out of memory if q consumed some of the memory that was
still available when entering p. We can avoid this by reserving enough memory
for both cells when entering p, but this would waste memory if the condition
of the if-then-else fails. Even if the condition succeeds, the fact that
cell 2 may not be near the top of the heap, and thus may not be near the
recently accessed part of the heap, when it is filled in can significantly
reduce the effectiveness of caches.

I think the best we can do is to take regions of code which consist solely of
(a) unifications and (b) calls to procedures for which we can prove an upper
bound on their memory allocation, and use a single heap check for each such
region. Such regions will typically be smaller than entire procedure bodies,
but they can still contain branched control structures such as switches,
so the problem of introducing heap checks into computation paths that didn't
used to have them remains. Here, profiling feedback can help: it can tell
us that factoring out the heap checks in a region will cause unnecessary
heap checks to be executed X times, while on other branches it leads to a
reduction of Y heap check executions (on the sample input). The compiler
can thus make an informed decision.

Zoltan.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------