Path: utzoo!attcan!uunet!samsung!think!mintaka!mit-eddie!uw-beaver!ubc-cs!alberta!calgary!wglen!bonham
From: bonham@wglen.UUCP (Mike Bonham)
Newsgroups: comp.lang.lisp
Subject: Re: LISP compiler? (really future of MACL)
Summary: realtime GC costs less than you may think
Message-ID: <4@wglen.UUCP>
Date: 24 Nov 89 21:27:59 GMT
References: <5130@internal.Apple.COM> <5149@internal.Apple.COM> <616@pyuxf.UUCP> <2159@cs-spool.calgary.UUCP>
Organization: Willowglen Systems Ltd., Calgary, Ab.
Lines: 46

In article <2159@cs-spool.calgary.UUCP>, gintera@cpsc.ucalgary.ca (Andrew Ginter) writes:
> 
> A real time (parallel or incremental) garbage collector is roughly
> twice as costly as a comparable stop-and-collect collector.  The real
> time version has to collect more frequently than stop-and-copy because
> the real time version has to start it's collection well before memory
> is exhausted.  A real time "two space copying" collector is even more
> expensive because of the cost of checking for a forwarding pointer on
> every reference to GC managed memory.  Real time collectors penalize
> real performance while improving some aspects of perceived
> performance.
> 
> So if you're going to add a real time collector, make it an option.
> 
As Mr. Ginter correctly points out, the total number of CPU cycles expended
to perform incremental garbage collection is substantially greater than for
an equivalent stop-and-collect algorithm.

But as he also mentions (but perhaps doesn't emphasize enough, IMHO), if an
application involves an interactive user interface (as many Lisp programs
do!!!), then incremental GC can greatly improve the *perceived* responsiveness.
This is primarily due to two factors:

Firstly, the system can do garbage collection while waiting for the next
user-supplied command or input event, when CPU cycles would otherwise go
to waste.

Secondly, when the next user-event does come in, incremental garbage collectors
can be suspended immediately, whereas stop-and-collect garbage collectors
must run to completion (or else be aborted and rolled-back, if that's
possible and preferable).

There is no reason one can't have a two-collector system: a background,
incremental GC can clean up whatever it can during user interface rest-stops,
but when heavy computations run completely out of space the heavy-duty,
highly efficient, stop-and-collect GC is called in.

There *are* incremental GC methods (eg. linear mark-and-sweep) that don't
impose the continuous run-time penalty of checking for forwarding pointers.
Fragmentation can be dealt with periodically during a stop-and-copy GC.

Properly-done background incremental GC ought to be a win in typical
interactive applications, and no great burden in compute-bound applications, 

-- Mike Bonham       CPSC.UCalgary.CA!wglen!bonham
--