[Gc] libgc not collecting objects with cyclic references ?

skaller skaller at users.sourceforge.net
Mon Mar 19 05:30:12 PST 2007

On Mon, 2007-03-19 at 21:45 +1200, Bruce Hoult wrote:
> On 3/19/07, Christophe Meessen <meessen at cppm.in2p3.fr> wrote:
> > I am a bit surprized about the statement that cycle references are not
> > resolved by the gc. Does this apply only to blocks with clean-up
> > functions ? Is the destructor of a C++ function a clean-up function ?
> Well what are you going to do?
> If A has a pointer to B then it's presumably using B in some way, so
> you can't finalize B first because then things in A may crash.  But if
> B has a pointer to A then presumably it's using A in some way, so you
> can't finalize A first because then things in B might crash.  It's
> insoluable.  The GC hasn't got enough information to know what is
> safe.

Not sure what Boehm does, but in Ocaml finalisers can actually
make an object live again. So an object scheduled for finalisation
is reachable because the finaliser closure points to it, and
the finaliser closure is reachable because the list of scheduled
finalisers is also reachable.

After the finaliser is invoked on the object, the finaliser
closure is removed from the list, and the object may,
or may not, become unreachable, depending on what the finaliser
did. If the object becomes reachable it no longer has a finaliser
associated with it, however a new one can be attached dynamically
by the programmer.

In this system, the order and timing of finaliser execution
is unspecified. If finaliser for object A depends on B,
and B is also scheduled for finalisation, it is up to the
programmer to write the finalisers so that the order of
finalisation does not matter.

The Felix gc is different: it is designed to finalise C++ objects.
During sweep, finalisable objects are scheduled for finalisation.
Then there is a finalisation pass, in which all the finalisers
are executed. Then all the objects are freed. This algorithm,
unlike the Ocaml one, does not allow dynamic attachment
of finalisers: the finaliser is fixed statically at compile
time and is a wrapper around the C++ destructor.

The effect is to make RAII unworkable for heap objects.
RAII was never useful for heap objects anyhow: it relies
on stack protocol (FIFO).

Solving the 'order of finalisation' problem is not tractable
even if the data existed, since it appears to be a sorting
problem and is thus O(n log n).

The bottom line is: RAII doesn't work with garbage collection,
so don't use it.

Felix actually leverages C++ destructors to greatly reduce
the overhead on the gc, by allowing destructors to release
known non-circular data structures .. but we're talking
about memory resources here, and order of release of memory
is not significant.

You should also note most gc languages do not run the
collector at program termination, since the OS can recover
memory much more efficiently -- another reason not to use
RAII model.

John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

More information about the Gc mailing list