Timely object destruction
Benjamin Goldberg
Piers Cawley wrote:
>
> The Perl 6 Summary for the week ending 20030601
> Another Monday, another Perl 6 Summary. Does this man never take a
> holiday? (Yes, but only to go to Perl conferences this year, how did
> that happen?)
>
> We start with the internals list as usual.
>
> More on timely destruction
> The discussion of how to get timely destruction with Parrot's Garbage
> Collection system continued. Last week Dan announced that, for languages
> that make commitments to call destructors as soon as a thing goes out of
> scope, there would be a set of helpful ops to allow languages to trigger
> conditional DOD (Dead Object Detection) runs at appropriate times.
> People weren't desperately keen on the performance hit that this entails
> (though the performance hit involved with reference counting is pretty
> substantial...) but we didn't manage to come up with a better solution
> to the issue.
>
> http://xrl.us/iu5
I'd like to reiterate (and clarify) my idea, of a hybrid scheme
combining refcounting and DoD.
All values needing timely destruction would inherit from a class
RefCounted. They should (in the normal scheme of things) be stored in
variables with an "is refcounted" trait (or a trait which inherits or
includes that trait, if that's possible).
Hopefully, only a *small* number of objects in a system need timely
destruction, and (for best performance) all variables which will hold
those objects will have the "is refcounted" trait set on them.
(If most or all objects needed timely destruction, then we wouldn't be
moving away from perl5's pure-refcount GC, would we?)
All operations on a variable or variables having the "is refcounted"
trait result in opcodes to call the refcount(inc|dec) method(s) of the
values in those variables.
Under normal circumstances, when a refcounted value's refcount goes
to zero, it self destructs^W^W cleans itself up.
This is quite perl5-esque, and of course slower than simply letting
the DoD-GC handle everything, BUT, in the absence of circular reference
loops, it does produce timely cleanup of those objects which need it,
which pure-DoD wouldn't, and DOESN'T result in numerous, and thus
expensive, requests for full DoD runs.
For all of the other schemes, full DoD runs would be run on every scope
exit, even if there's only one single variable in scope which needs
timely destruction.
Here's where the non-normal circumstances are described, and how they're
handled:
It's legal for a refcounted value to end up referenced by a non-
refcounted variable. This has to be so, since adding the "is refcounted"
trait everywhere would get cumbersome; also we may sometimes *need*, for
one reason or another, to store refcounted values in the same containers
which also hold non-refcounted values.
Thus, if a refcounted value gets stored in a non-refcounted variable,
then that value could quite easily still be reachable when it's refcount
goes to zero. Obviously, when this is the case, we need to avoid a
premature cleanup.
To avoid premature cleanup, any time that the contents of a
refcounted variable is assigned to a non-refcounted variable, an opcode
to set a "reachable by non-refcounted variable" flag on the value
precedes the assignment. If a refcounted values's refcount goes to
zero, and it has this flag set, it does NOT self-destruct[*].
A global counter keeps track of how many values have a refcount of zero
and have this flag set.
From here, we are in a similar situation as other proposals -- for the
timeliest possible destruction, then on every single scope exit, we
check if this global counter is nonzero, and if so, do a DoD run.
For potentially less timely destruction, we do this check whenever we
leave a scope where a refcounted variable was declared, but not when
we leave other scopes.
Which of these two is done is a choice of the language designer, but
might possibly be controlled by a pragma.
Note that in the absence of marking any variables with the "is refcounted"
trait, and with the use of the first option here (at every scope exit,
check the counter and maybe do DoD), this scheme behaves *identically*
with one of the other schemes proposed.
It would be *no* slower at run time, since the refcount(inc|dec) methods
are only called when doing operations dealing with variables with the
"is refcounted" trait, and if noone uses that trait, there's no extra
work. DoD would be a tiny bit slower with my scheme than the other,
due to the extra flag checking, but (assuming that *most* code with
objects needing timely destruction properly marks it's variables with
the necessary "is refcounted" trait) that's a small price to pay for
doing fewer DoD runs.
[*] How does this flag get cleared, you might ask?
Simplest would be to not clear it at all. This would be mostly harmless
in terms of when objects get destructed, but would probably result in
more DoD runs than we really need -- blech. [**]
A more "proper" solution would be to clear it during/after each DoD run.
During the course of a DoD run, when we look for what PMCs are reachable,
we keep track of what each thing was reachable *from*.
If a PMC was found to be reachable through a non-refcounted variable,
then we set a flag saying so. At the end of DoD, every reachable refcounted
value which has the first flag set, but this other flag not set, gets it's
first flag cleared.
[**] Please note: Never doing any checking or attempting to clear this
flag (and not adding any "is refcounted" traits to variables) would
result in my scheme having the EXACT same performance as the other
proposed scheme, and not be a single bit slower.
--
$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 "$@[$a%6
]\n";((6<=($a-=6))?$a+=$_[$a%6]-$a%6:($a=pop @b))&&redo;}
Leopold Toetsch
> I'd like to reiterate (and clarify) my idea, of a hybrid scheme
> combining refcounting and DoD.
I'll try to translate this to parrot speak. I hope that I fully
understand your scheme, but lets see.
> All values needing timely destruction would inherit from a class
> RefCounted.
All such variables?! ... have a special vtable and additionally a
refcount, where the ...
> All operations on a variable or variables having the "is refcounted"
> trait result in opcodes to call the refcount(inc|dec) method(s) of the
> values in those variables.
... get_val and the set_val part of the value access does inc|dec the
refcount:
if (--PTimer->refcount == 0)
if (PObj_is_referenced(PTimer))
interpreter->need_lazy_dod = 1
else
VTABLE_destroy( .. PTimer);
> Under normal circumstances, when a refcounted value's refcount goes
> to zero, it self destructs^W^W cleans itself up.
> To avoid premature cleanup, any time that the contents of a
> refcounted variable is assigned to a non-refcounted variable, an opcode
> to set a "reachable by non-refcounted variable" flag on the value
> precedes the assignment. If a refcounted values's refcount goes to
> zero, and it has this flag set, it does NOT self-destruct[*].
set_is_referenced PTimer := PObj_is_referenced_SET(PTimer)
set PAgggregate[key], PTimer
> A global counter keeps track of how many values have a refcount of zero
> and have this flag set.
IMHO no counter just a flag, but doesn't matter now.
> From here, we are in a similar situation as other proposals -- for the
> timeliest possible destruction, then on every single scope exit, we
> check if this global counter is nonzero, and if so, do a DoD run.
lazysweep # as currently
> During the course of a DoD run, when we look for what PMCs are reachable,
> we keep track of what each thing was reachable *from*.
> If a PMC was found to be reachable through a non-refcounted variable,
> then we set a flag saying so. At the end of DoD, every reachable refcounted
> value which has the first flag set, but this other flag not set, gets it's
> first flag cleared.
I think I don't understand the "first & other flag".
If a PTimer is e.g. inside an aggregate (i.e. reachable through
non-refcounted) the live_FLAG of the PTimer gets set and it will not get
destroyed. If during the DOD run the PTimer is not referenced it will
have the live_FLAG cleared and will be destroyed.
If there are any objects with a refcount live after a DOD run, we set
again the interpreter->need_lazy_dod flag.
leo
Benjamin Goldberg
> Benjamin Goldberg wrote:
>
>> I'd like to reiterate (and clarify) my idea, of a hybrid scheme
>> combining refcounting and DoD.
>
> I'll try to translate this to parrot speak. I hope that I fully
> understand your scheme, but lets see.
>> During the course of a DoD run, when we look for what PMCs are
>> reachable, we keep track of what each thing was reachable *from*.
>
>> If a PMC was found to be reachable through a non-refcounted variable,
>> then we set a flag saying so. At the end of DoD, every reachable
>> refcounted value which has the first flag set, but this other flag
>> not set, gets it's first flag cleared.
>
> I think I don't understand the "first & other flag".
>
> If a PTimer is e.g. inside an aggregate (i.e. reachable through
> non-refcounted) the live_FLAG of the PTimer gets set and it will not
> get destroyed. If during the DOD run the PTimer is not referenced it
> will have the live_FLAG cleared and will be destroyed.
>
> If there are any objects with a refcount live after a DOD run, we set
> again the interpreter->need_lazy_dod flag.
Suppose that we have the following situation:
{
my $x is refcounted = FileHandle.new("<", "foo.txt");
my $y = FileHandle.new("<", "bar.txt"); # sets need_lazy_dod
{
undef $y;
# at the following end of scope,
# the handle to bar.txt is closed by a DoD run.
}
# right now, is interpreter->need_lazy_dod set?
} # Does this end-of-scope result in a DoD run?
Following the DoD run from the first end-of-scope, there is one
refcounted object live. It has a refcount of 1. It is not referenced
through any variables lacking the 'is refcounted' property. Thus, it
will be cleaned up at the end of scope due to it's refcount going to
zero. There is no need for a DoD run at the second end-of-scope to
clean it up.
With my idea with flags on each value, we turn off
interpreter->need_lazy_dod after the first end-of-scope.
With your suggestion, the interpreter->need_lazy_dod would never get
unset until *all* refcounted objects get cleaned up.
Benjamin Goldberg
Miko O'Sullivan wrote:
>
> On Mon, 2 Jun 2003, Benjamin Goldberg wrote:
>
> > All values needing timely destruction would inherit from a class
> > RefCounted.
>
> I like this concept a lot, but maybe we can take it a little further
> and make it transparent to the programmer. Suppose that the internals
> only tracked objects that have a DESTROY method (or whatever it will
> be called in Perl6)? You get the same benefit without the additional
> brain-overhead of manually indicating that the class needs to be
> tracked.
That's a good idea, one which I left out because I was trying to
simplyfy/clarify my description.
Matt Fowles
I have been following the whole GC/timely destruction thing for a while
and have a few questions/observations.
Most of the ref counting systems provide for very simple ref counting
containers and, essentially, provide timely destruction for the simple
case where a variable is not placed into some more complicated
container. It seems to me that if we are worried about the simple cases
like
sub foo {
my $bar = open "bar.txt";
yada;
yada;
yada;
}
why not just have the compiler detect that $bar was not placed in a more
complicated container and generate the code to close $bar at end of scope.
This will provide timely destruction in the simple and common case. For
more complex cases timely destruction will not be assured.
Is there some glaring logical problem that I am missing here?
Matt
Benjamin Goldberg
After reading Leopold Toetsch's post, I'm going to simplify part of my
proposal slightly.
Benjamin Goldberg wrote:
[snip]
> To avoid premature cleanup, any time that the contents of a
> refcounted variable is assigned to a non-refcounted variable, an
> opcode to set a "reachable by non-refcounted variable" flag on the
> value precedes the assignment.
Actually, as Leopold suggested, we could merely set a global
interpreter->needs_lazy_dod flag to true.
[snip]
> [*] How does this flag get cleared, you might ask?
>
> Simplest would be to not clear it at all. This would be mostly
> harmless in terms of when objects get destructed, but would probably
> result in more DoD runs than we really need -- blech. [**]
>
> A more "proper" solution would be to clear it during/after each DoD
> run.
>
> During the course of a DoD run, when we look for what PMCs are
> reachable, we keep track of what each thing was reachable *from*.
This needs a bit of clarification, I think.
IIRC, DoD normally happens something vaguely like this:
for my $p (@all_pmcs) {
clear_is_live_flag($p);
}
our $traverse;
sub set_is_live_flag($p) {
if( !test_is_live_flag($p) and test_is_agregate($p) ) {
$traverse = [$p, $traverse];
}
really_set_is_live_flag($p);
}
set_is_live_flag($_) for @rootset;
while( $traverse ) {
((my $p), $traverse) = splice @$traverse;
$p->set_live_flag_on_contained_objects();
}
for my $p (@all_pmcs) {
next if test_is_live_flag($p);
free_pmc($p);
}
My proposal would change the set_is_live_flag to something like:
sub set_is_live_flag($p, $contained_in) {
if( test_uses_refcounting($p) and
not test_has_refcount_trait($contained_in) ) {
$needs_lazy_dod = 1;
}
if( !test_is_live_flag($p) and test_is_agregate($p) ) {
$traverse = [$p, $traverse];
}
really_set_is_live_flag($p);
}
Where $contained_in would be the variable (or agregate object) which the
object $p is contained in.
David Robins
> Most of the ref counting systems provide for very simple ref counting
> containers and, essentially, provide timely destruction for the simple
> case where a variable is not placed into some more complicated
> container. It seems to me that if we are worried about the simple cases
> like
<snip>
> why not just have the compiler detect that $bar was not placed in a more
> complicated container and generate the code to close $bar at end of scope.
>
> This will provide timely destruction in the simple and common case. For
> more complex cases timely destruction will not be assured.
>
> Is there some glaring logical problem that I am missing here?
That's somewhat like I suggested earlier, borrowing from the hybrid Python
GC (see http://arctrix.com/nas/python/gc/), but no-one replied.
The difference is that the solution proposed on the page uses refcounting as
the default and keep track of all "container objects" in a separate list.
Dave
Isa. 40:31
Benjamin Goldberg
>
> All~
>
> I have been following the whole GC/timely destruction thing for a
> while and have a few questions/observations.
>
> Most of the ref counting systems provide for very simple ref counting
> containers and, essentially, provide timely destruction for the simple
> case where a variable is not placed into some more complicated
> container. It seems to me that if we are worried about the simple
> cases like
>
> sub foo {
>
> my $bar = open "bar.txt";
> yada;
> yada;
> yada;
> }
>
> why not just have the compiler detect that $bar was not placed in a
> more complicated container and generate the code to close $bar at end
> of scope.
Hmm... this might be doable. Lemme think about it.
Firstly, the compiler needs to know that open() always returns an object
which needs timely cleanup. Easily doable through open()'s prototype,
since this of course describes traits/properties of the return value(s)
of the subroutine, amongst other things.
Second, the compiler needs to see that we never store into the $bar
variable anything which *doesn't* need timely destruction. Obviously,
we need to examine all assignments to $bar, and, check that $bar is
never passed into a subroutine through an "is rw" parameter. Again,
this is easily doable. (It *could* be passed to a sub through an "is
rw" parameter, if the compiler does all the same checks on that paramter
in that sub as it is doing in this scope).
Third, we need to make sure that all subroutines that we pass $bar to
*won't* store it in a complicated container. Note that all io
operations are subroutines... so you can't just say, "don't pass it to
subroutines," since then $bar is useless. How do we do this? Well,
again, it would have to be through the subroutine prototype -- the
parameter that we're passing $bar as would need to have some trait or
property attached to it saying that it won't get stored in a persistant
aggregate... I think this may be doable, and in fact the compiler could
*probably* detect this automatically, in sufficiently simple cases.
> This will provide timely destruction in the simple and common case.
Which is good.
> For more complex cases timely destruction will not be assured.
Which is not-so-good. We'd like timely destruction *always*
However, given that your suggestion can be implemented purely through
compile time behaviors, there's no reason we can't use what you've
suggested for the simple case, and some *other* solution for more
complex cases.
> Is there some glaring logical problem that I am missing here?
Not that I can see.
Matt Fowles
>>For more complex cases timely destruction will not be assured.
>
> Which is not-so-good. We'd like timely destruction *always*
>
> However, given that your suggestion can be implemented purely through
> compile time behaviors, there's no reason we can't use what you've
> suggested for the simple case, and some *other* solution for more
> complex cases.
I think that you will run into the halting problem here... Without ref
counting or running dod frequently I am not sure that you can guarantee
timely destruction, in complex cases...
Matt
Graham Barr
> IIRC, DoD normally happens something vaguely like this:
>
> for my $p (@all_pmcs) {
> clear_is_live_flag($p);
> }
> our $traverse;
> sub set_is_live_flag($p) {
> if( !test_is_live_flag($p) and test_is_agregate($p) ) {
> $traverse = [$p, $traverse];
> }
> really_set_is_live_flag($p);
> }
> set_is_live_flag($_) for @rootset;
> while( $traverse ) {
> ((my $p), $traverse) = splice @$traverse;
> $p->set_live_flag_on_contained_objects();
> }
> for my $p (@all_pmcs) {
> next if test_is_live_flag($p);
> free_pmc($p);
> }
This is something that has concerned me for a while. But does DoD
ensure any kind of ordering for the destruction ?
I ask becasue what happens if an object actually wants
to use its contents during its DESTROY ?
For example Net::POP3::DESTROY will send a reset command to its
server if the user did not call the quit method first. But how
could it do this if the socket PMC was already freed ?
Graham.
Leopold Toetsch
> Leopold Toetsch wrote:
>> Benjamin Goldberg wrote:
>>
>>> If a PMC was found to be reachable through a non-refcounted variable,
>>> then we set a flag saying so. At the end of DoD, every reachable
>>> refcounted value which has the first flag set, but this other flag
>>> not set, gets it's first flag cleared.
>>
>> I think I don't understand the "first & other flag".
Have it. Lets call this second flag: still_referenced_FLAG. Now above
sentence reads:
During the mark phase:
If a PMC is reachable through a non refcounted it gets
still_referenced_FLAG set.
And then:
If a PObj has the is_referenced_FLAG set but still_referenced_FLAG
cleared then reset the is_referenced_FLAG.
>> If there are any objects with a refcount live after a DOD run, we set
>> again the interpreter->need_lazy_dod flag.
> With your suggestion, the interpreter->need_lazy_dod would never get
> unset until *all* refcounted objects get cleaned up.
Yep, that was wrong. It should go:
At the beginning of the DOD run, we reset interpreter->need_lazy_dod.
At the end of the DOD run we do:
If we find refcounted objects with a refcount of zero and the
is_referenced_FLAG set, we set interpreter->need_lazy_dod.
leo
Leopold Toetsch
> I ask becasue what happens if an object actually wants
> to use its contents during its DESTROY ?
> For example Net::POP3::DESTROY will send a reset command to its
> server if the user did not call the quit method first. But how
> could it do this if the socket PMC was already freed ?
PMCs which have their own resources have the active_destroy_FLAG set
(this is done during init/clone). Now when such an object is found
unreferenced during a DOD run, the destroy() vtable method is called for
this object. The object should now cleanup itself (close sockets, free
system memory, ...). Thereafter the object is put onto the free list.
> Graham.
leo
Graham Barr
I may be missing something here. But within the resources of an object may
be other PMCs. As those PMCs will not be referenced from anywhere else
what is to stop the DoD run from freeing those before it freed the object ?
Graham.
Leopold Toetsch
If the PMC has explicit knowledge of an related PMC, the destroy can be
done in the correct order. But I think, the (higher level) cleanup will
be done at a higher level anyway, either in Parrot objects or in Perl6.
But even if we can't assure a correct order and one PMC has to call
another one (which might already be "freed", then it would be possible
to do the cleanup: We don't free PMCs, we just set a flag (on_free_list)
and put it on the free list. So when the relevant data of the PMC are
behind sizeof(void *) from the beginning of the PMC it could still be
used.
> Graham.
leo
Garrett Goebel
>
> I may be missing something here. But within the resources of
> an object may be other PMCs. As those PMCs will not be referenced
> from anywhere else what is to stop the DoD run from freeing those
> before it freed the object ?
Putting my head out on the chopping block twice in one day...
Correct me where I'm wrong but I was under the impression the DoD doesn't
free anything... It consists of marking those resources reachable from the
predetermined roots as active. All not marked active are deemed dead men
walking and will after due process get their own green mile. Graph, destroy,
deallocate... three separate phases.
Back to the point: once the object is no longer reachable, it and all
resources reachable only via it won't be marked as active and will
consequently be swept away and collected without any yet defined guarantees
of orderly destruction... Bad.
Couldn't parrot guarantee orderly destruction by recursively marking and
sweeping the rootless dead objects themselves? You might still end up with
circular references between the dead objects themselves... in which case
orderly destruction couldn't be guaranteed.
--
Garrett Goebel
IS Development Specialist
ScriptPro Direct: 913.403.5261
5828 Reeds Road Main: 913.384.1008
Mission, KS 66202 Fax: 913.384.2180
www.scriptpro.com garrett at scriptpro dot com
Dan Sugalski
>From: Graham Barr [mailto:gb...@pobox.com]
>>
>> I may be missing something here. But within the resources of
>> an object may be other PMCs. As those PMCs will not be referenced
>> from anywhere else what is to stop the DoD run from freeing those
>> before it freed the object ?
>
>Putting my head out on the chopping block twice in one day...
>
>Correct me where I'm wrong but I was under the impression the DoD doesn't
>free anything... It consists of marking those resources reachable from the
>predetermined roots as active. All not marked active are deemed dead men
>walking and will after due process get their own green mile. Graph, destroy,
>deallocate... three separate phases.
DOD combines finding the live objects and destroying the dead.
Garbage Collection handles the memory reaping.
I'd not be at all averse to having the DOD's destroy calling phase
build a tree and destroy from the top down, rather than just in arena
existence order, so long as it was an optional thing we could flag.
(I'm having destruction order issues at work at the moment, so I'm
rather amenable to this--take advantage of me while you can! :)
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Benjamin Goldberg
True enough.
But it shouldn't require solving the halting problem to recognize that
the current case is not simple. Thus, we can use Matt's idea for simple
situations, and detect when the situation is not so simple, and switch
to some other scheme.
There's no reason why the other scheme (whatever it is) can't be either
frequent DoD runs or my hybrid refcounting/dod scheme.
Leopold Toetsch
> There's no reason why the other scheme (whatever it is) can't be either
> frequent DoD runs or my hybrid refcounting/dod scheme.
Frequent DOD runs are not a problem for an average program (for some
definition of average). But when we come to ~1 million PMCs or so saving
some of them does already count a lot.
But doing the hybrid partial refcounting really depends on the var/value
vtable split, which we don't have yet and on Dan, who seems to be
strongly against it.
leo