Re: (= GC ref.counting)?

[osiris@cs.utexas.edu (Rob Browning)]

>Funny, I did not see anything in StCLtL on this...
>
>(1) If two mutually referencing MCL objects are otherwise unreferenced, do they
>get GC'ed?

Absolutely.  If you can't reach it, it will eventually be GC'ed (assuming
there are no bugs in the GC).  You almost never have to think about memory
allocation again (unless you're using the toolbox).  It just does the
"right thing".

>"You got a coupla hours?")

That's about the right answer :>

Seriously, gc has been (and still is) a hot research topic.  Recent
advances (i.e. generational garbage collectors, try (egc T) in MCL) have
made gc much more efficient, and hence languages like Lisp much more
attractive.

There are a variety of approches to gc.  One is reference counting.  Every
pointer has a field that contains a count of how man items are pointing to
it.  When this is decremented to zero, the object is deleted.  The problem
with this approach is that self referential groups of objects like you
described will hang around forever.  For that reason this apporach is not
really used in modern systems, although a hybrid approach is somewhat
feasable where you use a more general purpose gc now and then to clean up
all the self referential groups.

Some more modern gc's use a mark and sweep approach.  That means that there
is a set of "root" pointers.  (For example, all the symbol tables).  At
garbage collection time, the program sweeps over the graph represented by
all the objects pointed to directly or indirectly by objects in the root
list.  Each of the objects reached is marked as reachable.  Everything else
is garbage and is "deleted".  How this deletion happens varies.  Some
algorithms can do it without moving anything, some have to copy all the
live objects.

Lastly, there are incremental garbage collectors.  A good "real-time"
incremental garbage collector would obviously be a plus in some systems.

There's a good paper by our own Professor Wilson on the subject.  I'll try
to find a reference to it.  There's also a free C++ garbage collector from
some site at xerox.com.  Check the newsgroups.

Hope this helps.

--Rob.