Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!ames!ncar!gatech!hubcap!billwolf%hazel.cs.clemson.edu
From: billwolf%hazel.cs.clemson.edu@hubcap.clemson.edu (William Thomas Wolfe, 2847 )
Newsgroups: comp.sw.components
Subject: Re: Real-time Garbage Collection
Message-ID: <6488@hubcap.clemson.edu>
Date: 18 Sep 89 11:21:36 GMT
References: <91482@ti-csl.csc.ti.com>
Sender: news@hubcap.clemson.edu
Reply-To: billwolf%hazel.cs.clemson.edu@hubcap.clemson.edu
Lines: 39

From gateley@m2.csc.ti.com (John Gateley):
> There exists at least one real-time garbage collection algorithm 
> (don't have the reference right now, email if you want it).

    I recently read of a linear-time algorithm (ignoring constant
    factors, of course) -- the only problem is that it required 
    sixteen times the amount of space actually needed by the program!!!

    The point is, any system which uses GC is going to be considerably
    less efficient (and constant factors are important here!) than a
    competing system in which the fact that an object is no longer
    needed is directly communicated to the storage management system.

    Now the advocates of GC frequently claim that space management is
    too heavy a burden to be placed on the application programmer, and
    this may well be true.  However, there is a much better way to deal
    with this problem.  All that is necessary is to encapsulate the
    details of storage management within abstract data types, such that
    the destruction algorithm is integrated into the block exit mechanism.

    By doing this, we place a level of abstraction between the application
    programmer and the details of storage management.  The use of pointers
    is confined to the ADT's implementation, and the application programmer
    is shielded from all the resulting complexities.  The interface also
    simplifies the work of the ADT's implementor; the destruction algorithm
    is usually quite straightforward.

    Worrying about GC is essentially barking up the wrong tree; what we
    need is better reuse mechanisms, so that we can also gain the added
    benefit of exploiting the implicitly supplied information regarding 
    the fact that a given variable is no longer needed which is naturally
    produced (with no special effort on the part of the application
    programmer) upon each and every block exit.  Thus, we can have our
    programming convenience WITHOUT eating our memory or CPU cycles, and
    thereby keep everyone happy (except perhaps those hackers who get a
    charge out of playing with pointers).


    Bill Wolfe, wtwolfe@hubcap.clemson.edu