[perl #38348] [PATCH] Accept return values via a Continuation
Bob Rogers
# Please include the string: [perl #38348]
# in the subject line of all future correspondence about this issue.
# <URL: https://rt.perl.org/rt3/Ticket/Display.html?id=38348 >
It seems that Continuation needs the same set_address magic as
Exception_Handler in order to return values. Which means that
Exception_Handler can just inherit the magic. Having this extra magic
doesn't seem to bother RetContinuation, though I'm not sure that I
understand why it doesn't, but at least RetContinuation is thoroughly
covered by the test suite, so I think it's probably OK.
Unless there's supposed to be another way to return values when
calling a Continuation?
-- Bob Rogers
http://rgrjr.dyndns.org/
Leopold Toetsch
> It seems that Continuation needs the same set_address magic as
> Exception_Handler in order to return values.
Yep. At least as long we don't have better support for creating limited
continuations that are able to return some results. There is of course
the 'standard' way to achieve this effect with a helper subroutine
'call-with-current-continuation', but there are probably some more HLL
semantics, which translate to the usage of the patch.
Thanks, applied - r11379.
leo
Bob Rogers
Date: Mon, 30 Jan 2006 05:48:42 -0800
Bob Rogers (via RT) wrote:
> It seems that Continuation needs the same set_address magic as
> Exception_Handler in order to return values.
Yep. At least as long we don't have better support for creating
limited continuations that are able to return some results.
I'm afraid I don't follow. What would you consider better?
There is of course the 'standard' way to achieve this effect with a
helper subroutine 'call-with-current-continuation', but there are
probably some more HLL semantics, which translate to the usage of the
patch.
Seems to me that call-with-current-continuation uses the identical
underlying mechanism as what I've been trying to do with Continuation,
at least as "implemented" by the t/op/lexicals.t "closure 4" test case.
It invokes its continuation in the same way as the new "set_args via
explicit continuation" test (invokecc_p in both cases) -- but has always
worked just because it has always used a RetContinuation instead of a
Continuation. I think that's the only real difference.
But, FWIW, I am coming around to the view that continuations
shouldn't ever be invoked like this. Plain function calling is likely
to confuse optimizers, since they won't understand that you don't ever
expect to return. I was about to propose a new op when I discovered
that tailcall works just fine for this purpose (see below). I hope to
document this, so that it can become the standard idiom.
We may want to go farther, though. Since optimizers could still lose
on code that doesn't conform to this convention, perhaps Parrot should
enforce the distinction by throwing an error if invokecc is used to call
something that can't return?
-- Bob
------------------------------------------------------------------------
Index: t/op/lexicals.t
===================================================================
--- t/op/lexicals.t (revision 11383)
+++ t/op/lexicals.t (working copy)
@@ -651,7 +651,7 @@
our_try = find_lex "try"
$P2 = find_lex "choices"
$P3 = our_try($P2)
- our_cc($P3)
+ .return our_cc($P3)
.end
.sub _fail :outer(main)
Leopold Toetsch
> From: "Leopold Toetsch via RT" <parrotbug...@parrotcode.org>
> Yep. At least as long we don't have better support for creating
> limited continuations that are able to return some results.
>
> I'm afraid I don't follow. What would you consider better?
Limiting the callframe range, where the continuation can go. Currently
creating a continuation is rather expensive, as all RetContinuations up
the call chain are converted into full continuations. This is necessary
because there is no further information about the usage of the
continuation. It could be passed to 'main' and then 'jump' back. Thus
all the intermediate frames have to be kept alive, because normal
function return goes through these frames.
> But, FWIW, I am coming around to the view that continuations
> shouldn't ever be invoked like this. Plain function calling is likely
> to confuse optimizers, since they won't understand that you don't ever
> expect to return. I was about to propose a new op when I discovered
> that tailcall works just fine for this purpose (see below).
I don't think that we can enforce this. Have a look at
t/library/streams.t. I don't think that a compiler has the knowledge
that it's compiling the invocation of a continuation instead of a plain
subroutine.
The tailcall syntax works, because it's just ignored by the continuation.
leo
Bob Rogers
Date: Tue, 31 Jan 2006 14:01:42 +0100
Bob Rogers wrote:
> From: "Leopold Toetsch via RT" <parrotbug...@parrotcode.org>
> Yep. At least as long we don't have better support for creating
> limited continuations that are able to return some results.
>
> I'm afraid I don't follow. What would you consider better?
Limiting the callframe range, where the continuation can go. Currently
creating a continuation is rather expensive, as all RetContinuations up
the call chain are converted into full continuations. This is necessary
because there is no further information about the usage of the
continuation. It could be passed to 'main' and then 'jump' back. Thus
all the intermediate frames have to be kept alive, because normal
function return goes through these frames.
Hmm. In this particular case, that doesn't actually make much
difference. In order to implement certain classes of nonlocal exits,
I'm creating a continuation and stuffing it into a lexical variable, and
I notice that C<newclosure> also promotes the RetContinuation to a
Continuation (though only for that frame).
Worse, the closed-over frame is leaked entirely. (Is this what the
"obviously leaks memory" comment in src/register.c is talking about, or
are there other cases of leakage?) But I think I have a handle on
what's causing this, and hope to propose a fix shortly.
> But, FWIW, I am coming around to the view that continuations
> shouldn't ever be invoked like this . . .
I don't think that we can enforce this. Have a look at
t/library/streams.t. I don't think that a compiler has the knowledge
that it's compiling the invocation of a continuation instead of a plain
subroutine.
Well, mine does, but that doesn't mean much. ;-} Point taken.
The tailcall syntax works, because it's just ignored by the continuation.
leo
Yep; and it also avoids making a useless return continuation, which is
nice.
-- Bob
Leopold Toetsch
> Worse, the closed-over frame is leaked entirely. (Is this what the
> "obviously leaks memory" comment in src/register.c is talking about, or
> are there other cases of leakage?) But I think I have a handle on
> what's causing this, and hope to propose a fix shortly.
Yep re comment. It's probably just a matter of setting the initial
ctx->ref_count to 1. A context is either de-allocated immediately, if
the sub returns via RetContinuation (re_use := 1 in src/register.c:500)
or when the (ret)continuation is destroyed. The latter case needs a
proper ref_count setting.
I'm pretty sure that frames left via exception are also leaking
currently, which would also be covered by above strategy.
leo
Nicholas Clark
> Bob Rogers wrote:
> > From: "Leopold Toetsch via RT" <parrotbug...@parrotcode.org>
>
> > Yep. At least as long we don't have better support for creating
> > limited continuations that are able to return some results.
> >
> >I'm afraid I don't follow. What would you consider better?
>
> Limiting the callframe range, where the continuation can go. Currently
> creating a continuation is rather expensive, as all RetContinuations up
> the call chain are converted into full continuations. This is necessary
> because there is no further information about the usage of the
> continuation. It could be passed to 'main' and then 'jump' back. Thus
> all the intermediate frames have to be kept alive, because normal
> function return goes through these frames.
Could this be done lazily? Presumably the ret continuations only need to be
converted to full continuations just before they're returned through, or
when any (other) continuation is invoked, for as long as the newly created
continuation exists.
I've no idea what the extra book-keeping overhead of this would be, and
whether the savings would be big enough to pay for that overhead.
Nicholas Clark
Leopold Toetsch
On Feb 3, 2006, at 15:49, Nicholas Clark wrote:
> On Tue, Jan 31, 2006 at 02:01:42PM +0100, Leopold Toetsch wrote:
>> Limiting the callframe range, where the continuation can go. Currently
>> creating a continuation is rather expensive, as all RetContinuations
>> up
>> the call chain are converted into full continuations. This is
>> necessary
>> because there is no further information about the usage of the
>> continuation. It could be passed to 'main' and then 'jump' back. Thus
>> all the intermediate frames have to be kept alive, because normal
>> function return goes through these frames.
>
> Could this be done lazily? Presumably the ret continuations only need
> to be
> converted to full continuations just before they're returned through,
The 'rather' expensive thing is basically:
while (cont)
cont->vtable = Parrot_base_vtables[enum_class_Continuation]
cont = cont->caller
i.e. placing a new vtable into the whole call chain. Setting some flag
or whatever wouldn't be simpler. The only problem with above is that
it's O(n) in call depth. Therefore the idea of creating 'limited
continuations' that are only allowed to 'jump' between defined places
in the call chain.
No - I don't think that this can be done lazily.
> Nicholas Clark
leo
Bob Rogers
Date: Fri, 03 Feb 2006 14:49:00 +0100
Bob Rogers wrote:
> Worse, the closed-over frame is leaked entirely. (Is this what the
> "obviously leaks memory" comment in src/register.c is talking about, or
> are there other cases of leakage?) But I think I have a handle on
> what's causing this, and hope to propose a fix shortly.
Yep re comment. It's probably just a matter of setting the initial
ctx->ref_count to 1. A context is either de-allocated immediately, if
the sub returns via RetContinuation (re_use := 1 in src/register.c:500)
or when the (ret)continuation is destroyed. The latter case needs a
proper ref_count setting.
Turns out that the leak is due to C<newclosure>, which causes the
frame's ref_count to jump immediately from 0 to 2. One increment is due
to the RetContinuation => Continuation promotion, and the other is added
by parrot_new_closure to reflect the ref from the closure. So the
essence of the fix is to create a Closure:destroy that calls
Parrot_free_context. But I think it would be better to go further; more
on that below.
I'm pretty sure that frames left via exception are also leaking
currently, which would also be covered by above strategy.
leo
I'll take a look at that, then.
From: Leopold Toetsch <l...@toetsch.at>
Date: Fri, 3 Feb 2006 17:20:22 +0100
On Feb 3, 2006, at 15:49, Nicholas Clark wrote:
> On Tue, Jan 31, 2006 at 02:01:42PM +0100, Leopold Toetsch wrote:
>> Limiting the callframe range, where the continuation can go. Currently
>> creating a continuation is rather expensive . . .
>
> Could this be done lazily? . . .
The 'rather' expensive thing is basically:
while (cont)
cont->vtable = Parrot_base_vtables[enum_class_Continuation]
cont = cont->caller
i.e. placing a new vtable into the whole call chain. Setting some flag
or whatever wouldn't be simpler. The only problem with above is that
it's O(n) in call depth. Therefore the idea of creating 'limited
continuations' that are only allowed to 'jump' between defined places
in the call chain.
No - I don't think that this can be done lazily.
> Nicholas Clark
leo
If I understand correctly, this O(n) step is necessary because the new
Continuation might be used to jump back down the call chain. In that
case, it would be necessary to return more than once through these
contexts, for which RetContinuation doesn't work, being a "use once and
recycle from_ctx immediately" version of Continuation. For this reason,
there are also a handful of other places in the code that must change
RetContinuation to Continuation because RetContinuation is too
aggressive about recycling contexts that might still be referenced.
So suppose we turn RetContinuation into a non-agressive "use once and
maybe recycle" continuation. This could be done by making
RetContinuation use and obey the Parrot_Context ref_count field (and
making sure everybody else does too). In other words, RetContinuation
would drop its context refs after being called, but would only free the
"from" context if doing so made the ref count drop to zero (i.e. the
normal Parrot_free_context thing). We should also provide an explicit
"invalidate" operation that causes the context refs to be dropped
immediately; this would be useful for all continuation classes.
Then, in order to implement a stack-unwinding control structure, one
can create a new RetContinuation in frame X, without triggering
continuation promotion on X's call chain. The new RetContinuation gets
passed down (or stored in a lexical), and is either used, or explicitly
invalidated before exiting the frame; either way, X's ref count drops
back down. Then, returning from frame X (still via its RetContinuation)
would recycle it normally [1].
There are also a number of side benefits:
1. In the normal call/return case for which RetContinuation was
designed, "from" contexts would still get recycled immediately.
2. Creating a Continuation would still provide the desired "return
many" behavior, albeit still with the O(n) call-chain promotion cost,
but the extra expense would be optional. Presumably, language
implementors will know which kind of continuation they need; if they
don't, then we can't help them anyway.
3. If a Closure or RetContinuation is created, the existing
RetContinuation chain would still work, decrementing the ref_count but
without necessarily freeing the context [2].
4. Most of the continuation promotions and the "re_use" parameter to
Parrot_free_context can be made to go away. (IMHO, this will be easier
to maintain, as Parrot hackers won't be expected to figure out whether a
context could be referenced from elsewhere.)
5. Some other context memory leaks should be easier to fix. For
instance, I notice a few cases of:
cont->vtable = Parrot_base_vtables[enum_class_Continuation];
caller->ref_count++;
These promotions are done without first checking whether the continution
is a RetContinuation; if not, the ref_count increment will leak the
context.
6. Last but not least, "use once" with explicit invalidation is a
useful thing to provide for supporting HLL semantics. Indeed, I
discovered the original "Accept return values via a Continuation"
problem when trying to implement non-local exits in my Common Lisp
compiler [3]. I would also like to be able enforce the rule that one
can only exit from a block once; a non-aggressive RetContinuation would
not only support this nicely, it would also recycle the block's frame
that much sooner.
Sound good? Unless I've missed something, this seems like a win
across the board . . .
-- Bob Rogers
http://rgrjr.dyndns.org/
[1] Unless of course there are closures that reference this frame. I
am reluctant to suggest that it be possible to invalidate a
closure. Maybe if there were a separate DownwardClosure class?
[2] I think this would also fix a bug. Closure:invoke promotes the
return continuation of the :outer context, but not any other
continuation. I assume this is just to keep the context alive so
that the outer_ctx chain can be traversed, but it means that
invalidate_retc_context on a deeper frame will stop too soon. If
RetContinuation was less aggressive, then Closure:invoke wouldn't
have to promote at all.
[3] Which ought to be ready for release soon (though I've said that
before).
Leopold Toetsch
[detailed plan]
> Sound good? Unless I've missed something, this seems like a win
> across the board . . .
Sounds very good.
> -- Bob Rogers
leo
Bob Rogers
Date: Sun, 5 Feb 2006 02:21:19 +0100
[detailed plan]
Sounds very good.
Unfortunately, I may not be the person to follow through on this. I've
spent the equivalent of a day on it, and am still very much stuck, so I
think I need to give up, at least for now. However, I would like to
submit the attached patch for review, which contains three good things
that I would like to salvage:
1. Closure still needs a destroy method, and having one is in fact
sufficient to reclaim contexts that would otherwise be lost.
2. In order to prove this (not to mention for debugging of
RetContinuation hackery), I added a fair amount of new CTX_LEAK_DEBUG
trace code, centralized it in interpreter.h, and put all of this output
under control of PARROT_CTX_DESTROY_DEBUG_FLAG so that it could be
turned on/off without recompiling.
3. While I was at it, I flushed most of the "#if CHUNKED_CTX_MEM"
code in src/register.c -- this code has serious bit-rot, and having two
implementations of Parrot_free_context et. al. tended to get in the way,
especially since M-. usually found the wrong one. (Though you could
argue that I didn't go far enough in flushing all of the CHUNKED_CTX_MEM
stuff . . .)
It is possible to show that Closure:destroy does something useful by
taking t/op/lexicals_28.pir (the 'closure 3' case), adding "debug 0x80"
as the first line in "main", and running it with and without the
src/pmc/closure.pmc hunk. I toyed with the idea of making a regression
test by adding some Perl postprocessing magic to make it less dependent
on build and version, thus:
rogers@rgrjr> ./parrot t/op/lexicals_28.pir 2>&1 | perl -pe 's/0x[\da-f]*/"0x#".($X{$&}||=++$n)."#"/ge'
[alloc ctx 0x#1#]
[alloc closure 0x#2#, outer_ctx 0x#1#, ref_count=2]
[invoke cont 0x#3#, to_ctx 0x#4#, from_ctx 0x#1# (refs 2)]
[alloc ctx 0x#5#]
[free ctx 0x#5# of sub 'anon']
8
[alloc ctx 0x#5#]
[alloc closure 0x#6#, outer_ctx 0x#5#, ref_count=2]
[invoke cont 0x#7#, to_ctx 0x#4#, from_ctx 0x#5# (refs 2)]
[alloc ctx 0x#8#]
[free ctx 0x#8# of sub 'anon']
23
[alloc ctx 0x#8#]
[free ctx 0x#8# of sub 'anon']
11
[alloc ctx 0x#8#]
[free ctx 0x#8# of sub 'anon']
27
[destroy closure 0x#6#, context 0x#5#]
[destroy cont 0x#7#, to_ctx 0x#4#, from_ctx 0x#5#]
[free ctx 0x#5# of sub 'foo']
[destroy closure 0x#2#, context 0x#1#]
[destroy cont 0x#3#, to_ctx 0x#4#, from_ctx 0x#1#]
[free ctx 0x#1# of sub 'foo']
[destroy closure 0x#9#, context (nil)]
rogers@rgrjr>
But even that seems too sensitive to internal changes, so I didn't take
it any further. At least this gives me a chance to provide a sample of
the output. (Thanks to Uri Guttman, whose tiny templater provided the
inspiration for the one-liner.)
In any case, I will wait a few days for comments before attempting to
commit any of this (as three separate changes). TIA,
Leopold Toetsch
On Feb 14, 2006, at 4:06, Bob Rogers wrote:
> 1. Closure still needs a destroy method, and having one is in fact
> sufficient to reclaim contexts that would otherwise be lost.
Ack.
> 2. In order to prove this (not to mention for debugging of
> RetContinuation hackery), I added a fair amount of new CTX_LEAK_DEBUG
> trace code, centralized it in interpreter.h, and put all of this output
> under control of PARROT_CTX_DESTROY_DEBUG_FLAG so that it could be
> turned on/off without recompiling.
Good. That simplifies further fixes.
> 3. While I was at it, I flushed most of the "#if CHUNKED_CTX_MEM"
> code in src/register.c -- this code has serious bit-rot, and having two
> implementations of Parrot_free_context et. al. tended to get in the
> way,
> especially since M-. usually found the wrong one. (Though you could
> argue that I didn't go far enough in flushing all of the
> CHUNKED_CTX_MEM
> stuff . . .)
Well, the original plan contained the usage of a linear chunked
context/register memory. But it's right that the code is fully
out-dated and non-functional and it's in the way, when jumping around
through tags.
Therefore it's really better to just drop that code and maybe
re-implement it cleanly again *after* all issues are sorted out.
leo
Bob Rogers
Date: Wed, 15 Feb 2006 10:29:28 +0100
On Feb 14, 2006, at 4:06, Bob Rogers wrote:
> 1. Closure still needs a destroy method, and having one is in fact
> sufficient to reclaim contexts that would otherwise be lost.
Ack.
Committed as r11616.
> 2. In order to prove this (not to mention for debugging of
> RetContinuation hackery), I added a fair amount of new CTX_LEAK_DEBUG
> trace code, centralized it in interpreter.h, and put all of this output
> under control of PARROT_CTX_DESTROY_DEBUG_FLAG so that it could be
> turned on/off without recompiling.
Good. That simplifies further fixes.
Great; committed as r11612.
> 3. While I was at it, I flushed most of the "#if CHUNKED_CTX_MEM"
> code in src/register.c -- this code has serious bit-rot, and having two
> implementations of Parrot_free_context et. al. tended to get in the
> way . . .
Well, the original plan contained the usage of a linear chunked
context/register memory. But it's right that the code is fully
out-dated and non-functional and it's in the way, when jumping around
through tags.
Therefore it's really better to just drop that code and maybe
re-implement it cleanly again *after* all issues are sorted out.
leo
I couldn't agree more. Committed as r11609. Should I also get rid of
the CHUNKED_CTX_MEM references in interpreter.h?
-- Bob
Leopold Toetsch
> I couldn't agree more. Committed as r11609. Should I also get rid of
> the CHUNKED_CTX_MEM references in interpreter.h?
Hmm, doesn't harm but is OTOH confusing. Maybe adding some comment would
be best for now.
>
> -- Bob
leo