More on Garbage Collection.

[Raul Deluth Miller]

Here's another paper on Garbage Collection that might be of interest.

	ftp://ftp2.netcom.com/pub/hb/hbaker/NoMotionGC.html

Here's an extract:

************
INTRODUCTION
************

In 1978, we presented a relatively simple storage management algorithm using
garbage collection ("GC") which was "real-time" ("RT"), in the sense that all
of its operations could be bounded by a small constant, except for allocation,
which was bounded by a small constant times the size of the object being
allocated [[[Baker78].]] Since initialization requires time proportional to
the size of the new object, this algorithm was optimum, to within a constant
factor.  The key ideas of the paper were the tricolor marking scheme and the
use of the allocation pointer as a clock to measure the "time" until the
garbage collection must be finished.

Our 1978 paper had two major goals--to show that garbage collection could be
done in real time, and to show a relatively practical algorithm.  After the
discovery of the proof shown in that paper, and before the discovery of the
particular algorithm shown in that paper, we considered a number of different
strategies for implementing a real-time garbage collector.  The search space
included a number of different dimensions, including copying v.  non-copying,
breadth-first v.  depth-first, mark-sweep v.  non-mark-sweep.  The copying GC
which appeared in the paper was chosen because 1) it was space-efficient,
which appeared to be important for an embedded computer with all "real"
(non-virtual) memory; 2) it compacted by copying, which allowed for the
simplest allocation strategy--pointer incrementation; and 3) it had a single
phase, unlike the 2-phase mark-sweep algorithm.

We have since learned that compile-time garbage collection should be used
whenever possible [[[Chase87]]] [[[Chase88]]] [[[Hederman88]]] [[[Baker90];]]
that stack allocation should be used more often [[[Baker91b];]] that
functional objects should be treated differently from non-functional objects
[[[Baker93];]] that depth-first copying often causes fewer faults in a virtual
memory and/or caching environment [[[Moon84]]] [[[Andre86]]] [[[Wilson91];]]
that the asynchronous movement of objects is detrimental to compiler
optimization [[[Chase87]]] [[[Chase88];]] and that more efficient allocation
strategies exist [[[Brent89]]] [[[White91].]] A "conservative" garbage
collector [[[Boehm88]]] works much better without copying, since it can never
be sure that all pointers to an object have been found and updated.  Due to
the greater perceived costs of copying and due to the greater perceived
benefits of not copying, it now seems worthwhile to revisit an algorithm which
lost the initial real-time GC face-off.

......................................................................

Note that some of the cross references in this paper are stale.

Hopefully, this will be fixed before too long.

-- 
Raul D. Miller          N=:((*/pq)&|)@                 NB. public e, y, n=:*/pq
<rockwell@nova.umd.edu> P=:*N/@:#               NB. */-.,e e.&factors t=:*/<:pq
                        1=t|e*d    NB. (,-:<:)pq is four large primes, e medium
x-:d P,:y=:e P,:x                  NB. (d P,:y)-:D P*:N^:(i.#D)y [. D=:|.@#.d











-- 
Raul D. Miller          N=:((*/pq)&|)@                 NB. public e, y, n=:*/pq
<rockwell@nova.umd.edu> P=:*N/@:#               NB. */-.,e e.&factors t=:*/<:pq
                        1=t|e*d    NB. (,-:<:)pq is four large primes, e medium
x-:d P,:y=:e P,:x                  NB. (d P,:y)-:D P*:N^:(i.#D)y [. D=:|.@#.d