Re: Question from a newbie

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

garbage
Data that is not reachable.

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

Regards,
-- emery

--
Emery Berger
Assistant Professor
Dept. of Computer Science
University of Massachusetts, Amherst
www.cs.umass.edu/~emery
 
 

> -----Original Message-----
> From: [email protected] [mailto:[email protected]]
On
> Behalf Of Wang, Daniel Chen-An (Dan)
> Sent: Tuesday, May 06, 2003 11:42 PM
> To: [email protected]; Ravi Jonnalagedda
> Cc: [email protected]
> 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
are
> >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
the
> future, then there is no algorithm that has this complete garbage
> collection property. You basically have to solve the halting problem
to
> collect all the "garbage" under this definition.
> 
> If you take the more traditional definition of garbage to be memory
not
> reachable from any valid set of pointer deferences, then your notion
of
> "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
reclaim
> 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
your
> 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
amount
> of memory used by the program is asymptotically the same as the ideal
GC.
> 
> If your program only allocates a constant amount of space, then
reclaiming
> all the space at the end is just as good as an ideal GC that reclaims
any
> unreachable data after every operation. Likewise, if you have a RC
scheme
> 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
on
> to
> more data that a non-generational GC at any given point in the
program,
> 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
want
> to think about are an asymptotic notion of "completeness" as I've
defined
> 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
programs
> can be both handled by RC and GC. Generational schemes are less
prompt,
> 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.