Re: on the topic of GC.

[Dirk Herrmann <dirk at ida dot ing dot tu-bs dot de>]

On 20 Sep 1999, Jim Blandy wrote:

> > Wouldn't it be possible to have a function scanning some region of memory
> > and looking for possible references that haven't been registered?  This
> > function would help debugging and could even be used to check heap areas:
> > Guile does require explicit registering for heap objects, so there is even
> > with the current approach a chance that you forget to register something.
> 
> I'm not sure what you're suggesting here.  It sounds like the idea is
> to use precise marking, but then check up on it with a conservative
> scanner.
> 
> I'm not sure what benefits this provides.
> 
> - If you believe that conservative marking is more accurate than
>   precise marking, then you should be using conservative scanning for
>   marking, not just for error checking.

I believe conservative marking is less accurate.  See below.

> - If you believe that conservative marking is less accurate than
>   precise marking, then this error checking would produce mostly
>   misleading warnings.

This depends.  Nobody seems to have exact numbers about the frequency of
false positives.  Still, a single false positive kann prevent
unpredictable amounts of memory from gc.  If you are right by saying that
we would get _mostly_ misleading warnings (and I intepret that you also
mean 'lots of them') then, on the contrary, we also have to assume that
lots of memory are kept unnecessarily and that this also increases
execution time, since all that memory will then have to be marked.

> - If you believe that conservative marking is as accurate as precise
>   marking, then you should use conservative marking, since it's less
>   trouble.

There are some points in favor of precise marking:

* As said above, conservative gc produces false positives.  False
positives can prevent unpredictable amounts of memory from gc.  This also
increases time for gc, since the more memory remains, the longer the
marking itself takes.

* scanning the stack takes time.  However, nobody can tell whether this
really means a decrease or increase compared to the time for
marking/unmarking. This should be investigated, also in the context of
multiple threads.

* conservative gc depends on the compiler to store pointers on the stack
in an unmodified way.  This might not be an issue with existing compilers,
but still is an uncleanlyness that I personally don't like.

* even with conservative gc you have to register references that are
allocated on the heap.  Thus, we need a good interface for registering
references anyway, and also a way to search for unregistered references.

* conservative gc is kind of ugly and has up to now been the reason for
guile's strange initialization procedure (main and real_main and so on).

The worst problem with precise marking, as has been claimed during this
discussion, is the fact, that you can easily make mistakes by forgetting
to register something.

To clarify my point:

My suggestion is, to use precise marking.  Assume that there is some
reference that was forgotten to be registered.  Then, this reference is on
the stack, because conservative marking would have found it.  During
debugging, we could have a function find_unregistered_references. This
would be called during gc after all other marking has taken place and
would report candidates of forgotten SCM values that are on the stack but
would be gc'd.

=> standard is precise marking.
=> debugging makes use of techniques from conservative marking.

The gc with debugging would therefore work like this:
1) mark all but the stack.
2) scan the stack. report unmarked SCMs pointed to by stack data.
3) sweep

Best regards,
Dirk Herrmann