Bob Rogers wrote:
From: Leopold Toetsch <[EMAIL PROTECTED]>
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
