From: Nattfodd <[EMAIL PROTECTED]>
Date: Thu, 21 Jul 2005 03:22:04 +0200
Leopold Toetsch wrote:
>> ... Perhaps you should save your (metaphorical) breath, and I'll
>> wait for a more detailed design.
>
>
> I'm waiting too :-)
Hi,
I believe I found a good workaround for the cycle problems. It is a
little bit slower and worst case (which never occurs, happily) is
|IGP_set| passes, but should really be about 2 passes. But we need of
course not to run it each time. We can have 'classical' gmc most of the
time and once in a while, run NLDC (Night of the Living Dead Collection)
to get rid of evil IGP dead cycles.
;-}
Here is how NLDC works :
We do not care at all about generations. First, make a normal marking
pass, but without even considering the IGP set at all. Just see members
of the IGP set (origin and destination of the pointer) as normal objects.
Then, operation "Night of the Living Dead" begins (hence the name) : get
out of their graves objects that shouldn't have been buried first. Run
through the IGP set in reverse order of age of origin pointers. For each
(p0 -> p1) element in the IGP, do the following : if p0 is marked dead,
then do nothing and leave it dead. If it is marked alive, apply a
recursive procedure :
to_process := [p1];
while (to_process != []) {
p = pop (to_process);
if (p is dead) {
mark p alive;
forall (p -> q) in IGP {
push (q, to_process);
}
push (all childrens of p, to_process);
}
}
I'm still digesting it (and trying to bone up on GC algorithms at the
same time), but it does sound like it should work. I assume that
"forall (p -> q)" above really means "forall (q0 -> q where q0 == p)",
i.e. process all IGP entries from p.
However, except for the IGP loop, this is essentially the mark phase
of a two-pass algorithm. So if we know that p is live, and we're going
to mark the children of p as live, then we shouldn't also have to go
through the IGP entries for p at this point, should we?
FWIW, it might be better if you were to add only dead children to the
to_process queue:
to_process := [p1];
while (to_process != []) {
p = pop (to_process);
# assume p is dead
mark p alive;
forall child in children(p) {
if (child is dead) {
push (child, to_process);
}
}
}
At the very least, this would require a smaller to_process queue in the
typical case.
For the record, is it acceptable in Parrot to use page
write-protection to record whether oldspace objects have been modified
since the last full GC? This is what CMUCL does on most ports, but it
occurs to me that this might be a porting headache for Parrot.
. . .
I discussed it with friends and think it can even be proved to work
right (but that would take some time :/).
Does that sound reasonable to you ?
Regards,
Alexandre
Even an outline of a proof would help to identify hidden assumptions.
Especially valuable would be to prove bounds on storage and time costs.
But of course it's your time, so it's your call. (I'll holler if I find
any counterexamples, but I've been short on time lately.)
-- Bob Rogers
http://rgrjr.dyndns.org/
