Compilers - Copying GC and finalization

Author

Copying GC and finalization

Julian Stecklina

2005-07-26, 5:03 pm

Hello,

I am looking for ways to implement finalization of and weak pointers
to objects in a copying garbage collector. I am quite puzzled on how
to implement this without losing the nice property of copying garbage
collectors that there is nothing to do for objects that have become
garbage.

If anyone can point me to some information, it would be very helpful.

Regards,
--
Julian Stecklina

LISP has survived for 21 years because it is an approximate local
optimum in the space of programming languages. - John McCarthy (1980)

Chris Cheney

2005-07-28, 4:02 am

Julian Stecklina <der_julian@web.de> wrote in news:05-07-105@comp.compilers:
> I am looking for ways to implement finalization of and weak pointers
> to objects in a copying garbage collector. I am quite puzzled on how
> to implement this without losing the nice property of copying garbage
> collectors that there is nothing to do for objects that have become
> garbage.

Nothing to do except finalize them!

One (naive) way is to give all objects a hidden field ('hidden' meaning that
the garbage collector doesn't use it to find objects). I assume that the
type of the object is determinable when the object is accessed from the
hidden list.

1. When an object is created, chain it to a 'list of all current objects'
using this field.

2. When an object is found and copied by the garbage collector, unchain it
from the 'list of all current objects' and chain it to a 'temporary list'.

3. At the end of garbage collection, finalize all the objects remaining on
the 'list of all current objects' as these are the objects that have ceased
being current (= are garbage).

4. Empty the 'list of all current objects' and transfer the objects from the
'temporary list' to the 'list of all current objects'.

One will probably also wish to arrange that, if an object is finalized, it
is removed from the 'list of all current objects' (so that it is only ever
finalized once).

Whether the cost of this extra field is worthwhile clearly depends on the
particular application.

Now what about the weak pointers ...

HTH

Florian Liekweg

2005-07-28, 4:02 am

Julian Stecklina wrote:
> I am quite puzzled on how
> to implement this without losing the nice property of copying garbage
> collectors that there is nothing to do for objects that have become
> garbage.

Well, with finalisation, you have to do *something* to those objects,
by definition.

> If anyone can point me to some information, it would be very helpful.

I remember seeing a good article on that issue by Hans-J. Boehm of HP.
Start at http://www.hpl.hp.com/personal/Hans...alization.html,
and see the POPL2003 paper "Destructors, Finalizers, and Synchronization"
by the same author.

cheers,
Florian
--
========================================
===============================
Florian Liekweg | We resisted the temptation to develop what
IPD Universität Karlsruhe | the market needed at the time.
========================================
[ Rich Seifert on Ethernet ]===

Julian Stecklina

2005-08-05, 10:01 pm

Chris Cheney <cjc1@cam.ac.uk> writes:

> Julian Stecklina <der_julian@web.de> wrote in news:05-07-105@comp.compilers:
>
> Nothing to do except finalize them!
>
> One (naive) way is to give all objects a hidden field ('hidden' meaning that
> the garbage collector doesn't use it to find objects). I assume that the
> type of the object is determinable when the object is accessed from the
> hidden list.
>
> 1. When an object is created, chain it to a 'list of all current objects'
> using this field.
>
> 2. When an object is found and copied by the garbage collector, unchain it
> from the 'list of all current objects' and chain it to a 'temporary list'.

Without making this a doubly-linked list (and wasting another word)
this is an O(n) operation. It seems like it should be possible to
restrict this book-keeping to objects that actually have a finalizer
attached to them, thus (due to the small number of objects in need of
finalizing) the time spent modifying the list should be quite
small. Nevertheless it destroys the possibility of having a GC that
meets real-time properties.

> Now what about the weak pointers ...

In a stop-and-copy GC it should be possible to scan through all
objects containing weak-pointers after the actual collection and
replace every pointer to from-space by NIL or #f or something.

> HTH

Yes, it does. Thanks.

Regards,
--
Julian Stecklina

Eliot Miranda

2005-08-21, 2:56 am

Julian Stecklina wrote:

> Hello,
>
> I am looking for ways to implement finalization of and weak pointers
> to objects in a copying garbage collector. I am quite puzzled on how
> to implement this without losing the nice property of copying garbage
> collectors that there is nothing to do for objects that have become
> garbage.
>
> If anyone can point me to some information, it would be very helpful.
>
> Regards,
> --
> Julian Stecklina
>
> LISP has survived for 21 years because it is an approximate local
> optimum in the space of programming languages. - John McCarthy (1980)

Weak references are easy. During the scavenge any weak container
encountered isn't scavenge immediately. Instead it is added to a
linked list of weak containers (you can thread the list through the
corpse in past space, scavenging the container to survivor space
without scavenging its referents). Then once the scavenge is
complete, traverse the list of weak objects. Any referents that
remain in past space are dead and these fields can be nilled. You can
also arrange that any weak containers that have lost referents get
notified (e.g. add to a queue, have a system-level process extract the
containers form the queue and send them a notification).

Implementing finalization above this is possible but primitive. You
arrange that there is a proxy object for any finalizable object.
Finalizable objects are remembered in a weak container. Proxies are
held in a parallel strong array. When the weak container gets
notified it has lost referents it searches for nilled references,
fetches the corresponding proxy from the weak array, and finalizes the
proxy.

The major problem with this post-mortem finalization scheme is that it
is difficult to keep the proxy up to date.

A better scheme is to use guardians or ephemerons. I'm partial to
ephemerons myself. Ephemerons are marked specially and hold onto some
object. Like weak arrays, when encountered during a scavenge they are
not immediately scavenged unless their referent has already been
scavenged. Once the scavenge has completed, the ephemerons are
processed. Any whose referent has not been scavenged are the sole
referrers to their referent and so can be "triggered", identified as
having a reference to an object that would be collected except for
still being referenced by an ephemeron.

An ephemeron is triggered by placing it in a queue for subsequent
notification and then scavenging its referent (and its referents). In
the course of this more ephemerons may be encountered. The process
continues until all reachable objects have been scavenged and the
reachable ehemerons divided into triggered and untriggered ones.
Subsequently the triggered ephemerons are notified and can then
finalize their referents as a triggered ephemeron knows its referent
is only referenced by other triggered ephemerons.

To arrange for an object to be finalized simply create an ephemeron with
the finalizable object as its referent and put the ephemeron in some
container. On finalizing its referent an ephemeron also removes itself
from the container and is subsequently garbage-collected.

Scavenging can be substituted by or combined with a scan-mark (possibly
incremental). This is the scheme we use in VisualWorks, a leading
Smalltalk system (www.cincomsmalltalk.com)

Heer's a reference for the ephemeron paper:

Ephemerons: a new finalization mechanism
Barry Hayes
Conference on Object Oriented Programming Systems Languages and Applications
Proceedings of the 12th ACM SIGPLAN conference on Object-oriented
programming, systems, languages, and applications
pp 176 - 183, 1997

HTH
--
_______________,,,^..^,,,____________________________
Eliot Miranda Smalltalk - Scene not herd

Julian Stecklina

2005-08-24, 7:00 pm

Eliot Miranda <eliotm@pacbell.net> writes:
[lots of very useful information]

Thank you very much. This should get me going quite a bit. :-)

> Heer's a reference for the ephemeron paper:
>
> Ephemerons: a new finalization mechanism
> Barry Hayes
> Conference on Object Oriented Programming Systems Languages and Applications
> Proceedings of the 12th ACM SIGPLAN conference on Object-oriented
> programming, systems, languages, and applications
> pp 176 - 183, 1997

Thanks again.

Regards,
--
Julian Stecklina

(Of course SML does have its weaknesses, but by comparison, a
discussion of C++'s strengths and flaws always sounds like an
argument about whether one should face north or east when one
is sacrificing one's goat to the rain god.) -- Thant Tessman

Sponsored Links