NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/lang/cplus/13003

Text File | 1992-08-27 | 5.8 KB | 127 lines

Path: sparky!uunet!synaptx!synaptics.com!daveg
From: [e-mail] (Dave Gillespie)
Newsgroups: comp.lang.c++
Subject: Re: Garbage Collection for C++
Message-ID: <[e-mail]>
Date: 28 Aug 92 07:43:31 GMT
References: <[e-mail]> <[e-mail]>
Sender: [e-mail]
Organization: Synaptics, Inc., San Jose, CA
Lines: 114
In-reply-to: [e-mail]'s message of 27 Aug 92 18:33:04 GMT

In article <[e-mail]> [e-mail] (Hendrik Boom) writes:
>> I did; as far as I can tell, the GC has to call destructors, and it's

> One of my nightmares in a Lisp garbage collector is the destructor
> from Hell that retrieves otherwise moribund objects and makes them
> accessible again.  Do we have to do another garbage collection to see if
> objects are really free?  And if they are, do we have to call
> the destructor from hell again? and again? and again?and again?

Your description is more dramatic than clear :-), but it brings to
mind an example where garbage collection could be troublesome in C++.
Is this what you were thinking of?

   class D *orphanedThing;
   class C {
     D *thing;
     ~C() { orphanedThing = thing; }
   };

Now suppose there is a C object which has become garbage, and there
is a D object that is unreferenced except through that C object's
"thing" member.  The GC is justified in noting that the C object is
garbage and destroying it, but it can't go on to conclude that the
D object is garbage since the destructor is going to leave behind
another reference to it.

Lisp objects generally don't have "destructors", at least not ones
with visible side effects.  In Lisp, if the only references to an
object are from other garbage objects, that object is also garbage.
If Lisp couldn't rely on this, a 1000-element garbage linked list
could only be freed one link at a time, requiring 1000 successive
GC's to free the whole list!  (Thus resulting in the fire and
brimstone to which Hendrik alludes.)


This all reminds me of the idea of "finalizations" in Lisp, a
simple-sounding and very useful concept that turns out to be a
horrible quagmire of complications when it is implemented.

Basically, a finalization is a property that can be attached to
any allocated object, which is a function to be called to clean up
when that object is garbage-collected.  In other words, it's a
destructor.

As well as the problem Hendrik describes, there is the more basic
problem of when to call the finalization:  Most Lisps shut down
completely during GC and are not able to call user-defined
functions until the GC is completely finished; if you have a
compacting garbage collector, how do you compact across an
object if you haven't called its finalization yet?

The only Lisp system I've used which implements finalizations is
Allegro Common Lisp.  They solve these problems by freeing objects
with finalizations in two stages.  When the GC first determines
that an object is garbage, and the object has a finalization, the GC
doesn't actually destroy it; instead, it adds the object to a list
of things to be finalized, and then *removes the finalization from
the object*.  When GC finishes, it finalizes these objects and
removes them from the list before going on with the main program.
Since the objects' finalizations have been removed, the *next* GC
will finally destroy them.  If for some reason the finalization
code saves away a reference to a part of the object, or even to the
object itself, the next GC will see the new reference and do the
right thing.

Even if the next GC occurs during the finalization step from the
previous GC, you're safe because the yet-to-be-finalized objects
are not garbage yet---they're referenced by the finalization list
itself!

Hendrik's issue is solved by making garbage-ness transitive only
for things without destructors.  If an object has a destructor,
it is not deleted by the first GC so the things it points to are
not yet garbage.


If you made a linked list of N things each of which had destructors,
it would still take N GC's to delete the list, but the idea is that
destructors (finalizations) would only be used for the kinds of
things that are not used in big lists.  For example, a finalization
might close a file that was held open by the object; rarely would
you have a linked list of 1000 objects each holding open a file!
(And where the links are in the objects themselves; a conventional
Lisp list of pointers to finalizable objects would have no problem,
because the cons cells themselves have no finalizations and so can
be collected all at once.)

A C++ garbage collector could make itself destructor-safe using
the same strategy.  When the GC finds an object is garbage and the
object has a destructor, it simply calls the destructor and then
somehow sets a flag showing that the object has effectively been
converted to raw bits.  The next GC will finally collect the
object's memory.  I doubt such a flag would be difficult to add;
allocated objects would need a place to record enough RTTI to find
the proper destructor anyway.

But wait---don't most classes have destructors?  Yes, at present,
but I claim that GC would render most destructors obsolete.
Destructors tend to be used for cleaning up auxiliary memory, a
task which would be automated by GC.  Destructors in a C++ with
GC would be just as rare as finalizations are in Lisp.

A compiler that could prove a given destructor had no (pointer)
side effects could optimize by instructing the GC to call the
destructor and delete the object immediately.  For example, a
destructor which only calls close(), or only adjusts some profiling
statistics, could do this.  But is only an optimization; a simple
compiler could treat all destructors the same.

                                -- Dave
--
Dave Gillespie
  [e-mail], uunet!synaptx!daveg
  or: [e-mail]