[gclist] Question from a newbie

Emery Berger emery@cs.umass.edu
Wed, 7 May 2003 00:14:05 -0400

>From the FAQ: http://www.iecc.com/gclist/GC-algorithms.html#Jargon

Data that is not reachable.

Think of completeness in terms of temporal logic: eventually all garbage
is collected.

-- emery

Emery Berger
Assistant Professor
Dept. of Computer Science
University of Massachusetts, Amherst

> -----Original Message-----
> From: owner-gclist@lists.iecc.com [mailto:owner-gclist@lists.iecc.com]
> Behalf Of Wang, Daniel Chen-An (Dan)
> Sent: Tuesday, May 06, 2003 11:42 PM
> To: moss@cs.umass.edu; Ravi Jonnalagedda
> Cc: gclist@lists.iecc.com
> Subject: Re: [gclist] Question from a newbie
> At 10:43 PM 5/6/2003, Eliot Moss wrote:
> >I think by "comprehensive" you mean what I have usually called
> "complete",
> >namely that the GC guarantees to reclaim all garbage eventually. Here
> >some things I know, since I have worked on algorithms w.r.t. this
> property:
> Just to be a nit-picker, but what do you define as "garbage"? If you
> define
> garbage to be any memory that will never be touched by the program in
> future, then there is no algorithm that has this complete garbage
> collection property. You basically have to solve the halting problem
> collect all the "garbage" under this definition.
> If you take the more traditional definition of garbage to be memory
> reachable from any valid set of pointer deferences, then your notion
> "complete" is perfectly sensible. However, the reclaim the garbage
> "eventually" definition is too loose. As I can implement a "complete"
> garbage collector by just waiting until the program terminates and
> all the space then and there.
> A tighter formal definition of "complete" collection requires you to
> define
> a procedure to estimate the space complexity of a program based on
> favorite notion of what "garbage" really is and a ideal GC. Then a
> particular GC is complete iff it reclaims enough space so that the
> of memory used by the program is asymptotically the same as the ideal
> If your program only allocates a constant amount of space, then
> all the space at the end is just as good as an ideal GC that reclaims
> unreachable data after every operation. Likewise, if you have a RC
> that doesn't handle cycles but can prove that the number of cycles is
> statically bounded, then a RC scheme could be considered "complete"
for a
> particular class of programs.
> It is the case the generational GC are "sloppy" in that they may hold
> to
> more data that a non-generational GC at any given point in the
> but
> I think it's fair to say that this sloppyness doesn't change the
> asymptotic
> space usage.
> If you want to categorize GC schemes, I think the two dimensions you
> to think about are an asymptotic notion of "completeness" as I've
> above, and another notion of "promptness". RC is prompt because they
> reclaim garbage as soon as possible.
> Copying/mark sweep are complete but not as prompt as RC when the
> can be both handled by RC and GC. Generational schemes are less
> but
> sometimes being tardy is a good thing, if the amount of work you do is
> related to the amount of "live data" and not the amount of garbage.