[gclist] Language behaviour wrt GC (Was: Name that hypothesis)

[Hans Boehm]

On Dec 5,  2:39am, Geert Bosch wrote:

> The effect of these properties is that in most situations where C uses
> dynamic memory allocations it is not needed in Ada. When using pointers
> to stack-allocated data it is not possible to create dangling references.
> All pointers in the stack pointing to the stack are backward pointers.
>
> So the only reason to use dynamic memory allocation is in cases where
> having backward pointers is not enough. I'm very curious what the effects
> of this would be for the garbage hypotheses posted lately.
>
My guess is that the significance of this difference is normally overstated.
Almost all of the allocation in C code that I've written would also have been
necessary in Ada.  I have occasionally written code to dynamically allocate
variable sized arrays, solely because C didn't allow variable size automatic
arrays.  On the other hand, if the block was frequently executed, I generally
use an automatic array for the common case and dynamically allocate only in
case of overflow.  (And I would explicitly deallocate the overflow arrays, if
the environment allows.  Thus it probably shouldn't enter the statistics
anyway.  Allocating and dropping large arrays in a GC environment is expensive,
since it greatly increases GC frequency for a given heap size.  That's the one
place in which malloc/free is a large performance win.)

The restrictions to prevent dangling references probably require some dynamic
allocation in Ada that's not needed in C.  (Consider for example the C strtok
function, admittedly an abomination.  It usually retains a pointer to a buffer
that is passed in in a global variable.  The buffer can still often be stack
allocated in C.  But you need at least whole program flow analysis to determine
that this is safe.)  I suspect this effect is also minor.


> It's a little bit sad that a modern language that actually *needs* a
> garbage collector if you don't want to use Unchecked_Deallocation, has
> no good implementations that have one. As a small survey has indicated
> the main property of such a collector would be safety, which is why not m
> any people are interested in a conservative collector.

The survey indicated much confusion.  I'm not sure about anything else.
I never did get a convincing explanation as to why conservative collection
(implemented correctly, with minimal compiler support) is less safe than manual
deallocation.  Most people involved in that discussion also seemed to believe
that explicit deallocation gives you reasonable guaranteed space bounds, and
that Sun's Java implementation uses a nonconservative collector, both of which
are easily demonstrated to be false.  As Henry suggested, the first
misconception probably came from experience with relatively small embedded
systems in which there were very few distinct object sizes, if there was any
dynamic allocation.

>
> There is a lot of interest in a precise (preferably compacting)
> garbage collector on the other hand. What I'm interested in is what
> GC techniques would be efficient in this particular case. Also note
> that Ada is a tasking language. Most literature on GC seems to deal
> with C at one side or very "artificial" languages at the other side.
>
> I have not found very much information or statistics on strongly typed,
> statically checked tasking languages like Ada and Modula-3.

You might look at Barry Hayes' Stanford thesis which contains some measurements
of Cedar environments.  I would expect the statistics to be similar to
Modula-3. (Some of the code was probably written by the same people.)

Hans



-- 
Hans-Juergen Boehm
boehm@mti.sgi.com