Re: Ada GC and a bunch of other stuff

(I suggest we move this discussion to the newly formed gc mailing list.
I attempted to send a copy of this message there.)


Dave Lloyd <dave@occl-cam.demon.co.uk> writes:


>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, ...


My view is different. A big advantage of a time-sliced/preemptive
thread system is that it is possible to fork a compute-bound thread
such that it runs in the background without interfering with
interactive response. This is often reflected in the user interface,
which remains functional during compute-bound tasks. The crucial
advantage over a nonpreemptive system is that the compute bound task
does not have to yield periodically. It's hard to insert periodic
yield calls, because that will affect all code whose running time you
can't bound. That includes library routines, etc.


You have effectively replaced the yield calls by synchronization
calls. I will agree that that's likely to work most of the time. But
it doesn't strike me as particularly robust. A low priority
background thread performing an expensive nonallocating computation
(e.g. numerical calculation, or image transformation, or in-place
sort, or ...) can effectively block other threads that allocate
occasionally, e.g. a thread that's responsible for updating the
display, tracking the mouse, or whatever. Even if you don't care
about interactive response, it can seriously reduce processor
utilization in a multiprocessor if you have a mixture of allocating
and nonallocating threads.


>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.


I agree that this is a problem. It may be easier to single-step then
to predict the next safe gc point. I agree that most current thread
packages are deficient when it comes to such things. Even
conservative collectors share some of this problem.


>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's actually not clear that this is impossible for a hybrid gc that
scans a few stack frames (e.g. the tops of thread stacks)
conservatively. A variant of Bartlett's mostly conservative collector
should be able to handle this.


Hans-J. Boehm
(boehm@parc.xerox.com)
--

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