Bob Rogers wrote:
>     From: Leopold Toetsch <lt@[...].at>
>     Date: Sun, 17 Jul 2005 12:08:34 +0200
>  
>     > What happens when a store creates a cycle?  And how would this be
>     > detected?
>  
>     To keep the invariant we can't move the container nor the contained 
>     object, *if* both are aggregates. Therefore the pointer store will be 
>     recorded on the IGP list. Thus there is no need to detect cycles.
>  
>  But when are objects taken off the IGP list?  This is not contemplated
>  in [1], which explicitly mentions as a drawback that circular structures
>  cannot be recovered [2], and it is not (yet) addressed in the GMC design
>  [3].

Circular or not isn't really the problem. With generational GC you'll 
always have the chance of tenured garbage. E.g.

    gen n           |      gen j
    [ A ]           |      [ C ]
      ^                      |
      +----------------------+

We got a reverse pointer, which needs remembering on the IGP list of 
generation n. IGPn then becomes part of the root set of this generation 
n and the object A is marked and kept alive. So far so good.

Now due to some other pointer store the object C becomes dead. But as 
long as we don't scan up to generation j, we don't realize this and 
object A stays alive.

This is usually not a problem, just some waste of memory, except when 
the object A needs timely destruction. In such a case we would have to 
scan more generations, up to generation j in the above case.
As object C belongs to generation j, the IGP entry that marks A would 
become invalid, because the object C (and its refered contents) have to 
be anchored somwhere else to be alive.

    gen n           |       gen j
    [ A ] ->  [ B ] -|-----> [ C ]
      ^                      |
      +----------------------+

A circular data structure doesn't really change the picture, except, 
when again scanning up to generation j, and we find object C being 
alive, we'd have to restart scanning at object A, by following the 
backreference.
If non of A, B, or C is referenced from elsewhere, we would still delete 
the whole reference loop.

>  ...  Is one-pass mark-sweep really a suitable GC algorithm for Parrot?

I still think it's suitable yes. It's only in the above case that we 
can't immediately cleanup A, because of the invalidation of the IGP entry.

>  					-- Bob

leo