Ordered destruction and object graph traversal
Jeff Clites
destruction working. I actually have a mostly-working version of this
now, which will merit its own discussion, but there's a particular
aspect which I wanted to call out in light of Dan's recent post on
"Object freezing".
A key aspect of getting destruction-ordering right is doing an object
graph traversal to determine which objects are reachable from objects
which need to have their vtable->destroy() methods called--these
objects can't safely go away until these destroy's have been called.
This amounts to doing exactly what trace_children() does, except that
(1) you start with a different base set of objects to trace out from,
and (2) you need to set a different flag on the objects you reach.
For PMC's with custom vtable->mark() methods, this posed a
problem--that method sets the live flag, but now I needed to repeat
that logic almost exactly, but setting a different flag. Hmm--that was
telling me something, namely that we needed to generalize. In
particular, what was needed in both cases was simply a way to find out
what other objects are referenced by a particular object.
Since this is to be used in the middle of a DOD run, I thought it
crucial that this not require the allocation of additional memory
(which rules out an iterator object or method which returns something
like a flat array of referenced objects).
My solution was to define a new vtable method--I've called it visit(),
though the name's not the important part--to which you pass a callback
(plus an optional context argument). It's job is to invoke that
callback on each of it's referenced "children" (also passing the
context object with each invocation), and that's it. The PMC doesn't
know or care what the callback does--in a GC context the callback may
set a flag on what's passed in and stash it for later processing; in
another context it may be used inside of an iterator which vends out
objects one-by-one and guards against loops.
With this method, you end up not needing vtable->mark() -- all you need
to do is call vtable->visit() and pass it a callback which wraps
pobject_lives(). To do the destruction ordering which I need, you pass
it a different callback, which sets a different flag. And finally (the
reason I bring this up now), I expect that this method will serve as
the primitive which a vtable->traverse() implementation would leverage.
To be clear, this vtable->visit() isn't an object traversal
method--it's a tell-me-what-you-directly-point-to method, and often a
building block for traversal strategies or for iterator
implementations. I'm fairly convinced that a separate vtable->mark() is
unnecessary; at most, I'd say that the default implementation (which
calls visit() to do its work) would rarely need to be overridden.
Similarly for vtable->traverse(), although it's too soon to tell for
sure.
Again, I'm bringing this up now so that anyone diving into freeze/thaw
or traversal can leverage the work/thought I've put into this so far.
(I have some other thoughts on how to do traversals, but I'll save
those for another post.)
(My ordered-destruction implementation not quite ready for general
consumption yet--there are quite a few existing PMCs with custom mark
methods which need to be converted to custom visit methods. It's
straightforward to do but is taking a bit of time, and I want to finish
that before submitting this to make sure that I haven't overlooked
anything. All you really have to do to turn a mark() method into a
visit() method is change the prototype and change the call to
pobject_lives into a call to the callback.)
JEff
Gordon Henriksen
> My solution was to define a new vtable method--I've called it visit(),
> though the name's not the important part--to which you pass a callback
> (plus an optional context argument). It's job is to invoke that
> callback on each of it's referenced "children" (also passing the
> context object with each invocation), and that's it. The PMC doesn't
> know or care what the callback does--in a GC context the callback may
> set a flag on what's passed in and stash it for later processing; in
> another context it may be used inside of an iterator which vends out
> objects one-by-one and guards against loops.
Great! This is exactly the fundamental operation I'd been musing would
be the best building block to enable serialization and pretty-print
operations, and I'm sad to see that your post has been Warnocked. :(
This mechanism is excellent in that it enables both breadth-first and
depth-first traversals, and is neutral to whether a pointer is traversed
or not: The client (callback) can decide that based upon the live bit or
the ordered destruction bit or a seen table or the phase of the moon.
This also doesn't alone imply any resource consumption. And it doesn't
affect concurrency; threading is preserved. Great!
Serialization is a very natural client of this API, and at least some of
the arguments surrounding serialization should be lessened—because the
core technology is amenable to use by various possible algorithms, and
so deciding upon those algorithms early becomes less vital.
Serialization simply becomes an easier problem with this in place.
I would venture, though, that DoD may well need a separate and heavily
optimized implementation, purely for efficiency's sake.
—
Gordon Henriksen
mali...@mac.com
Dan Sugalski
> On Monday, October 20, 2003, at 11:40 , Jeff Clites wrote:
>
> > My solution was to define a new vtable method--I've called it visit(),
> > though the name's not the important part--to which you pass a callback
> > (plus an optional context argument). It's job is to invoke that
> > callback on each of it's referenced "children" (also passing the
> > context object with each invocation), and that's it. The PMC doesn't
> > know or care what the callback does--in a GC context the callback may
> > set a flag on what's passed in and stash it for later processing; in
> > another context it may be used inside of an iterator which vends out
> > objects one-by-one and guards against loops.
>
> Great! This is exactly the fundamental operation I'd been musing would
> be the best building block to enable serialization and pretty-print
> operations, and I'm sad to see that your post has been Warnocked. :(
Allow me to haul out this bucket of ice-water I keep around for just such
an eventuality. :)
There's a low limit to the complexity of any sort of traversal we can
provide. We *can't* go recursive in a traversal, if it crosses the
C->Parrot or Parrot->C boundary as part of the recursion, or stays
entirely in C. We can only count on a 20-40K stack *total*, and it doesn't
take too many calls into a recursive procedure to eat that up. That limits
the mechanisms we can use to traverse the graph of objects pretty badly.
The linked list mechanism the DOD system is using is one of the few that
isn't recursive.
There are other mechanisms that can be used for traversal that avoid
recursion, but they generally trade off pretty heavy memory usage for that
lack, which makes them unsuitable for general use.
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Jeff Clites
Who said anything about recursion?
JEff
Gordon Henriksen
> Allow me to haul out this bucket of ice-water I keep around
> for just such an eventuality. :)
>
> There's a low limit to the complexity of any sort of traversal we can
> provide. We *can't* go recursive in a traversal, if it crosses the
> C->Parrot or Parrot->C boundary as part of the recursion, or stays
> entirely in C. We can only count on a 20-40K stack *total*,
> and it doesn't
> take too many calls into a recursive procedure to eat that
> up. That limits
> the mechanisms we can use to traverse the graph of objects
> pretty badly.
> The linked list mechanism the DOD system is using is one of
> the few that
> isn't recursive.
>
> There are other mechanisms that can be used for traversal that avoid
> recursion, but they generally trade off pretty heavy memory
> usage for that
> lack, which makes them unsuitable for general use.
That's what's beautiful about this: ->visit isn't providing the
traversal algorithm at all. This vtable is agnostic to the traversal
algorithm. Breadth-first or depth-first; seen hash or mark bit or what
have you; zero-resource or resource-consuming: Whatever is best suited
to the requirements at hand. And it cleanly exposes that core
functionality to HLLs (which may have algorithmic requirements for
traversals that involve queues or stacks).
If parrot is embedded multi-threaded in an RDBMS or web server (which
strikes me as a more likely scenario than parrot embedded in a
resource-constrained embedded environment), then blocking the
interpreter for a serialization on one thread will negatively impact
response time, concurrency, and scalability. That might be considered
more damaging than additional resource consumption. ->visit neatly
enables BOTH resource-consuming, threadsafe serialization AND
zero-resource, blocking serialization.
--
Gordon Henriksen
IT Manager
ICLUBcentral Inc.
gor...@iclub.com