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);
}
}
And then proceed with compaction as usual. This ensures us that dead
cycles have been destroyed and that every alive object has been marked so.
Here is how it works. Consider a dead cycle :
[A] --> [B] --> [C]
^ |
+--------------------+
In the first run, the C->A link does not exist. Thus, as A, B and C are
not referenced from elsewhere, they are all marked dead. And in NLD
pass, C being dead, no object of the cycle comes back to life and it can
safely go to hell.
If now, for instance B is referenced from the vast outer world, A is
dead but B and C as marked alive after the first pass. Thus C is marked
alive and we apply the recursive function that just rescues A.
Some cases are just a little trickier :
For instance :
|
v
[A] --> [B] --> [C]
^ |
| +---+
| v
| [D] --> [E] --> [F]
| |
+----------------------------------------+
We have C->D and F->A in the IGP set, and B is referenced from the outer
world. Thus, the whole cycle is alive.
After the first pass, only B and C are marked alive. In NLD pass, we
first check F and find it dead, thus do nothing. Next is C, which is
alive. And, thanks to the "forall (p->q) in IGP...", we add D to the
living, and then the whole cycle.
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
