Juergen Boemmels wrote:
>
> Benjamin Goldberg <[EMAIL PROTECTED]> writes:
>
> > I was recently reading the following:
> >
> > http://www.parrotcode.org/docs/dev/infant.dev.html
> >
> > It's missing some things. One of which is the (currently used?) way
> > of preventing infant mortality: anchor right away, or else turn off
> > DoD until the new object isn't needed.
>
> This is Solution 3: Explicit root set augmentation
>
> Its not explained in so much details than the other solutions.
>
> > This document doesn't mention another technique, which was mentioned
> > recently:
> >
> > http://groups.google.com/groups?
> > selm=m2k7asg87i.fsf%40helium.physik.uni-kl.de
> >
> > , at the "use a linked list of frames" part.
>
> In principle this is a variant of the explicit root set
> augmentation. The linked list of frames is part of the root set. The
> big advantages of this list is that return and longjmp automatically
> drop the now unused objects, because each partial list is stored in
> the C-stack-frames.
>
> > Another similar idea (one which I thought of myself, so feel free to
> > shoot it down!) is to use a generational system, with the "current
> > generation" as a value on the C stack, passed as an argument after the
> > interpreter. That is, something like:
> >
> > foo(struct ParrotInterp *interpreter, int generation, ...)
> > {
> > PMC * temp = bar(interpreter, generation);
> > baz(interpreter, generation+1);
> > }
> >
> > Because inside baz(), generation is a higher value than it was when
> > temp was created, a DOD run inside of baz() won't kill foo.
>
> This is a solution similar to Solution 2 / Variant 4: Generation
> count.
>
> > During a DOD run, any PMC with a generation less than or equal to the
> > current generation is considered live.
>
> You can even use mark the current generation as free. If a function
> wants to keep data it uses Parrot_do_DOD(interp, generation + 1). If
> it does not have any data to keep it calls Parrot_do_DOD(interp,
> generation).
>
> > Any PMC with a generation
> > greater than the current generation gets it's generation set to 0.
>
> You mean is marked as free. An anchored object should be set to 0.
Actually, I meant generation set to MAX_INT, not 0.
Marking pmcs as free happens at the end of DOD. Marking pmcs as live or
dead happens earlier. I was thinking of something like:
foreach(pmc in all_pmcs) {
if( pmc->generation <= current_generation )
mark pmc as live
if( pmc is an aggregate )
add pmc to list of pmcs to be traced
/* don't alter it's generation */
else
mark pmc as dead
/* and if it becomes alive again, then */
/* on the next DOD, it shouldn't be considered */
/* alive due to being neonate/on the stack */
pmc->generation = MAX_INT;
}
foreach(pmc in root set) {
if( pmc is marked as live ) next;
mark pmc as live
if( pmc is an aggregate )
add pmc to list of pmcs to be traced
}
trace the pmcs in the list of pmcs to be traced
foreach(pmc in all_pmcs) {
if( pmc isn't live )
add pmc to the free list
}
> > Like the linked list scheme, this works through longjmps and recursive
> > run_cores, and it's much simpler for the user, too: just add one to
> > the generation to prevent all temporaries in scope from being freed.
> >
> > It similarly has the drawback of altering the signature of every
> > parrot function.
>
> If this will lead to exact and fast DOD we might bite the bullet.
Actually, I just thought of a seriously cool idea. If the C stack
always grows up, or always grows down, then we can use the address of
the local variable holding the interpreter, as the generation number.
Thus, we can avoid changing the prototype of all our functions. Sortof
like how one write an alloca() library function.
> > There's another drawback I can think of... consider:
> >
> > foo(struct ParrotInterp *interpreter, int generation, ...)
> > {
> > PMC * temp = bar(interpreter, generation);
> > baz(interpreter, generation+1);
> > qux(interpreter, generation+1);
> > }
> >
> > If baz creates a temporary object and returns, then qux performs a
> > DOD, baz's (dead) object won't get cleaned up.
>
> When asume the current generation as free (less than instead of less
> equal) this is not problem. Only if qux calls another function with an
> increased generation count without a prior call to Parrot_do_DOD the
> temporaries of baz will survive. But this can be solved by:
>
> foo(struct ParrotInterp *interpreter, int generation, ...)
> {
> PMC * temp = bar(interpreter, generation);
> baz(interpreter, generation+1);
> Parrot_do_DOD(interpreter, generation+1);
> /* free the temporaries baz */
> qux(interpreter, generation+1);
> }
>
> > This could be solved by keeping a stack of newly created objects, and
> > providing some sort of generational_dod_helper() function, which would
> > do something like:
> > while( neonates && neonates->top->generation > current_generation ) {
> > neonates->top->generation = 0;
Again, that should be set to MAX_INT, not 0.
> > neonates = neonates->next;
> > }
> > , and calling that in foo between baz and qux. (And maybe sometimes
> > at toplevel, between opcodes... at times when the generation count in
> > a "normal" generation count scheme (with a global counter) would be
> > incremented) You lost a bit of simplicity, by having to call this
> > function occcasionally, but it can save a bit of memory.
>
> In principle your generational_dod_helper is the sweep-function of the
> garbage-collector (or in parrot its called free_unused_objects).
Except that generational_dod_helper is much simpler and faster -- it
doesn't mark anything as alive or free, it only adjusts the generation
of those pmcs that were created in C functions which we have since
returned from.
(Hmm, that code should be setting neonates->top->generation to MAX_INT,
not zero. I think.)
> If you are sure that no objects have been anchored since the last mark
> no further mark is necessary (Parrot_do_DOD). But I'm not sure if you
> can guarantee that.
>
> I have the feeling that extending the signature of all
> Parrot-functions will remove the need of walking the C-Stack
> entirely. If this will be the linked list of frames or the generation
> count is more or less a matter of taste: The generation count forces
> some intermediate DOD-runs, whereas the linked list of stack
> frames makes the creation of temporaries a little bit more
> complicated.
The generation count doesn't *force* intermediate DOD-runs... or at
least, not a *full* DOD, anyway.
--
$a=24;split//,240513;s/\B/ => /for@@=qw(ac ab bc ba cb ca
);{push(@b,$a),($a-=6)^=1 for 2..$a/6x--$|;print "[EMAIL PROTECTED]
]\n";((6<=($a-=6))?$a+=$_[$a%6]-$a%6:($a=pop @b))&&redo;}
