Re: Ada GC and a bunch of other stuff

Dave Lloyd <>
23 Feb 1996 00:22:59 -0500

          From comp.compilers

Related articles
[4 earlier articles]
Re: Ada GC and a bunch of other stuff (1996-02-13)
Re: Ada GC and a bunch of other stuff (1996-02-14)
Re: Ada GC and a bunch of other stuff (Dave Lloyd) (1996-02-16)
Re: Ada GC and a bunch of other stuff (1996-02-17)
Re: Ada GC and a bunch of other stuff (1996-02-21)
Re: Ada GC and a bunch of other stuff (1996-02-21)
Re: Ada GC and a bunch of other stuff (Dave Lloyd) (1996-02-23)
Re: Ada GC and a bunch of other stuff (1996-02-27)
| List of all articles for this month |

From: Dave Lloyd <>
Newsgroups: comp.compilers
Date: 23 Feb 1996 00:22:59 -0500
Organization: Compilers Central
References: 96-02-113 96-02-210
Keywords: GC, parallel

Henry Baker <> wrote:
> Why not treat the GC as an asynchronous thread -- that the compiler
> knows about -- that has access to (most of) the live data structures?

Our conceptual model has a system parallel action for the GC, but the
implementation 'overlays' this onto the same thread as the parallel
action invoking the GC (our model treats threads as execution
resources for parallel actions similarly to the Solaris
model). Ideally I would like the GC to run on the master thread which
usually has a deeper stack and on some systems is easier to
synchronise with, but reserving the master thread for GC might be an
even better idea.

> One must decide what the 'sequence/synchronization' points are,
> however. In most of my work, I force these points to be the points of
> allocation -- e.g., any CONS may do some GC work.

We additionally put synchronisation points in all thunks to 'alien'
code (i.e., not compiled by one of our compilers) as these may invoke
system I/O and be out for a while. We split the synchronisation so
that on entry to the alien code, our process is suspended allowing a
GC can occur at any time between the call and return. Clearly there
is some danger if the alien code is holding the sole copy of one of
our pointers or modifies one of our data structure while the GC is
traversing. Therefore our policy of what is allowed across the alien
interface is tighter than most, but it seems sufficient for most
practical use.

Incidentally what to Conservative GCs do about this? Surely they have
the same problem: a sole copy of a pointer may have been sent across
the Net to a machine in Finland (much poorly designed C uses the
integer equivalent of the internal pointer as the external handle to a
data structure). Similarly there may be unregistered threads of
execution that are capable of modifying the GC arena behind the
sweep. Many OS-supplied thread mechanisms do not allow all threads
within your process to be enumerated - some even allow threads to be
slept and woken from other processes.

> The GC process has access to GC-collectible stuff. Explicitly-managed
> stuff -- like 'linear/unique' types -- can be hidden from the GC, _so
> long as they can never reference GCable stuff_.

Some years ago I came across a paper (sorry, reference not at hand)
using type inference to put bounds on which objects might point into
the heap or might be pointed at from the heap. This can be
particularly useful when constructing a generational garbage collector
or (as in their interest) a distributed multi-processor GC, both of
which partition the dataset and record the pointers that cross the
boundary. Not an easy task it seems. Has there been any recent work
on this?

Dave Lloyd Email:
Oxford and Cambridge Compilers Ltd Phone: (44) 1223 572074
55 Brampton Rd, Cambridge CB1 3HJ, UK

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.