Re: Garbage Collection

[barmar@think.COM (Barry Margolin)]

In article <4073@hubcap.UUCP> wtwolfe@hubcap.clemson.edu writes:
>    Why doesn't the editor do the deletion of warnings?  If the editor
>    is already providing a "search for next warning" function, it should
>    provide the "delete warning" function as well.  Then we wouldn't have
>    to deal with shared variables at all, although your later comments do
>    make the whole question moot.

Who said that the editor doesn't provide for deletion of warnings,
too?  But that shouldn't prevent the command processor from also
deleting them.

>> Real-time GC mechanisms are defined to do a bounded amount of work PER
>> ALLOCATION.  [....]  And generational and ephemeral GC mechanisms
>> concentrate their efforts on memory most likely to contain garbage.
>
>    Could you send me a detailed explanation of these mechanisms?

The canonical reference for real-time GC is a paper, about 10 years
old, by Henry Baker.  I don't know the exact reference, but the title
included the phrases "Garbage Collection" and "Real-time", and it was
probably in something like a proceedings of a POPL conference.  The
general idea of these mechanisms is that every time an object is
allocated up to N words are scanned for non-garbage objects to be
copied.

My reference for ephemeral GC is David Moon's paper, approximately
titled "Garbage Collection in Large Virtual Memory Systems", which is
in the proceedings of the first (or maybe second) ACM Lisp Conference.
I don't know what the references for generational GC's are; recent
Lisp and Functional Programming Conference proceedings are probably a
good place to look.

>> Decent GC mechanisms can be told to ignore manually managed space.  
>
>    If this means that I can specify that my allocation requests carry
>    the condition that the GC mechanism will stay away from the space
>    I receive, then I'll be happy to change my position on garbage collection.

Well, the GC implementation that I'm most familiar with is the
Symbolics 3600.  This architecture organizes the address space into
logical entities called "areas".  Each area can be flagged as either
dynamic or static, the latter indicating that garbage should not be
collected there.  The GC still has to scan through static areas to see
whether they contain references to objects in dynamic areas, though;
otherwise the GC might create a dangling reference.

In the Symbolics system, the primary use of static areas is to prevent
pure code pages that are paged directly out of load files from being
copied into swap space.  They are also used for holding I/O buffers,
which are manually reused and therefore never become garbage.  The
features they are missing for your purposes are sophisticated
allocation and deallocation primitives; the only primitives the Lisp
Machine provides always allocate and deallocate space at the end of an
area, because the system depends on the GC to free up interior space.
But you could easily build a sophisticated allocator that manages its
own space inside a static area.

>    HOWEVER.  There are still things that need changing.  There still needs
>    to be implicit destruction of local environments via calls to DESTROY
>    routines.  Parameter passing is still ambiguous with respect to storage
>    utilization.  In general, I can live with GC being required IFF I can
>    also exert total control over when, how, and for how long every piece
>    of space is occupied, and I can determine exactly how much space is
>    being used implicitly and for how long.  

Lisp-like languages provide for this by providing macros that
encapsulate the allocation and deallocation of objects.  For example,
in Common Lisp one can write:

	(WITH-OPEN-FILE (variable file-name options...)
	  body...)

This opens the specified file, assigns the stream to the variable,
executes the body, and then closes the file.  And it guarantees that
the file will be closed no matter how the environment is exited.  This
is generally implemented using Lisp's UNWIND-PROTECT primitive, which
allows arbitrary code to be executed when an environment is being
exited.

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar