Jeff Clites writes:
> On Jan 5, 2004, at 5:47 AM, Luke Palmer wrote:
>
> >After many months of lying dormant, I figured I'd get my act together
> >and adapt this patch to the few recent modifications. And this time,
> >I'm posting a benchmark!
> >
> >My results get about 5% slowdown in the eager case, and the usual
> >10,000% speedup in the lazy case.
>
> Sounds cool; do you have a quick high-level description of what it's
> all about? (I had seen that needs_early_DOD flag in the source, and
> didn't know what it was intended to do.)
>
> Thanks!
Okay, here I go, just before I get some sleep and then wake up to tie up
the rather insidious bugs in the patch.
We have a problem with several common constructs that Perl will likely
require of us. For instance, this one:
{
my $fh = open '> foo';
print $fh: "Hello!\n";
}
{
my $fh = open '< foo';
print <$fh>;
}
In Perl 5, this prints "Hello!" without the blink of an eye (well, if it
were valid Perl 5 syntax ;-). But now on Parrot with a opportunistic
DOD, this guarantee doesn't hold. If $fh isn't closed before it's
opened, the results here are undefined.
Performing a full sweep at every scope exit is not practical: there's
enough sub-call overhead as it is. So a new variant of C<sweep> was
added: C<sweep 0> would only sweep if there were no PMCs that had been
marked as neededing early (or impatient for) DOD.
I and several others quickly saw this as a makeshift solution. There
will commonly be at least one such object that will last the entire
lifetime of a program. So C<sweep 0>, in practice, was exactly
equivalent to C<sweep 1>.
Enter the scheme that this patch implements. It was batted around and
refined several times before I implemented it a few months ago. Here's
how it goes:
The common case is that none of the impatient objects go out of program
view, and moreover that the various paths to find them remain the same.
The algorithm takes heavy advantage of this, keeping state across
multiple DOD runs.
Each PMC has associated with it a "high priority" flag. First, only the
impatient objects have this flag set. But on each DOD run, it's
possible to efficiently tell all objects that hold a reference to this
high priority object. Those objects also get their high priority flag
set. And so on down the chain.
Then during the DOD main loop, if such a high priority object comes
along, it is prepended to the queue, temporarily switching the DOD to
depth first. This allows it to quickly navigate its way to the
impatient objects, and once they are all found, the lazy DOD is
terminated. And the more the lazy DOD is run, the faster it becomes.
When one of the impatient objects can't be found, the run is equivalent
to a C<sweep 1>, but that happens rarely. Also in this case, all high
priority flags are cleared, so that a wide-spreading circular data
structure doesn't end up making I<everything> high priority, thereby
nullifying the algorithm. This is one of those things I forgot to
implement ;-)
Hope this clarified things.
Luke
> JEff
>
