On 7/25/05, Bob Rogers <[EMAIL PROTECTED]> wrote:
> 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.
Yes, that's what I meant.
I am sorry not to have told everyone before, but I discussed with leo
on IRC and the scheme he originally envisionned is actually very close
to NLDC and more simple : simply do the NLD pass at the same time than
the marking pass. But the underlying idea of collecting the IGP cycles
remains the same.
There is also the problem of no wanting to mark the whole memory but
only a given number of generations which is addresses this way.
> 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.
That's a good idea, thanks.
> 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.)
Well, I'll try to provide a sketch of it, but not now.
Actually, I had some laptop problems which should hopefully be fixed
soon. As time is beginning to run short (remember that the GC should
be functional by Sept. 1st), I'll rewrite GMC for dummies very soon
(tomorrow ?) and hope to begin coding just after that.
Regards,
Alexandre
