Re: Ada GC and a bunch of other stuff

>Preemptive multi-threading is hairier still depending on one's
>strategy. We chose to use semaphores to force all processes to
>synchronise before a GC. This may cause a longer latency in the
>process that triggered the GC but there is a gap in the process's view
>of synchronisation with the GC in which compute which doesn't interact
>with the GC or GC-owned pointers can be hidden (e.g. a vector product
>of reals). The analysis is tractable for many useful cases in Algol 68
>and PCF-Fortran, but I have yet to get this far.


Hans Boehm <boehm@parc.xerox.com> wrote:
> I don't understand this. Clearly you can't mean that you wait for all
> other threads to try to acquire a lock? Even if you handle threads
> blocked on IO correctly, this leaves you with a completely unbounded
> wait for compute-bound threads that don't synchronize, negating much
> of the advantage of preemptive multi-threading.


Actually, I do mean that I wait for all threads to acquire a
lock. Handling IO locks consistently is easy if done at the right
place (in essence, the process is suspended whilst in the kernel and
doesn't get involved in the GC wait). It is not really a *completely*
unbounded wait unless your compute thread is 'until the end of time'
and such a thread with no synchronisation would be useless drag
anyway.


I guess it all depends on what you want out of the system. We
designed primarily to hide compute behind communication ala Occam in
which case as long as useful work continues, the latency on GC is
irrelevant. Interactive programs care more for this, but tend to have
a continual stream of system calls to provide convenient GC points on
the interactive threads; a well designed interactive program will also
have consideration given to the load balancing and synchronisation
between threads. After all a short latency to get past a GC is no help
if you have to block immediately afterwards waiting for the results of
the compute thread.


There are other ways of doing precise GC with pre-emptive threads. We
considered sticking a breakpoint at the next safe GC point (usually a
call) but asides from the obvious problem of following all possible
branches, not all multithreading systems allow one process to get hold
of the process state of a pre-emptively suspended thread without
having 'debugger' privilege. Synchronisation via semaphores may be
brutal and risk the occasion pause, but it is also easy and good for
overall throughput.


Hans Boehm makes a good argument for the nice properties of a
conservative collector, so why do we bother with precise GCs? Apart
from some problems recovering self-referential structures, the main
problem with a conservative GC is that it can never return part of an
allocated block to free-store. Now to C programmers this is probably
an unthinkable operation, but in languages with arrays like Algol 68,
it is not uncommon to allocate a large array as a buffer, fill it
upwards with the desired elements and then deliver a slice of the
array with only those elements in. This may well be a 4K array of
characters to deliver a string of length 8. A precise GC will recover
the 4K-8 bytes while a conservative GC is doomed to hold onto the
entire 4K until the string is ditched.


It is good to have some real debate on Garbage Collection for
imperative languages after all these years of being asked 'What's
wrong with free?'.
----------------------------------------------------------------------
Dave Lloyd Email: Dave@occl-cam.demon.co.uk
Oxford and Cambridge Compilers Ltd Phone: (44) 1223 572074
55 Brampton Rd, Cambridge CB1 3HJ, UK
--

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