An evil task for the interested
Dan Sugalski
looks like we need to get that done sooner rather than later. So, this is
a good chance for someone to burn those surplus SAN points and become one
with the great gibbering chaos at the center of the universe (no, wait,
that's not it) by digging into the DOD system.
Not a huge task, we just need to order PMCs before destroying them, to
make sure we don't call the destructor for a PMC before we destroy the
things that depend on it. A quick run through the PMC pools to build up a
dependency chain if there's more than one PMC that needs destruction
should do it.
Takers?
Dan
Dave Mitchell
I always thought that was a rather hard issue, due to circular
dependencies. It's certainly the case that Perl5 is very poor at global
destruction of objects.
--
SCO - a train crash in slow motion
Dan Sugalski
In the circular case you just pick a place and go from there -- there's no
good way to handle those. There are a lot of cases where there are
non-circular dependencies, though, so it seems worthwhile to take those in
order. Probably ought to be optional for all the sweeps except, perhaps,
the final one, though I expect perl, python, and ruby code will all enable
ordered destruction.
Dan
Thomas Fjellstrom
I've been interested in how to clean up circular dependencies... Just how easy
is it to find all cases? Is it possible? Like say a really really deep
case... Should you just not care at that point, and say the programmer
deserves what [s]he gets?
> Dan
--
Thomas Fjellstrom
tfjel...@strangesoft.net
http://strangesoft.net
Luke Palmer
Well, you don't really need to *find* the circular dependencies,
considering you can't really do anything with them once you do.
To destroy in a good order, you just have to topologically sort the
dependency graph, which isn't terribly hard. The way circular
dependencies are destroyed depends on the edge cases of the topological
sort algorithm you use. It would probably be best to 'prefer' objects
with explicit destructors, such that they appear earlier in the sort.
Luke
Dan Sugalski
It's pretty easy to find the cases--if you pick an object with an active
destroy method, start tracing the tree, and hit that object during the
trace then you've got a circular structure. There's no reliable way of
properly cleaning these up, since any scheme you can think of (and people
have thought up a lot of 'em) can run leave you with a situation you can't
reasonably resolve.
The only good thing to do is clean up all the non-circular structures and
see if there's anything left (since sometimes destructors on other objects
can end up resolving the issue) and, if there is, picking an object at
random to start the destruction with. And for parrot, it *should* be
random, if we're not otherwise going to set a scheme in place. (Complete
with calls to rand() and everything)
Dan
Jeff Clites
> We've got ordered destruction on the big list 'o things to do, and it
> looks like we need to get that done sooner rather than later.
...
> Not a huge task, we just need to order PMCs before destroying them, to
> make sure we don't call the destructor for a PMC before we destroy the
> things that depend on it. A quick run through the PMC pools to build
> up a
> dependency chain if there's more than one PMC that needs destruction
> should do it.
I have a partial implementation of this now. (Need to clean it up
before submitting it.) There are a couple of thorny points that may
need some discussion, but I'll start with the sharpest thorn: For PMCs
with a custom mark method, the idea is that it's opaque exactly what
other object they have references to, right? (That is, the PMC knows
how to mark them alive, but doesn't reveal what they are, right?)
I'm asking because my approach is to collect the list of PMCs which
need their destroys called, and trace through this set (like a DOD run)
to see which ones are referred to by others on the list (and more
importantly, which ones are not), destroy() those that are unreferenced
and take them off the list (or do this to an arbitrary one if none are
unreferenced), and repeat until done. This works out fine, but I don't
think I can use the PObj_live_FLAG for this marking or it will mess up
the subsequent work in free_unused_pobjects(), but there isn't a way to
ask a mark() method to set another flag. This leaves me stuck with
regard to PMCs with custom mark methods (but it's working for the other
PMC flavors of referring).
So, I wanted to see if I'm missing something obvious, or if we need for
mark() to take a parameter to indicate the flag to set.
(For a second I was about to decide that I could re-use PObj_live_FLAG,
since by definition it will be unset for objects we are going to
destroy(), thinking that I just need to be sure to clear the flag again
before getting to the rest of free_unused_pobjects(), but since there's
no unmark() method I'm again stuck, since my tracing could
inadvertently appear to bring things back to life. Though I suppose a
subsequent DOD run would get them....)
Thoughts?
JEff
Leopold Toetsch
> On Oct 9, 2003, at 8:43 AM, Dan Sugalski wrote:
>...
>> Not a huge task, we just need to order PMCs before destroying them,
> ..., but there isn't a way to
> ask a mark() method to set another flag. This leaves me stuck with
> regard to PMCs with custom mark methods (but it's working for the other
> PMC flavors of referring).
This sounds exactly as it needs the general PMC traverse/iterator too,
discussed in the thread "[RfC] vtable->dump".
,--[ /me ]---------------------------------------------------------------
| So I'm speaking of a framework, which calls a vtable->traverse() method
| that calls vtable methods (freeze, clone, dump, or whatever) on SELF
| and then puts aggregate items (if any) on a TODO list. This
| functionality is IMHO that of an iterator. This does address stack
| blowing and self-referential structures.
`------------------------------------------------------------------------
Using mark() for everything doesn't work as soon as Luke Palmers scheme
Subject: "PATCH] Re: Timely Destruction: An efficient, complete solution"
is merged (BTW where are the benchmarks).
> So, I wanted to see if I'm missing something obvious, or if we need for
> mark() to take a parameter to indicate the flag to set.
An extra parameter (and check in pobject_lives) would slow down DOD, so
rather not.
> Thoughts?
Yep: vtable->traverse()
> JEff
leo
Juergen Boemmels
> On Oct 9, 2003, at 8:43 AM, Dan Sugalski wrote:
>
> > We've got ordered destruction on the big list 'o things to do, and it
> > looks like we need to get that done sooner rather than later.
> ...
> > Not a huge task, we just need to order PMCs before destroying them, to
> > make sure we don't call the destructor for a PMC before we destroy the
> > things that depend on it. A quick run through the PMC pools to build
> > up a
>
> > dependency chain if there's more than one PMC that needs destruction
> > should do it.
>
> I have a partial implementation of this now. (Need to clean it up
> before submitting it.) There are a couple of thorny points that may
> need some discussion, but I'll start with the sharpest thorn: For PMCs
> with a custom mark method, the idea is that it's opaque exactly what
> other object they have references to, right? (That is, the PMC knows
> how to mark them alive, but doesn't reveal what they are, right?)
Right. There are ways to find out which PMCs are actually marked but
that is digging in the deep internals of the DOD-System. After a call
to vtable->mark the list interpreter->mark_ptr/pmc->next_for contains
the objects which are marked. With some hacks that create a new list
before the next call to vtable->mark it might be possible to get a
list of children. But I don't suggest to go this way.
> I'm asking because my approach is to collect the list of PMCs which
> need their destroys called, and trace through this set (like a DOD
> run) to see which ones are referred to by others on the list (and more
> importantly, which ones are not), destroy() those that are
> unreferenced and take them off the list (or do this to an arbitrary
> one if none are unreferenced), and repeat until done.
You might need to iterate quite often with this approach. The worst
case scenario is destroying a linked list. You iterate the list, find
out which is the head, destroy it and search the list again for the
new head.
But you can, while generating the list of PMCs which need destruction
enforce that this list is ordered. If you know nothing about the
object already append it to the front of the list, if you know that it
must destroyed after an object which is already on list enter it after
the list. If the tree is walked depth first you get a list which is in
the right order for destruction. The destruction is then just
iterating a list and calling the functions.
But I did not figure out a way to do the depth-first tree-walking
without massive recursion.
> This works out
> fine, but I don't think I can use the PObj_live_FLAG for this marking
> or it will mess up the subsequent work in free_unused_pobjects(), but
> there isn't a way to ask a mark() method to set another flag. This
> leaves me stuck with regard to PMCs with custom mark methods (but it's
> working for the other PMC flavors of referring).
>
>
> So, I wanted to see if I'm missing something obvious, or if we need
> for mark() to take a parameter to indicate the flag to set.
We need a general tree-walk vtable. This is needed for dump, freeze
and more things. Leo suggested something like that in the thread
[RfC] vtable->dump. One way to implement this is a generalization of
the mark-function.
I don't like the idea of generalizing the mark function:
mark is called very often and should be as fast as
possible. I think we should have one mark function which is very tight
coupled to the gc-system and one general iterator function.
> (For a second I was about to decide that I could re-use
> PObj_live_FLAG, since by definition it will be unset for objects we
> are going to destroy(), thinking that I just need to be sure to clear
> the flag again before getting to the rest of free_unused_pobjects(),
> but since there's no unmark() method I'm again stuck, since my tracing
> could inadvertently appear to bring things back to life. Though I
> suppose a subsequent DOD run would get them....)
Resurrection of objects is opening a can of worms. Do we really want
to go into this. It might be a nice feature, but it is worse the
trouble.
bye
boe
--
Juergen Boemmels boem...@physik.uni-kl.de
Fachbereich Physik Tel: ++49-(0)631-205-2817
Universitaet Kaiserslautern Fax: ++49-(0)631-205-3906
PGP Key fingerprint = 9F 56 54 3D 45 C1 32 6F 23 F6 C7 2F 85 93 DD 47