Continuations, stacks, and whatnots
Dan Sugalski
We've definitely got performance issues with continuations. This is
Not Good, since we're using them for control flow. Leo's hacked in a
performance fix, but it's got its own issues. I think it's time for
some thought, and a more unified solution.
Making a continuation conceptually has three steps. One must:
1) Copy the current environment contents to the continuation
2) Note the bytecode address at which the continuation should run
3) Mark the stacks as COW
Step 3 is universally required *however* we can skip it *if* we
mandate that return continuations can't be used for anything other
than returning. I'm not sure that's a good idea, but we can do it. We
can also do it transparently if it turns out that it's a bad idea.
Allocating continuations quickly is important enough that I think
they warrant a separate arena with specifically sized PMCs. (with
each allocatable item being sizeof(PMC)+sizeof(environment) so
there's no need for memory allocation at continuation allocation
time) Creating a continuation, if step 3 above is skipped, then has
the cost of a single PMC allocation from a free list and a memcpy of
the environment chunk of the interpreter structure.
Part of the problem we're seeing with continuations has to do with
the stacks. We've got a chunked stack frame system, with multiple
frames fitting into a single stack chunk. This made sense when I
first did it, but that was years and a number of significant design
decisions ago. At this point I think it's a sub-optimal decision. So
it's time to fix it.
What I'd like to do is switch from the current chunked system (which
made sense when it was first done, but things have changed a lot
since then) to a single-frame system, and make 'em PMCs to boot. That
is, rather than having the stack allocated in chunks that can hold
multiple pushes, we make each push to the stack live in its own
independent structure that's linked to the previous top-of-stack
element. If we make these PMCs as well then we get it all nicely
DOD-able and GC-able without any (well, much) special code. The "this
is a buffer of PObj pointers" flag will work nicely for this too, as
it'll mean we won't even need to bother with a separate scanning code
path for this stuff.
This should all be transparent, as it's API-protected, but it'll mean
some internal rework, so now's the time to dig into the discussion on
it.
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Leopold Toetsch
> Since this has gotten to be an issue...
> Making a continuation conceptually has three steps. One must:
> 1) Copy the current environment contents to the continuation
> 2) Note the bytecode address at which the continuation should run
> 3) Mark the stacks as COW
> Step 3 is universally required *however* we can skip it *if* we
> mandate that return continuations can't be used for anything other
> than returning. I'm not sure that's a good idea, but we can do it. We
> can also do it transparently if it turns out that it's a bad idea.
That is a RetContinuation. It has only pointers of the context inside.
> Allocating continuations quickly is important enough that I think
> they warrant a separate arena with specifically sized PMCs. (with
> each allocatable item being sizeof(PMC)+sizeof(environment)
What about other sub PMCs: Sub, Closure, Coroutine, Exception_Handler?
> there's no need for memory allocation at continuation allocation
> time) Creating a continuation, if step 3 above is skipped, then has
> the cost of a single PMC allocation from a free list and a memcpy of
> the environment chunk of the interpreter structure.
Should be faster by some yes.
[ single items stack ]
> ... and make 'em PMCs to boot. That
> is, rather than having the stack allocated in chunks that can hold
> multiple pushes, we make each push to the stack live in its own
> independent structure that's linked to the previous top-of-stack
> element. If we make these PMCs as well then we get it all nicely
> DOD-able and GC-able without any (well, much) special code. The "this
> is a buffer of PObj pointers" flag will work nicely for this too, as
> it'll mean we won't even need to bother with a separate scanning code
> path for this stuff.
Making it a PMC just for marking is suboptimal.
Special handling of PObj_is_buffer_of_pobjs can be inserted in
mark_special().
The current Stack_Chunk_t has a C<limit> member to protect against
to many pushes and C<name> for displaying error messages.
leo
Dan Sugalski
>Dan Sugalski <d...@sidhe.org> wrote:
>> Since this has gotten to be an issue...
>
>> Making a continuation conceptually has three steps. One must:
>
>> 1) Copy the current environment contents to the continuation
>> 2) Note the bytecode address at which the continuation should run
>> 3) Mark the stacks as COW
>
>> Step 3 is universally required *however* we can skip it *if* we
>> mandate that return continuations can't be used for anything other
>> than returning. I'm not sure that's a good idea, but we can do it. We
>> can also do it transparently if it turns out that it's a bad idea.
>
>That is a RetContinuation. It has only pointers of the context inside.
Yes, I know that. I'm not 100% sure it's safe. Or, rather, I'm sure
its safe if it's only used as a return continuation, as any
full-fledged continuation will mark everything COW so it'll be fine.
I'm just not sure we're going to be able to guarantee that a return
continuation won't be used in other ways.
I suppose we could have an upgrade op that upgraded this to a full
continuation, which'd just involve a COW stack walk.
D'oh! (I should edit this all out but, well...) If we go with a one
frame stack chunk then we don't have to bother with COW-ing
*anything* with the stack. Which makes the differentiation between a
return continuation and a regular continuation irrelevant, as they'd
be identical.
> > Allocating continuations quickly is important enough that I think
>> they warrant a separate arena with specifically sized PMCs. (with
>> each allocatable item being sizeof(PMC)+sizeof(environment)
>
>What about other sub PMCs: Sub, Closure, Coroutine, Exception_Handler?
Dunno if they're allocated often enough to warrant any extra work.
Maybe exception handlers.
>[ single items stack ]
>
>> ... and make 'em PMCs to boot. That
>> is, rather than having the stack allocated in chunks that can hold
>> multiple pushes, we make each push to the stack live in its own
>> independent structure that's linked to the previous top-of-stack
>> element. If we make these PMCs as well then we get it all nicely
>> DOD-able and GC-able without any (well, much) special code. The "this
>> is a buffer of PObj pointers" flag will work nicely for this too, as
>> it'll mean we won't even need to bother with a separate scanning code
>> path for this stuff.
>
>Making it a PMC just for marking is suboptimal.
Maybe, but I'm not sure of that. It's not the reason for going for a
one frame stack chunk, but if we're going to we might as well just
make it a PMC, or a PObj, or whatever. Reduce the number of special
cases for the moment.
>Special handling of PObj_is_buffer_of_pobjs can be inserted in
>mark_special().
>
>The current Stack_Chunk_t has a C<limit> member to protect against
>to many pushes and C<name> for displaying error messages.
Yes, I know. I want to skip the multiple frames per stack chunk thing
entirely. One element per chunk and that's it.
Leopold Toetsch
> ... If we go with a one
> frame stack chunk then we don't have to bother with COW-ing
> *anything* with the stack.
BTW: which stacks: Register frames of course. What about Pad, User, and
Control?
leo
Leopold Toetsch
> At 7:00 PM +0100 3/22/04, Leopold Toetsch wrote:
> D'oh! (I should edit this all out but, well...) If we go with a one
> frame stack chunk then we don't have to bother with COW-ing
> *anything* with the stack. Which makes the differentiation between a
> return continuation and a regular continuation irrelevant, as they'd
> be identical.
Ok. BTW:
$ parrot tools/dev/bench_op.imc --times=1000000 'new P10, .PerlInt'
Time for 1M ins: 0.314813
$ parrot tools/dev/bench_op.imc --times=1000000 'new P10, .RetContinuation'
Time for 1M ins: 1.679647
$ parrot tools/dev/bench_op.imc --times=1000000 'new P10, .Continuation'
Time for 1M ins: 4.876401
(-O3 on Athlon 800)
I estimate a special Fat Continuation PMC at around 1 sec per Meg.
So avoiding the creation of (Ret)?Continuations at all is still a very
valuable goal IMHO.
>>What about other sub PMCs: Sub, Closure, Coroutine, Exception_Handler?
> Dunno if they're allocated often enough to warrant any extra work.
> Maybe exception handlers.
Exception handlers are derived from Continuations. All these share some
code - not much though.
leo
Dan Sugalski
>Dan Sugalski <d...@sidhe.org> wrote:
>> At 7:00 PM +0100 3/22/04, Leopold Toetsch wrote:
>
>> D'oh! (I should edit this all out but, well...) If we go with a one
>> frame stack chunk then we don't have to bother with COW-ing
>> *anything* with the stack. Which makes the differentiation between a
>> return continuation and a regular continuation irrelevant, as they'd
>> be identical.
>
>Ok. BTW:
>
>$ parrot tools/dev/bench_op.imc --times=1000000 'new P10, .PerlInt'
>Time for 1M ins: 0.314813
>
>$ parrot tools/dev/bench_op.imc --times=1000000 'new P10, .RetContinuation'
>Time for 1M ins: 1.679647
Wow. Not a bad difference at all. (Yes, I know, factor of five, but
there's a good chunk of memcopying going on there too :)
>I estimate a special Fat Continuation PMC at around 1 sec per Meg.
>
>So avoiding the creation of (Ret)?Continuations at all is still a very
>valuable goal IMHO.
Sure, it's a great goal. I'm just not sure it's a feasable one. The
other constraints on the system make it dodgy to go reuse these
things. Lets first see where a separate continuation pool takes us
and we can go from there.
> >>What about other sub PMCs: Sub, Closure, Coroutine, Exception_Handler?
>
>> Dunno if they're allocated often enough to warrant any extra work.
>> Maybe exception handlers.
>
>Exception handlers are derived from Continuations. All these share some
>code - not much though.
Let's worry about them later. For now, we'll concentrate on
continuations, and look into the rest after that.
Piers Cawley
I hope he means "All of 'em".
And what control stack? The continuation chain is the control stack, surely?
Dan Sugalski
Nope. There's the exception handlers, at the very least. Possibly
some lexical pad stuff. (Though of that I'm less sure)
Matt Fowles
I am not sure that I understand why we deal with exception handlers at
all. Why not just make exception handlers a second continuation passed
to all functions. Then you call continuation 1 for successful returns
and continuation 2 for exceptions. This will not introduce overhead to
the common case, as common case is not installing exception handlers so
you can just pass along the one you were handed, while it will simplify
the code by removing the need for the control stack and special
exceptions pmcs.
Matt
Piers Cawley
> At 12:59 AM +0000 3/23/04, Piers Cawley wrote:
>>Leopold Toetsch <l...@toetsch.at> writes:
>>
>>> Dan Sugalski <d...@sidhe.org> wrote:
>>>
>>>> ... If we go with a one
>>>> frame stack chunk then we don't have to bother with COW-ing
>>>> *anything* with the stack.
>>>
>>> BTW: which stacks: Register frames of course. What about Pad, User, and
>>> Control?
>>
>>I hope he means "All of 'em".
>>
>>And what control stack? The continuation chain is the control stack, surely?
>
> Nope. There's the exception handlers, at the very least.
Just add a field to the continuation structure "NextExceptionHandler"
which points to the continuation of the next exception handler in the
chain. To throw an exception you invoke that exception. If that
exception handler needs to rethrow the exception, its P1 will contain
the appropriate continuation.
> Possibly some lexical pad stuff. (Though of that I'm less sure)
I've always wondered why lexical pads have their own stack. I'd hang it
off the Sub object and, when the sub's invoked, shove the current pad
into a control register, which then gets closed over by any
continuations that get made. Invoking a continuation restores the pad
register and away you go.
Leopold Toetsch
> Dan Sugalski <d...@sidhe.org> writes:
>>>And what control stack? The continuation chain is the control stack, surely?
>>
>> Nope. There's the exception handlers, at the very least.
> Just add a field to the continuation structure "NextExceptionHandler"
> which points to the continuation of the next exception handler in the
> chain.
What about C code that either installs exception handlers or throws
exceptions?
>> Possibly some lexical pad stuff. (Though of that I'm less sure)
> I've always wondered why lexical pads have their own stack. I'd hang it
> off the Sub object and, when the sub's invoked, shove the current pad
> into a control register, which then gets closed over by any
> continuations that get made. Invoking a continuation restores the pad
> register and away you go.
Interesting idea. Well, the control register is a pointer in the context
structure. We should be careful not to use up too many PMC registers.
But the current lexical pad structures are suboptimal (searching is
O(n)). OTOH we need some kind of linked lists of pads, which matches the
single item stacks approach.
leo
Dan Sugalski
>Piers Cawley <pdca...@bofh.org.uk> wrote:
>> Dan Sugalski <d...@sidhe.org> writes:
>
>>>>And what control stack? The continuation chain is the control
>>>>stack, surely?
>>>
>>> Nope. There's the exception handlers, at the very least.
>
>> Just add a field to the continuation structure "NextExceptionHandler"
>> which points to the continuation of the next exception handler in the
>> chain.
>
>What about C code that either installs exception handlers or throws
>exceptions?
Or multiple nested exception handlers, or serial exception handlers
in a block... And then there's the fun with exception handlers and
coroutines.
It's a stack, like it or not.
> >> Possibly some lexical pad stuff. (Though of that I'm less sure)
>
>> I've always wondered why lexical pads have their own stack. I'd hang it
>> off the Sub object and, when the sub's invoked, shove the current pad
>> into a control register, which then gets closed over by any
>> continuations that get made. Invoking a continuation restores the pad
>> register and away you go.
>
>Interesting idea. Well, the control register is a pointer in the context
>structure. We should be careful not to use up too many PMC registers.
>
>But the current lexical pad structures are suboptimal (searching is
>O(n)). OTOH we need some kind of linked lists of pads, which matches the
>single item stacks approach.
Just because the current version's implementation is broken doesn't
make the concept wrong. :)
Matt Fowles
This got warnocked when last I sent it, so I will try again as I think
it is a reasonable idea.
I am not sure that I understand why we deal with exception handlers in
the current manner. Why not just make exception handlers a second
Leopold Toetsch
> All~
> This got warnocked
Only indirectly ...
> ... Why not just make exception handlers a second
> continuation passed to all functions.
... because it is answered in a f'up to a similar proposal by our
summarizer:
,--[ leo ]-----------------------------------------------------------
| What about C code that either installs exception handlers or throws
| exceptions?
`--------------------------------------------------------------------
,--[ dan ]----------------------------------------------------------------
| Or multiple nested exception handlers, or serial exception handlers in a
| block... And then there's the fun with exception handlers and
| coroutines.
`-------------------------------------------------------------------------
leo
Matt Fowles
> Matt Fowles <Matt_...@softhome.net> wrote:
>>... Why not just make exception handlers a second
>>continuation passed to all functions.
>
> ... because it is answered in a f'up to a similar proposal by our
> summarizer:
>
> ,--[ leo ]-----------------------------------------------------------
> | What about C code that either installs exception handlers or throws
> | exceptions?
> `--------------------------------------------------------------------
Before calling C code parrot could install an exception handler, if that
handler is used parrot could call the appropriate continuation.
Similarly, after C code that installs an exception handler, parrot could
create a new continuation that would jump into the installed handler
when called.
> ,--[ dan ]----------------------------------------------------------------
> | Or multiple nested exception handlers, or serial exception handlers in a
> | block... And then there's the fun with exception handlers and
> | coroutines.
> `-------------------------------------------------------------------------
Nested exception handlers would be handled exactly the same way nested
function calls are handled by continuations. The inner exception
continuation would store the outer one in a register which it new about
and then call it. I am not entirely sure what is meant by serial
exception handlers. If it just means
try {
...
} catch(FooException fe) {
...
} catch(BarException be) {
...
} catch(Exception e) {
...
}
This can be handled compiler side, by attaching/checking properties
to/on the exception continuation.
Matt
Piers Cawley
> At 8:46 AM +0100 3/23/04, Leopold Toetsch wrote:
>>Piers Cawley <pdca...@bofh.org.uk> wrote:
>>> Dan Sugalski <d...@sidhe.org> writes:
>>
>>>>> And what control stack? The continuation chain is the control
>>>>> stack, surely?
>>>>
>>>> Nope. There's the exception handlers, at the very least.
>>
>>> Just add a field to the continuation structure "NextExceptionHandler"
>>> which points to the continuation of the next exception handler in the
>>> chain.
>>
>>What about C code that either installs exception handlers or throws
>>exceptions?
C code that installs exception handlers is (admittedly) tricky, but C
code throwing an exception seems reasonably straightforward. Wrap the C
call in a basic exception handler that catches the C exception and
rethrows to the current continuation's exception continuation.
> Or multiple nested exception handlers,
Invoke the exception continuation, which restores the appropriate
current contination (and associated exception continuation) rethrow
the exception by invoking the new current exception continuation, which
restores a new current continuation (and associated exception
continuation). Rinse. Repeat.
> or serial exception handlers in a block...
Installing an exception handler sets the current exception handler,
removing it unsets it, then you install a new one. Any function calls
will get appropriate exception continuations depending on the currently
set exception handler.
> And then there's the fun with exception handlers and
> coroutines.
>
> It's a stack, like it or not.
So what happens when you invoke a continuation that jumps deep within a
functional call chain with a couple of exception handlers? What happens
when you do it again? ie: Is the control stack properly garbage collected?