[gclist] Fast-allocating non-copying GC's

[Robert A Duff]

> After some time of just reading this list, I think it's time to fire
> my share of stupid questions. Currently I'm working on implementing
> a GC-friendly allocator for Ada-95 (a language in the ALGOL family).

This is good to hear.  Good luck!

I'm not a GC expert, but I'm an Ada expert; feel free to e-mail me if
you want to discuss Ada-language-related issues with me.  Or if you want
me to review your design.

>     Since changing the compiler (GNAT) in a way that makes 
>     precise GC possible is way too hard and time-consuming,
>     I have chosen for a conservative GC.

Makes sense.  By the way, if you *did* modify the GNAT compiler, I
suspect the changes might be applicable to gnu C++ (etc?), since they
share the same back end, and probably most of the changes (and the
hardest ones) are back end related.

> (2) Precise versus Conservative GC
> 
>     Since changing the compiler (GNAT) in a way that makes 
>     precise GC possible is way too hard and time-consuming,
>     I have chosen for a conservative GC.

Makes sense.  Also, conservatism would seem to make the multi-tasking
issues of Ada easier to deal with.

>          (?) In Ada only a very small subset of the objects
>              can contain pointers that point inside objects.

This is not really true.  Any object of a general access type ("access
all") can point any aliased object.  In addition to heap objects, any of
these can be declared aliased: stack objects, record components, array
components.  So you can have a pointer that lives in a component of a
heap-allocated record, and (sometimes!) points to a component of a
stack-allocated array.  And you can't tell this at compile time (compile
time of the pointer, I mean).

You *can* tell at compile time which things are aliased, though.

>              The compiler knows about these cases. Would
>              it be worth the effort to have the compiler 
>              pass this info to the allocator at allocation 
>              time?

It might be helpful for the compiler to pass over information about
which objects and subcomponents are aliased.  But as you said, you don't
want to modify GNAT -- it's too hard.

> (4) Because of (2.1) and (2.2) I've chosen to have a 
>     table in which I can lookup any possible pointer 
>     and get its size and some other attributes which
>     I'll describe in the next section.

Can't you play some games with the address space to make this more
efficient?  E.g. put all the storage pools in one region of the virtual
address space, so any potential pointer outside that range is not really
a pointer.

Well, I have more to say, but I think I'll make it private e-mail, to
avoid boring the GC folks with Ada-specific mumbo-jumbo.

- Bob