Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!zephyr.ens.tek.com!tekcrl!tekchips!kend
From: kend@tekchips.LABS.TEK.COM (Ken Dickey)
Newsgroups: comp.lang.lisp
Subject: Re: real time collector costs
Message-ID: <5241@tekcrl.LABS.TEK.COM>
Date: 14 Dec 89 20:28:06 GMT
References: <5130@internal.Apple.COM> <5149@internal.Apple.COM> <616@pyuxf.UUCP> <5117@tekcrl.LABS.TEK.COM> <2203@cs-spool.calgary.UUCP>
Sender: ftp@tekcrl.LABS.TEK.COM
Reply-To: kend@tekchips.LABS.TEK.COM (Ken Dickey)
Organization: Tektronix, Inc., Beaverton,  OR.
Lines: 36

In article <2203@cs-spool.calgary.UUCP> gintera@cpsc.ucalgary.ca (Andrew Ginter) writes:

>In article <5117@tekcrl.LABS.TEK.COM>, Ken Dickey writes:
>> > A real time (parallel or incremental) garbage collector is roughly
>> > twice as costly as a comparable stop-and-collect collector ...
>>
>> This is not the case if you use your VM hardware.  See "Real-time
>> Concurrent Collection on Stock Multiprocessors" by Appel, Ellis, &
>> Lee; Princeton U. tech. report: CS-TR-133-88.
>
>Appel, Ellis & Li's technique reduces the cost of checking for
>forwarding pointers.  It does nothing to address the performance
>penalty associated with the increased frequency of garbage collection
>in a real time or incremental system (Philip L. Waldler, CACM, Sept/76).
>Waldler concludes that parallel collectors consume twice the resources
>of serial collectors, almost all of the time, even when using algorithms
>without any forwarding pointers.
>
>Andrew Ginter, 403-282-2984, gintera@CPSC.UCALGARY.CA, Ginter@UNCAMULT.BITNET


In looking at Walder's model, I see that the `twice as costly' result
applies only to the mark-sweep collection strategy presented in the
paper.  There are other assumptions violated as well (GC now is 2-3%
of CPU, not 10-30%, because these assumptions have changed).

Increased time to `context-switch' between the collector and the
mutator is the only time difference involved between Appel-Ellis-Li
and stop-and-copy.  The reported benchmark was "the sequential
real-time version is 11% slower than the more efficient stop-and-copy,
while the concurrent version was 18% faster" (see above, p. 15).

All of the above is moot if a particular collector is fast enough for
your particular real-time system.  Not everyone uses CONS.

-Ken