[gclist] Question from a newbie

Eliot Moss moss@cs.umass.edu
Tue, 6 May 2003 22:43:13 -0400

I think by "comprehensive" you mean what I have usually called "complete",
namely that the GC guarantees to reclaim all garbage eventually. Here are
some things I know, since I have worked on algorithms w.r.t. this property:

- ref cnt is by itself incomplete, but there are cycle detection algorithms
  one can add to it (which are not generally very fast)

- mark/sweep, mark/compact, and copying can each be complete or incomplete,
  because ....

- collecting the whole heap at once, or only a portion, is a concept
  orthogonal to the allocation/reclamation technique (MS, MC, or copy, from
  the bullet above).

MOS (also called the Train algorithm), and a new algoritm called MarkCopy
(that my student just had accepted to present at OOPSLA next fall), are
both complete copying algorithms that do not ever copy the whole heap at
once. This is an area of active research.

Best wishes ....		Eliot Moss
J. Eliot B. Moss, Associate Professor     http://www.cs.umass.edu/~moss    www
Director, Arch. and Lang. Impl. Lab.      +1-413-545-4206                voice
Department of Computer Science            +1-413-695-4226                 cell
140 Governor's Drive, Room 372            +1-413-545-1249                  fax
University of Massachusetts at Amherst    moss@cs.umass.edu              email
Amherst, MA  01003-9264  USA              +1-413-545-3733 Priscilla Coe  sec'y