RFC: Implicit threading and Implicit event-loop (Was: Re: Continuations)
Em Ter, 2009-05-26 às 19:33 -0700, Jon Lang escreveu:
The exact semantics of autothreading with respect to control
structures are subject to change over time; it is therefore erroneous
to pass junctions to any control construct that is not implemented via
as a normal single or multi dispatch. In particular, threading
junctions through conditionals correctly could involve continuations,
which are almost but not quite mandated in Perl 6.0.0.
What is a continuation?
Continuation here is meant in the most generic sense, which is:
The rest of the thread of execution
It doesn't imply any specific API on manipulating the continuations, nor
it implies that the continuations are re-invocable, cloneable or
anything like that.
It basically means that the interpreter can choose to interrupt your
code at any point and continue it later, after running some other code.
This has the basic effect that Perl 6 points toward *implicit threading*
rather than explicit, and also that it points toward *implicit event
loop* rather than explicit.
In practical terms:
sub baz (*...@input) {
for @input - $element {
say BAZ!;
$element + 1;
}
}
sub foo (*...@input) {
for @input - $element {
say FOO!;
$element - 1;
}
}
sub bar (*...@input) {
for @input - $element {
say BAR!;
$element * 2;
}
}
say BEFORE!;
my @a == baz == foo == bar == $*IN;
say AFTER;
Is going to open 5 implicit threads (which might be delegated to any
number of worker threads), besides the initial thread. So, at first,
you'll immediatly see in the output:
BEFORE!
AFTER!
The implicit threads are:
1 - read from $*IN and push into a lazy list X
2 - read from the lazy list X, run an iteration of the for in the sub
bar, and push to the lazy list Y
3 - read from the lazy list Y, run an iteration of the for in the sub
foo, and push to the lazy list W
4 - read from the lazy list W, run an iteration of the for in the sub
baz, and push to the lazy list Z
5 - read from the lazy list Z and push into the lazy list that
happens to be stored in '@a'
That basically means that this lazy lists are attached to the
interpreter main-loop (yes, Perl 6 should implement something POE-like
in its core), which will allow the read of IO to be non-blocking, so you
don't need a OS thread for that. It also means that every lazy list
should be somehow attached to that event-loop.
So, as you enter data in $*IN, you should get something like that:
I entered this line!
BAR!
FOO!
BAZ!
I entered this other line!
BAR!
FOO!
BAZ!
On the implementation side, I think there is going to be a
ControlExceptionWouldBlock, which is raised by every lazy object when
the data is not immediatly available, allowing the interpreter to put
this continuation in a blocked state, somehow registering a listener
to the event that blocks it.
One of the attributes of the ControlExceptionWouldBlock would be a
Observable object, this Observable object is the thing that is waiting
for the specific event to happen and register additional listeners to
that event. The interpreter itself will register itself as an Observer
to that Observable, so it can re-schedule the thread, marking it as
waiting.
That being said, I think we have a continuation pool which are in
either running, blocked or waiting state. And a scheduler that
takes this continuations and assign to the worker threads, while you
can use a command line switch to control the minimum/maximum number of
worker threads as well as the parameter for when to start a new worker
thread and when to deactivate it...
Well, this is my current view on the state of affairs, and is thougth a
lot in the context of SMOP, so it would be really interesting to have
some feedback from the parrot folks...
daniel
Re: Continuations
Andrew Whitworth wrote:
The issue mentioned in the Synopses is that junctions autothread, and
autothreading in a conditional could potentially create multiple
threads of execution, all of which are taking different execution
paths. At some point, to bring it all back together again, the various
threads could use a continuation to return back to a single execution
flow.
Hmm. If that's the case, let me suggest that such an approach would
be counterintuitive, and not worth considering. When I say if any of
these books are out of date, review your records for inconsistencies;
otherwise, make the books available for use, I don't expect to end up
doing both tasks. In a similar manner, I would expect junctions not
to autothread over conditionals, but to trigger at most one execution
path (continuation?). The real issue that needs to be resolved, I
believe, is illustrated in the following statement:
if any of these books are out of date, review them. The question,
as I understand it, is what is meant by 'them'? Is it these
books, or is it the ones that are out of date? In perl 6 terms:
$x = any(@books);
if $x.out-of-date { $x.review }
Is this equivalent to:
if any(@books).out-of-date { any(@books).review }
or:
if any(@books).out-of-date { any(@books.grep {.out-of-date} ).review }
I don't mean to reopen the debate; though if we can get some
resolution on this, I won't mind. But I _would_ at least like to see
the summary of the issue stated a bit more clearly.
--
Jonathan Dataweaver Lang
Re: RFC: Implicit threading and Implicit event-loop (Was: Re: Continuations)
Sounds like threads to me.
What I see that's different from common threads in other languages is
that they are all the same, rather than one master and many new threads
that have no context history above them. In Perl 6, every thread sees
the same dynamic scope as the original. It doesn't matter which one is
left standing to continue and eventually return up the context chain.
--John
Daniel Ruoso daniel-at-ruoso.com |Perl 6| wrote:
Em Ter, 2009-05-26 às 19:33 -0700, Jon Lang escreveu:
The exact semantics of autothreading with respect to control
structures are subject to change over time; it is therefore erroneous
to pass junctions to any control construct that is not implemented via
as a normal single or multi dispatch. In particular, threading
junctions through conditionals correctly could involve continuations,
which are almost but not quite mandated in Perl 6.0.0.
What is a continuation?
Continuation here is meant in the most generic sense, which is:
The rest of the thread of execution
It doesn't imply any specific API on manipulating the continuations, nor
it implies that the continuations are re-invocable, cloneable or
anything like that.
It basically means that the interpreter can choose to interrupt your
code at any point and continue it later, after running some other code.
This has the basic effect that Perl 6 points toward *implicit threading*
rather than explicit, and also that it points toward *implicit event
loop* rather than explicit.
In practical terms:
sub baz (*...@input) {
for @input - $element {
say BAZ!;
$element + 1;
}
}
sub foo (*...@input) {
for @input - $element {
say FOO!;
$element - 1;
}
}
sub bar (*...@input) {
for @input - $element {
say BAR!;
$element * 2;
}
}
say BEFORE!;
my @a == baz == foo == bar == $*IN;
say AFTER;
Is going to open 5 implicit threads (which might be delegated to any
number of worker threads), besides the initial thread. So, at first,
you'll immediatly see in the output:
BEFORE!
AFTER!
The implicit threads are:
1 - read from $*IN and push into a lazy list X
2 - read from the lazy list X, run an iteration of the for in the sub
bar, and push to the lazy list Y
3 - read from the lazy list Y, run an iteration of the for in the sub
foo, and push to the lazy list W
4 - read from the lazy list W, run an iteration of the for in the sub
baz, and push to the lazy list Z
5 - read from the lazy list Z and push into the lazy list that
happens to be stored in '@a'
That basically means that this lazy lists are attached to the
interpreter main-loop (yes, Perl 6 should implement something POE-like
in its core), which will allow the read of IO to be non-blocking, so you
don't need a OS thread for that. It also means that every lazy list
should be somehow attached to that event-loop.
So, as you enter data in $*IN, you should get something like that:
I entered this line!
BAR!
FOO!
BAZ!
I entered this other line!
BAR!
FOO!
BAZ!
On the implementation side, I think there is going to be a
ControlExceptionWouldBlock, which is raised by every lazy object when
the data is not immediatly available, allowing the interpreter to put
this continuation in a blocked state, somehow registering a listener
to the event that blocks it.
One of the attributes of the ControlExceptionWouldBlock would be a
Observable object, this Observable object is the thing that is waiting
for the specific event to happen and register additional listeners to
that event. The interpreter itself will register itself as an Observer
to that Observable, so it can re-schedule the thread, marking it as
waiting.
That being said, I think we have a continuation pool which are in
either running, blocked or waiting state. And a scheduler that
takes this continuations and assign to the worker threads, while you
can use a command line switch to control the minimum/maximum number of
worker threads as well as the parameter for when to start a new worker
thread and when to deactivate it...
Well, this is my current view on the state of affairs, and is thougth a
lot in the context of SMOP, so it would be really interesting to have
some feedback from the parrot folks...
daniel
Re: Continuations
Jon Lang dataweaver-at-gmail.com |Perl 6| wrote: From S09, under Junctions: The exact semantics of autothreading with respect to control structures are subject to change over time; it is therefore erroneous to pass junctions to any control construct that is not implemented via as a normal single or multi dispatch. In particular, threading junctions through conditionals correctly could involve continuations, which are almost but not quite mandated in Perl 6.0.0. What is a continuation? http://en.wikipedia.org/wiki/Continuation Early on, Perl 6 discussion featured a lot on Continuations. Now, I don't see it anywhere at all, and believe that the general form is not required, by design. That is, not mandated. It's a computer science concept that generalizes *all* forms of flow control including exceptions, co-routines, etc. The long-jump or exception is a more normal case of returning to something that is still in context, but imagine if you could go both ways: bookmark something in the code, like making a closure but for the complete calling stack of activation complexes, and then jump back to it later.
Re: Continuations
On Tue, May 26, 2009 at 8:05 PM, John M. Dlugosz 2nb81l...@sneakemail.com wrote: Jon Lang dataweaver-at-gmail.com |Perl 6| wrote: From S09, under Junctions: The exact semantics of autothreading with respect to control structures are subject to change over time; it is therefore erroneous to pass junctions to any control construct that is not implemented via as a normal single or multi dispatch. In particular, threading junctions through conditionals correctly could involve continuations, which are almost but not quite mandated in Perl 6.0.0. What is a continuation? http://en.wikipedia.org/wiki/Continuation Early on, Perl 6 discussion featured a lot on Continuations. Now, I don't see it anywhere at all, and believe that the general form is not required, by design. That is, not mandated. It's a computer science concept that generalizes *all* forms of flow control including exceptions, co-routines, etc. The long-jump or exception is a more normal case of returning to something that is still in context, but imagine if you could go both ways: bookmark something in the code, like making a closure but for the complete calling stack of activation complexes, and then jump back to it later. OK; that's about as clear as mud. But I think I've got a rough idea about what you're talking about. Next question: what does that have to do with junctions? -- Jonathan Dataweaver Lang
Re: Continuations and inferior runloops: Analysis and POC
From: Leopold Toetsch [EMAIL PROTECTED]
Date: Wed, 9 Aug 2006 14:00:19 +0200
The continuation barrier is only one nastyness of inferior runloops. The
second problem with it is that it heavily influences the guts of garbage
collection . . .
See Method Overloading and GC Issues in Cfunc.pod. The only way
IMHO to avoid this problem is to run GC at safe points at the
runloop level . . .
Had you considered keeping track of object references from C variables
explicitly? This is what Emacs does, and the overhead is surprisingly
low -- less than one line in 300. There are occasional bugs introduced
due to failure to GCPRO the right things at the right times, but the
cost might be more acceptable than conservative GC. (But, IIUC, your
Csub proposal should make this problem completely avoidable, so this is
just academic curiosity.)
. . . But the code splitting can be simplifed vastly IMHO. Your POC
is creating an extra layer between opcodes and C code, which is
basically doing two things:
- manage to call user code on behalf of the C code and pass args to it:
CParrot_op_set_reg_from_vtable and C C_continuation stuff
- pass return results back to the opcode:
Cstore_tail_result_into_register
Yes.
The proposal below is dealing with these issues directly in the runloop.
Basically all C code is called like this:
if (info-op_func(interpreter, args)) {
/* if it branched, goto new pc */
pc = args[n - 1];
}
where Cop_func is any C function following this calling convention
. . .
Yes; your proposal clearly goes farther, addressing more problems by
taking a larger view. And, at least as importantly, it is much less
ugly than the code I wrote.
When now this opcode function is overloaded, it would be a stub that
- invokes the PASM/PIR subroutine, which returns the new Cpc
and creates a return continuation
- sets up current_args and current_results pointers
Then the runloop would just dispatch to the PASM/PIR user code and run it
w/o
any inferior runloop.
There's still the mentioned problem of calling user code deeply inside some
called C function. E.g. calling Cget_string from with Cparrot_pass_args
due to argument conversion. This can be handled by a combination of:
a) roll it into the runloop e.g.
print_p = set_s_p ; print_s
b) disallow or restrict some overloading
c) handle argument conversion at the runloop too
We still need a mechanism to run C when the PASM/PIR sub returns,
though. In the case of (e.g.) rewinding the stack, you need a hook to
tell Continuation:invoke to resume rewinding [1].
. . .
The attached Cfunc.pod has plenty other reasons, why we might need to
change C internals as well. The continuation barrier is just one of
these.
Comments welcome,
leo
I have mostly questions, but these are about details; I'd rather see
others respond first.
There is one pressing question, though: I had intended to use the
continuation-tailcalling mechanism from the POC to eliminate inferior
runloops from stack rewinding, as the logical next step in my campaign
to clean up dynamic environment support. Should I wait for a more
complete Cfunc.pod design, or should I proceed in the expectation that
the continuation-tailcalling mechanism isn't likely to change that much?
-- Bob
[1] Of course, that can be done in terms of a Csub, but you still need
the equivalent of C_closure state.
Re: Continuations and inferior runloops: Analysis and POC
Am Samstag, 12. August 2006 17:55 schrieb Bob Rogers: From: Leopold Toetsch [EMAIL PROTECTED] See Method Overloading and GC Issues in Cfunc.pod. The only way IMHO to avoid this problem is to run GC at safe points at the runloop level . . . Had you considered keeping track of object references from C variables explicitly? Ah, yep. I forget about that. It was discussed (and discarded) some years ago and is also documented: $ perldoc docs/dev/infant.pod Solution 3: Explicit root set augmentation Variant 1: Temporarily anchor objects There is one pressing question, though: I had intended to use the continuation-tailcalling mechanism from the POC to eliminate inferior runloops from stack rewinding, as the logical next step in my campaign to clean up dynamic environment support. Should I wait for a more complete Cfunc.pod design, or should I proceed in the expectation that the continuation-tailcalling mechanism isn't likely to change that much? I dunno yet. A general continuation-tailcalling mechanism could still be needed for all stuff that just can't be (easily) forced into the runloop like a user-defined sort function. OTOH, if all is done properly, we might only have a few special cases, which could be handled as such. -- Bob leo
Re: Continuations and inferior runloops: Analysis and POC
Am Sonntag, 6. August 2006 17:20 schrieb Bob Rogers:
The problem is that inferior runloops cannot be re-entered via
continuation. One example (out of many) is the delegate pmclass, which
uses inferior runloops in vtable methods to run bytecode. The resulting
call structure (mixing bytecode and C) looks like this:
main runloop
= main bytecode
= op (e.g. set_s_p)
= vtable method
= inferior runloop
= method bytecode
The continuation barrier is only one nastyness of inferior runloops. The
second problem with it is that it heavily influences the guts of garbage
collection. Due to the involved C code with its auto-storage objects on the
C-stack, we have to walk the C-stack for active objects. This is the reason
that our GC system is termed 'conservative', but much worse, it effectively
prevents timely destruction.
See Method Overloading and GC Issues in Cfunc.pod. The only way IMHO to
avoid this problem is to run GC at safe points at the runloop level, so
that we don't have to trace any system areas (HW registers and C stack). This
can be achieved by a) avoiding inferior runloops and b) triggering GC within
some opcodes like Cnew, if there is resource shortage but not inside C
code. I.e. if an allocation inside C code needs more objects, it would just
set a flag need_GC, allocate more objects and proceed.
This would have also the advantage, that no pointers (e.g. str-strstart)
would move under C code.
Back to continuations.
2. Eliminate inferior runloops. This is much harder, as it involves
rewriting much code, though the attached POC (see patch; more on this
below) shows that it is possible. The essential strategy is to split
the C code into two or more portions, the first containing the part that
sets up the bytecode call, and the rest deals with the result.
Exactly. But the code splitting can be simplifed vastly IMHO. Your POC is
creating an extra layer between opcodes and C code, which is basically doing
two things:
- manage to call user code on behalf of the C code and pass args to it:
CParrot_op_set_reg_from_vtable and C C_continuation stuff
- pass return results back to the opcode:
Cstore_tail_result_into_register
The proposal below is dealing with these issues directly in the runloop.
Basically all C code is called like this:
if (info-op_func(interpreter, args)) {
/* if it branched, goto new pc */
pc = args[n - 1];
}
where Cop_func is any C function following this calling convention. (It
might be reasonable to also pass an argument signature or argument count, but
this are implementation details).
When now this opcode function is overloaded, it would be a stub that
- invokes the PASM/PIR subroutine, which returns the new Cpc
and creates a return continuation
- sets up current_args and current_results pointers
Then the runloop would just dispatch to the PASM/PIR user code and run it w/o
any inferior runloop.
There's still the mentioned problem of calling user code deeply inside some
called C function. E.g. calling Cget_string from with Cparrot_pass_args
due to argument conversion. This can be handled by a combination of:
a) roll it into the runloop e.g.
print_p = set_s_p ; print_s
b) disallow or restrict some overloading
c) handle argument conversion at the runloop too
The POC runloop below (np2.c) basically splits the runloop into 2 parts:
a) fast inlined (switched) opcodes
b) Cfunc calls, with argument setup performed in the runloop
This argument setup could also be used for calling PASM/PIR code so that
necessary argument conversions, which might trigger user code, are also
executed in the runloop.
The attached Cfunc.pod has plenty other reasons, why we might need to change C
internals as well. The continuation barrier is just one of these.
Comments welcome,
leo
=head1 TITLE
Calling C Functions
=head1 STATUS
Proposal, supersedes parts of Finterfaces.pod.
This document does not describe HL issues of interfaces, but rather
the internals that might be needed to implement it.
=head1 AUTHOR
Leopold Toetsch
=head1 ABSTRACT
Parrot is calling C functions on behalf of user code in a vast
variety: opcode and vtable functions, (multi-)subs and -methods. All
these functions are called with differing calling schemes, which is
causing a lot of issues.
This document is covering mainly opcodes. The description of current
state is also showing some problems with vtables and methods. But a
generalization to vtable/methods and interfaces needs still more
specifications from the namespace front.
This proposal tries to describe current state and a possible solution.
=head1 DESCRIPTION of STATE
Classification of function types.
=head2 Opcode Functions
Parrot has currently +1200 opcodes. There are basically two types of
opcodes: simple, easily-JITtable [1] (mostly number-related) opcodes,
which have a representation at the
Re: Continuations and inferior runloops: Analysis and POC
Am Sonntag, 6. August 2006 17:20 schrieb Bob Rogers: [ a much more detailed answer will follow ] The problem is that inferior runloops cannot be re-entered via continuation. Cget_string is an excellent example for the POC. I've a first question though: assuming that we might want to eliminate inferior runloops, what can we do about usage of (e.g.) Cget_string in: a) print P0 b) foo(P0)# function call with Preg ... .sub foo .param string s # string param a) could be easy by making the get_string explicit in the opcodes: $S0 = P0# imcc could handle this conversion print $S0 but I see little chance to catch b) at compile time. And b) is of course really nasty, as the Cget_string is occuring during argument passing, which has also to be used for any replacement functionality. leo
Re: Continuations and inferior runloops: Analysis and POC
From: Leopold Toetsch [EMAIL PROTECTED]
Date: Tue, 8 Aug 2006 19:43:31 +0200
Am Sonntag, 6. August 2006 17:20 schrieb Bob Rogers:
[ a much more detailed answer will follow ]
? ?The problem is that inferior runloops cannot be re-entered via
continuation. ?
Cget_string is an excellent example for the POC. I've a first question
though: assuming that we might want to eliminate inferior runloops, what can
we do about usage of (e.g.) Cget_string in:
a) print P0
b) foo(P0)# function call with Preg
...
.sub foo
.param string s # string param
a) could be easy by making the get_string explicit in the opcodes:
$S0 = P0# imcc could handle this conversion
print $S0
Or print_p (which is not much more complicated than set_s_p) could be
reimplemented using a print_tail_result helper fn instead of
store_tail_result_into_register. (Given the difficulty I've had with
set_retval, that would have made an easier POC, come to think of it.)
but I see little chance to catch b) at compile time. And b) is of
course really nasty, as the Cget_string is occuring during argument
passing, which has also to be used for any replacement functionality.
leo
Yes, this is a good example of the kind of pain I meant. If we insisted
on trying to optimize this away, we'd be limited to supporting languages
no more dynamic than Java or C# -- and that's pretty limited. ;-} [1]
It can still be done, IIUC. Since an arbitrary number of
get_{string,number,integer} calls might be required, the arg processing
loop would have to be rewritten as a tail-recursion, and then broken
into thunks so that each could be called as a C_continuation if
necessary. But it may depend on how many places need to call
parrot_pass_args and its kin, and how difficult *those* are to rewrite.
This may not be quite so as bad as it seems -- the current algorithm
(as you well know!) already revolves around an explicit struct
call_state. On the other hand, it's not a PMC, and we'd have to figure
out how to keep GC on during arg processing.
Then there are :flat arrays. What if some user passes a :flat arg
using an array class with an overloaded get_pmc_keyed_int method?
Methinks it would be good to draw a line here.
Your detailed reply is eagerly awaited,
-- Bob
[1] Actually, I take that back: For INS formals, IMCC could generate a
prolog that is equivalent to this for each parameter n:
Cn:
unless param_n_needs_conversion goto Cn+1
param_n = param_n_temp
Cn+1:
. . .
So if the value destined for param_n is a PMC, process_args
stuffs it into param_n_temp (still a P register) and sets the
param_n_needs_conversion flag. The fact that coercion is
out-of-order with respect to the assignment of other formals should
not matter; it won't be visible to vtable methods [2]. The whole
prolog would be unecessary if all were P formals, and could be
skipped at runtime if no coercion was required.
It rather seems like a band-aid to me. But it would be easier in
the short term.
[2] Unless we should someday provide a mechanism for formals to be bound
dynamically.
Re: Continuations and inferior runloops: Analysis and POC
Bob Rogers wrote: There are two broad solutions: 1. Restrict continuations to move only outward, which makes it unnecessary to restart inferior runloops. This may not be as bad as it seems, as most of the languages I can think of can be implemented using only outward (returning) continuations. And I believe the rest (including Scheme) can be implemented without Parrot continuations, by using the CP transformation, which is a standard Scheme compiler technique in any case. However, we'd probably have to abandon coroutines, since telling people that they can't use coroutines with OO programming is really lame. Important to consider this option, but overall it's too restrictive and doesn't allow enough room for the future evolution of programming languages. (Yeah, we can't go out of our way to accommodate languages that don't exist yet. The YAGNI principle applies. But we can avoid making decisions along the lines of No one could ever need more than 64K of RAM.) 2. Eliminate inferior runloops. This is much harder, as it involves rewriting much code, though the attached POC (see patch; more on this below) shows that it is possible. The essential strategy is to split the C code into two or more portions, the first containing the part that sets up the bytecode call, and the rest deals with the result. Ironically, this is just the CP transformation mentioned earlier; we are turning the latter half of the C code into a continuation, and then arrange to call it after the bytecode returns. Unfortunately, this is a pain in C, as we have to fake a closure in order to retain state between the C functions. In general, this is the right direction to head. But that's about like saying you can get to Chicago from Portland by heading east. It is true, but we'll have to work out a few more details before we get there. The second solution is subject to a few variations: V1. It may be possible to redesign delegation in a way that doesn't involve vtable methods. For instance, it's not clear that all uses of VTABLE_get_string (there are ~250 of them) need to support delegation, and some of them might be really hard to rewrite, being within deeply nested C calls. Of course, set_s_p would need to call a delegated method, but that is easier to special-case (it is the subject of the POC). And that only covers some of the vtable-to-bytecode cases. V2. Failing that, it may be possible to limit the number of vtable methods that are subject to delegation. In specific, both of these solutions are too specific. These two variations extend Parrot with C code that calls back into bytecode, but the general principle applies to any C code used to extend Parrot. That doesn't mean we need to support CPS and exceptions in any arbitrary C code called from within Parrot (the native call interface handles more general C libraries), but it does mean we need to be a bit more general than limiting or eliminating vtable methods from delegation. We can put some restrictions on the C code that avoids inferior runloops. These fall into the general category of calling conventions: we can require set-up and tear-down code wrapped around the C code; we can require any calls out of the C code (to bytecode, other C code, or by throwing an exception) to set up certain information before the call; we can probably even go so far as limiting what C features you can use in extension code; we can certainly provide macros to ease the pain of whatever constraints we put on C extension code. (This isn't a solution, it's just the tools we can use to reach a solution.) What are the necessary and essential aspects of the Parrot calling conventions that a C routine would need to replicate or emulate in order to act as if it was a Parrot subroutine/method/opcode? - accepting a return continuation as an argument? - returning from the C code by invoking the return continuation passed in? - creating a return continuation for any calls out of the C code (perhaps a special return continuation that externally acts just like an ordinary one, but internally takes special actions or stores special information for interfacing with the C code)? Other suggestions? Leo? MMD doesn't worry me. It has long been known that Parrot MMD needs to be reimplemented more efficiently, and my own favorite candidate for the job is the FSM-based dispatch that is standard technology for Common Lisp systems. The idea is that, instead of doing the type dispatch directly, the MMD engine builds an FSM in PIR that does argument discrimination, compiles it to bytecode, caches it for future use, then calls it to handle the case at hand. That neatly kills multiple birds with one stone. I can't say I'm entirely enamored with the idea of handling MMD with a Lispy FSM. OTOH, I do suspect that ultimately MMD will have to be extensible, to allow for different ways to do MMD. But that's a rabbit-trail, so let's save it
Re: Continuations, basic blocks, loops and register allocation
Matt Fowles [EMAIL PROTECTED] wrote: ... Thus you can consider all of the following questions (even though they will be phrased as statements). 1) After a full continuation is taken all of the registers must be considered invalid. Calling a subroutine allocates a new register frame, that subs register frame pointer in the context points to these fresh registers. A continuation restores the context it captured, i.e. at the place, where it was created. This is true for all continuations. Inside the context there is a *pointer* to a register frame, which is therefore restored too. The effect of taking a continuation is therefore to restore registers to that state where the continuation was created. Due to calling conventions a part of the registers is volatile (used during a call or as return results), while the other part is non-volatile. Until here there is no difference between return or full continuation. The effect of a full continuation can be to create a loop, where the known control flow doesn't show a loop. Without further syntax to denote such loops 1) is true. This register invalidation happens, if a preserved register was e.g. only used once after the call and then that register got reassigned, which is allowed for a linear control flow but not inside a loop. This has per se nothing to do with a continuation. If you got an opcode that does *silently* a goto again_label the CFG doesn't cope with the loop, because it isn't there and things start breaking. The effect of a full continuation *is* to create such loops. 2) After a return continuation is taken, the registers can be trusted. Yes, according to usage in pdd03. 3) If someone takes a full continuation, all return continuations down the callstack must be promoted. If one *creates* a full continuation ... 4) After a function call, some magic needs to happen so that the code knows whether it came back to itself via a return continuation and can trust its registers, or it came back via a full continuation and cannot trust them. No. It's too late for magic. Either the CFG is known at compile time or refetching in the presence of full continuations is mandatory. For both the code must reflect the facts. Corrections welcome, Matt leo
Re: Continuations, basic blocks, loops and register allocation
Leo~ Thanks for the clarification. Matt On Wed, 17 Nov 2004 08:48:58 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: Matt Fowles [EMAIL PROTECTED] wrote: ... Thus you can consider all of the following questions (even though they will be phrased as statements). 1) After a full continuation is taken all of the registers must be considered invalid. Calling a subroutine allocates a new register frame, that subs register frame pointer in the context points to these fresh registers. A continuation restores the context it captured, i.e. at the place, where it was created. This is true for all continuations. Inside the context there is a *pointer* to a register frame, which is therefore restored too. The effect of taking a continuation is therefore to restore registers to that state where the continuation was created. Due to calling conventions a part of the registers is volatile (used during a call or as return results), while the other part is non-volatile. Until here there is no difference between return or full continuation. The effect of a full continuation can be to create a loop, where the known control flow doesn't show a loop. Without further syntax to denote such loops 1) is true. This register invalidation happens, if a preserved register was e.g. only used once after the call and then that register got reassigned, which is allowed for a linear control flow but not inside a loop. This has per se nothing to do with a continuation. If you got an opcode that does *silently* a goto again_label the CFG doesn't cope with the loop, because it isn't there and things start breaking. The effect of a full continuation *is* to create such loops. 2) After a return continuation is taken, the registers can be trusted. Yes, according to usage in pdd03. 3) If someone takes a full continuation, all return continuations down the callstack must be promoted. If one *creates* a full continuation ... 4) After a function call, some magic needs to happen so that the code knows whether it came back to itself via a return continuation and can trust its registers, or it came back via a full continuation and cannot trust them. No. It's too late for magic. Either the CFG is known at compile time or refetching in the presence of full continuations is mandatory. For both the code must reflect the facts. Corrections welcome, Matt leo -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
Matt Fowles [EMAIL PROTECTED] wrote: [ continuations should restore registers ] I am sorry, but I don't understand what you are trying to say here. Would you mind rewording it for me? Imagine a simple loop: i = 0 lp: foo() inc i if i 10 goto lp Looking at the loop counter a programmer or optimizer could easily decide that using an I-Reg for it instead of a P-Reg is fine. Now comes your proposed implementation for continuations: they copy the register frame on creation and restore it on invocation. Besides of the big cost of the memcpy's this simple loop above suddenly stops working, depending on the implementation of foo() - which might be outside your control. BTW in an early stage we had exactly this behavior of continuations. This was abandoned. The subject was IIRC something like Should continuations close over registers. The answer was clearly no. leo
Re: Continuations, basic blocks, loops and register allocation
Leo~ On Tue, 16 Nov 2004 09:23:24 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: Matt Fowles [EMAIL PROTECTED] wrote: [ continuations should restore registers ] I am sorry, but I don't understand what you are trying to say here. Would you mind rewording it for me? Imagine a simple loop: i = 0 lp: foo() inc i if i 10 goto lp Looking at the loop counter a programmer or optimizer could easily decide that using an I-Reg for it instead of a P-Reg is fine. Now comes your proposed implementation for continuations: they copy the register frame on creation and restore it on invocation. Besides of the big cost of the memcpy's this simple loop above suddenly stops working, depending on the implementation of foo() - which might be outside your control. BTW in an early stage we had exactly this behavior of continuations. This was abandoned. The subject was IIRC something like Should continuations close over registers. The answer was clearly no. There is one thing I am not sure about here. The loop will work correctly for each seperate invocation of the appropriate continuation. The first time you call foo i is 0. The second time i is 1. If foo ever invokes the full continuations that it captured at one of these points, then i will go back to whatever it was when that continuation was captured. All of this seems like reasonable behavior to me. In the general case our optimizer will not be able to downgrad i from a P to an I register anyway, as foo could mess with $CALLER::i or whatever. Thus, I am not sure that I by your argument. Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
Matt Fowles [EMAIL PROTECTED] wrote: Leo~ On Tue, 16 Nov 2004 09:23:24 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: i = 0 lp: foo() inc i if i 10 goto lp There is one thing I am not sure about here. The loop will work correctly for each seperate invocation of the appropriate continuation. No. Imagine, foo() is not a simple function anymore. Someone e.g. Jens Rieks[1], discovers that the algoritm is simpler implemented with continuations. So inside foo() the return continuation of foo() is copyied, stored elsewhere, passed along to another function, and that one now suddenly returns via this continuation to your loop. If this invocation of the continuation would restore registers suddenly the loop will become an infinite one, as Ci is always restored to zero. [1] Have a look at runtime/parrot/library/Streams/Sub.imc leo
Re: Continuations, basic blocks, loops and register allocation
Leo~ On Tue, 16 Nov 2004 16:37:04 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: Matt Fowles [EMAIL PROTECTED] wrote: Leo~ On Tue, 16 Nov 2004 09:23:24 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: i = 0 lp: foo() inc i if i 10 goto lp There is one thing I am not sure about here. The loop will work correctly for each seperate invocation of the appropriate continuation. No. Imagine, foo() is not a simple function anymore. Someone e.g. Jens Rieks[1], discovers that the algoritm is simpler implemented with continuations. So inside foo() the return continuation of foo() is copyied, stored elsewhere, passed along to another function, and that one now suddenly returns via this continuation to your loop. If this invocation of the continuation would restore registers suddenly the loop will become an infinite one, as Ci is always restored to zero. [1] Have a look at runtime/parrot/library/Streams/Sub.imc leo I disagree with that analysis. Let us consider the actual effect of such an implementation. First iteration i = 0; foo(); #at this point a continuation created capturing i=0, promoted by Jens and stuff happens #eventually it is invoked, restoring i=0 i++; #i = 1 foo(); #at this point a NEW return continuation is created capturing i=1; promoted by Jens... #eventually it is invoked, restoring i=1 i++; #i = 2 ... Thus every single invocation of foo will have an i one greater than the last. If foo's algorithm had an error and did not use the new return continuation to recreate its internal continuation each time, then you would be correct. But that would be a bug in the implementation of foo. As the following code #set up for foo foo() #set other stuff for foo foo() would be an infinite loop alway returning immediately after the first invocation of foo. I looked at Sub.imc and think it would work because write always creates a new Continuation for each invocation of write. Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
At 11:52 AM -0500 11/16/04, Matt Fowles wrote: Leo~ On Tue, 16 Nov 2004 16:37:04 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: Matt Fowles [EMAIL PROTECTED] wrote: Leo~ On Tue, 16 Nov 2004 09:23:24 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: i = 0 lp: foo() inc i if i 10 goto lp There is one thing I am not sure about here. The loop will work correctly for each seperate invocation of the appropriate continuation. No. Imagine, foo() is not a simple function anymore. Someone e.g. Jens Rieks[1], discovers that the algoritm is simpler implemented with continuations. So inside foo() the return continuation of foo() is copyied, stored elsewhere, passed along to another function, and that one now suddenly returns via this continuation to your loop. If this invocation of the continuation would restore registers suddenly the loop will become an infinite one, as Ci is always restored to zero. [1] Have a look at runtime/parrot/library/Streams/Sub.imc leo I disagree with that analysis. You would, however, in this case be incorrect. The loop variable must have a backing store outside of the register set. The contents of registers must be assumed to be unreliable when a continuation is continued. If we declare that they are put back into the state they were when the continuation was taken, which is reasonable though not required, the values of non-reference type registers (ints and floats) will be reset. The rference type registers (strings and PMCs) will also be reset so the pointers to the string/pmc structs will be what they were when the continuation was taken, but as they are references the referred-to thing may have changed and the changed value will be seen. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, basic blocks, loops and register allocation
Matt Fowles wrote: I disagree with that analysis. Let us consider the actual effect of such an implementation. First iteration i = 0; foo(); #at this point a continuation created capturing i=0, promoted by Jens and stuff happens #eventually it is invoked, restoring i=0 i++; #i = 1 foo(); #at this point a NEW return continuation is created capturing That would work if there is a one to one representation of the invoation of foo() an it's continuation. But no one guarantees that. By repeatedly invocing the continuation you alway get to the opcode after invoke, and registers would be restored to some earlier state. ... If foo's algorithm had an error and did not use the new return continuation to recreate its internal continuation each time, then you would be correct. But that would be a bug in the implementation of foo. Why? If foo's implementation is changed internally to double it's work per call, it could indicate that progress by returning twice through the same continuation. E.g. unless done (done, result) = foo() s .= result leo
Re: Continuations, basic blocks, loops and register allocation
Dan~ On Tue, 16 Nov 2004 12:29:19 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 11:52 AM -0500 11/16/04, Matt Fowles wrote: Leo~ On Tue, 16 Nov 2004 16:37:04 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: Matt Fowles [EMAIL PROTECTED] wrote: Leo~ On Tue, 16 Nov 2004 09:23:24 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: i = 0 lp: foo() inc i if i 10 goto lp There is one thing I am not sure about here. The loop will work correctly for each seperate invocation of the appropriate continuation. No. Imagine, foo() is not a simple function anymore. Someone e.g. Jens Rieks[1], discovers that the algoritm is simpler implemented with continuations. So inside foo() the return continuation of foo() is copyied, stored elsewhere, passed along to another function, and that one now suddenly returns via this continuation to your loop. If this invocation of the continuation would restore registers suddenly the loop will become an infinite one, as Ci is always restored to zero. [1] Have a look at runtime/parrot/library/Streams/Sub.imc leo I disagree with that analysis. You would, however, in this case be incorrect. The loop variable must have a backing store outside of the register set. The contents of registers must be assumed to be unreliable when a continuation is continued. If we declare that they are put back into the state they were when the continuation was taken, which is reasonable though not required, the values of non-reference type registers (ints and floats) will be reset. The rference type registers (strings and PMCs) will also be reset so the pointers to the string/pmc structs will be what they were when the continuation was taken, but as they are references the referred-to thing may have changed and the changed value will be seen. I am having trouble in that I agree with what you are saying, but I am coming to a different conclusion. I think that foo would create a new continuation (from it return continuation) each time it is called, and thus things below it on the call stack would be unaffected by its own internal continuation tricks (assuming for the moment that registers are put back into place by continuations). Since both you and Leo are arguing against me here, it seems like that I am wrong, but I would like to figure out exactly why I am wrong so that I can correct my train of thought in the future. Thanks, Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
On Nov 15, 2004, at 10:29 AM, Leopold Toetsch wrote:
Jeff Clites [EMAIL PROTECTED] wrote:
Picture this call stack:
main -- A -- B -- C -- D -- E
The call from D to E uses the RESUMEABLE label, and E stores the
resulting continuation in a global, and everything up to main returns.
Then, main invokes the continuation, and we find ourselves back in D.
Now, C, B, and A will return again, without any compile-time hint.
That's fine. The return is an expected operation. I don't think that's
the problem. The error in gc_13 is a call path like:
choose() - try (with_cc) - fail() -
|
(choose again) - + --+
|
choose() - try (with_cc) - fail() -|
||
(choose again) - +|
|
fail() --+
The problem now is not per se the path in main from the two choose()
calls down to fail is executed more then once (as it's the case with
multiple returns). The problem is the loop in main. By denoting the
loop
from the call to fail() to the first choose() with some kind of syntax,
the register allocator does the right thing.
But consider even this simple function:
sub B
{
a = 1
foo()
print a
b = 2
return b
}
If something called by foo() captures a continuation, and something
invokes it after B() returns, then there's a hidden branch, in effect,
from the return to the print, isn't there? The register allocator could
decide to use the same register for a and b, but then the second
return from foo() would print 2 instead of 1, which is wrong. And the
author of B(), of course, may have no idea such a thing would happen,
so wouldn't be able to supply any syntax to tell the compiler.
I'm just trying to come up with a simpler example, since it seems to me
that there's a problem any time a function returns, and the last thing
that executed in that frame wasn't a call to that function. (There's a
lot going on in the gc_13 example, and I think some of it is
distracting from the main point.)
But a RESUMABLE label seems like the information that's needed by the
compiler. But on the other hand in an example like the above, the
function B() may not be written to expect foo() to be resumed. So, what
should happen at runtime, if the label is absent? We could declare
undefined behavior, but that would mean that for defined behavior,
you'd need the RESUMABLE label all the way up the stack, and Ruby and
Scheme don't have that syntactic constraint. With Scheme, it's only
clear from the syntax what's going on locally--but you can invoke a
continuation far from any call/cc, if that continuation was stored away
into a variable.
JEff
Re: Continuations, basic blocks, loops and register allocation
Leo~ On Tue, 16 Nov 2004 18:32:07 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: Matt Fowles wrote: I disagree with that analysis. Let us consider the actual effect of such an implementation. First iteration i = 0; foo(); #at this point a continuation created capturing i=0, promoted by Jens and stuff happens #eventually it is invoked, restoring i=0 i++; #i = 1 foo(); #at this point a NEW return continuation is created capturing That would work if there is a one to one representation of the invoation of foo() an it's continuation. But no one guarantees that. I suppose that what I am arguing is that anyone who does not maintain such a one-to-one representation (at least from the perspective of code calling foo()); full well deserves what they get. They are restoring the execution to an earlier state by invoking an old continuation. If the earlier state called them again the first time, they should probably expect the earlier state to call them again the second time. Unless they have some specific knowledge that the earlier state will change it behavior (because things in the heap have changed), there should be no expectation for it to. Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
On Nov 16, 2004, at 10:03 AM, Matt Fowles wrote:
Since both you and Leo are arguing against me here, it seems like that
I am wrong, but I would like to figure out exactly why I am wrong so
that I can correct my train of thought in the future.
Here's a real example you can play with, if you have Ruby installed:
% cat continuation6.ruby
def strange
callcc {|continuation| $saved = continuation}
end
def outer
a = 0
strange()
a = a + 1
print a = , a, \n
end
# these two lines are main
outer()
$saved.call
% ruby continuation6.ruby
a = 1
a = 2
a = 3
a = 4
a = 5
a = 6
a = 7
a = 8
a = 9
a = 10
...infinite loop, by design
What happens when the program runs is that outer() is called (only
once) which creates a continuation (inside of strange()), increments a,
prints and returns. The next thing that happens is that the
continuation is invoked. Control jumps to the location in strange()
right after the callcc line, then that return and we are at the line in
outer() where 'a' is incremented. So 'a' increments from the last value
it had in that frame (since we are magically back again inside of the
same single invocation of outer()), then 'a' is printed and outer()
returns again (note: outer only called once, returned twice so far),
and then we call the continuation again, and start the loop over.
We only ever create one continuation in this example, since we only
ever call strange() once. The continuation preserves the frame (the
mapping from logical variables to their values), but not the values of
those variables at the time the continuation was created. In effect, I
think the continuation is arranging to preserve the state of the
variables as they were when code in the frame was last executed, rather
than at the time the continuation was created.
The behavior you were describing is what I had thought would happen,
but then I realized I wasn't sure, so I confirmed that it wasn't. The
above is the behavior of Ruby, and I believe Scheme works the same way.
What you described would be useful for backtracking (jumping back not
only to a previous location in a computation, but also its previous
state), but it's not what these languages seem to do.
JEff
Re: Continuations, basic blocks, loops and register allocation
At 10:32 AM -0800 11/16/04, Jeff Clites wrote: The continuation preserves the frame (the mapping from logical variables to their values), but not the values of those variables at the time the continuation was created. This is one of the fundamental properties of continuations, but it does throw people. And it's why register contents have to be thrown away when a continuation is invoked, since the registers have values, and continuations don't preserve values. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, basic blocks, loops and register allocation
Jeff Clites [EMAIL PROTECTED] wrote:
sub B
{
a = 1
foo()
print a
b = 2
return b
}
If something called by foo() captures a continuation, and something
invokes it after B() returns, then there's a hidden branch, in effect,
from the return to the print, isn't there?
Yes. That's right and would cause problems. Again this is creating a
loop as you say from the return to the print statement.
OTOH looking at the scheme example, you can create such continuation
loops just for nested closures. All other usage would be like a goto
statement into the middle of some totally unrelated subroutine, which is
only solvable by going the all gets refetched road.
But a RESUMABLE label seems like the information that's needed by the
compiler. But on the other hand in an example like the above, the
function B() may not be written to expect foo() to be resumed.
Yes. Again, the HLL language, that is creating the code has a clear
indication, what's going on. PIR code currently hasn't.
... With Scheme, it's only
clear from the syntax what's going on locally--but you can invoke a
continuation far from any call/cc, if that continuation was stored away
into a variable.
So all closures inside that call/cc have to be emitted in such a way that
they can cope with it. It's IMHO nothing we can solve, except for
providing some syntax construct that clearly indicates the possible loop
for the CFG.
JEff
leo
Re: Continuations, basic blocks, loops and register allocation
Dan~ On Tue, 16 Nov 2004 13:41:25 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 10:32 AM -0800 11/16/04, Jeff Clites wrote: The continuation preserves the frame (the mapping from logical variables to their values), but not the values of those variables at the time the continuation was created. This is one of the fundamental properties of continuations, but it does throw people. And it's why register contents have to be thrown away when a continuation is invoked, since the registers have values, and continuations don't preserve values. I think right here we have the crux of my failure to understand. I was/am under the impression that the continuation will restore the register frame to exactly as it was when the continuation was taken. Thus those registers which are values (I,N) will continue to have the value they had when the continuation was taken, while those registers which are pointers/references (S, P) will still point to the same place, but that data may have changed. Is this correct? Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
At 3:12 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 13:41:25 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 10:32 AM -0800 11/16/04, Jeff Clites wrote: The continuation preserves the frame (the mapping from logical variables to their values), but not the values of those variables at the time the continuation was created. This is one of the fundamental properties of continuations, but it does throw people. And it's why register contents have to be thrown away when a continuation is invoked, since the registers have values, and continuations don't preserve values. I think right here we have the crux of my failure to understand. I was/am under the impression that the continuation will restore the register frame to exactly as it was when the continuation was taken. Thus those registers which are values (I,N) will continue to have the value they had when the continuation was taken, while those registers which are pointers/references (S, P) will still point to the same place, but that data may have changed. Is this correct? No. The registers are just about the only thing that *isn't* restored. Continuations put the environment back. This includes things like the lexical pad stack, the namespace stack, the stack itself, any security credentials... basically everything that describes the environment. *Data*, on the other hand, is *not* restored. Data stays as it is. Registers are a special case of data, and they're just declared crud by fiat, since otherwise things get nasty and unpredictable. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, basic blocks, loops and register allocation
Dan~ On Tue, 16 Nov 2004 15:25:24 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 3:12 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 13:41:25 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 10:32 AM -0800 11/16/04, Jeff Clites wrote: The continuation preserves the frame (the mapping from logical variables to their values), but not the values of those variables at the time the continuation was created. This is one of the fundamental properties of continuations, but it does throw people. And it's why register contents have to be thrown away when a continuation is invoked, since the registers have values, and continuations don't preserve values. I think right here we have the crux of my failure to understand. I was/am under the impression that the continuation will restore the register frame to exactly as it was when the continuation was taken. Thus those registers which are values (I,N) will continue to have the value they had when the continuation was taken, while those registers which are pointers/references (S, P) will still point to the same place, but that data may have changed. Is this correct? No. The registers are just about the only thing that *isn't* restored. Continuations put the environment back. This includes things like the lexical pad stack, the namespace stack, the stack itself, any security credentials... basically everything that describes the environment. *Data*, on the other hand, is *not* restored. Data stays as it is. Registers are a special case of data, and they're just declared crud by fiat, since otherwise things get nasty and unpredictable. Then I am not sure what you mean by The return continuation PMC type, used to create return continuations used for call/return style programming, guarantees that registers 16-31 will be set such that the contents of those registers are identical to the content of the registers when the return continuation was Icreated. I read that as saying that registers will be restored by continuations. If that is not what it is intended to mean, could you clarify for me. Thanks, Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
At 3:39 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 15:25:24 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 3:12 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 13:41:25 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 10:32 AM -0800 11/16/04, Jeff Clites wrote: The continuation preserves the frame (the mapping from logical variables to their values), but not the values of those variables at the time the continuation was created. This is one of the fundamental properties of continuations, but it does throw people. And it's why register contents have to be thrown away when a continuation is invoked, since the registers have values, and continuations don't preserve values. I think right here we have the crux of my failure to understand. I was/am under the impression that the continuation will restore the register frame to exactly as it was when the continuation was taken. Thus those registers which are values (I,N) will continue to have the value they had when the continuation was taken, while those registers which are pointers/references (S, P) will still point to the same place, but that data may have changed. Is this correct? No. The registers are just about the only thing that *isn't* restored. Continuations put the environment back. This includes things like the lexical pad stack, the namespace stack, the stack itself, any security credentials... basically everything that describes the environment. *Data*, on the other hand, is *not* restored. Data stays as it is. Registers are a special case of data, and they're just declared crud by fiat, since otherwise things get nasty and unpredictable. Then I am not sure what you mean by The return continuation PMC type, used to create return continuations used for call/return style programming, guarantees that registers 16-31 will be set such that the contents of those registers are identical to the content of the registers when the return continuation was Icreated. I read that as saying that registers will be restored by continuations. If that is not what it is intended to mean, could you clarify for me. Return continuations are special, basically. There are a number of specialized continuation forms, and this is one of 'em. Which makes things a bit more confusing but, well, there you go. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, basic blocks, loops and register allocation
Dan~ On Tue, 16 Nov 2004 15:54:48 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 3:39 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 15:25:24 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 3:12 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 13:41:25 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 10:32 AM -0800 11/16/04, Jeff Clites wrote: The continuation preserves the frame (the mapping from logical variables to their values), but not the values of those variables at the time the continuation was created. This is one of the fundamental properties of continuations, but it does throw people. And it's why register contents have to be thrown away when a continuation is invoked, since the registers have values, and continuations don't preserve values. I think right here we have the crux of my failure to understand. I was/am under the impression that the continuation will restore the register frame to exactly as it was when the continuation was taken. Thus those registers which are values (I,N) will continue to have the value they had when the continuation was taken, while those registers which are pointers/references (S, P) will still point to the same place, but that data may have changed. Is this correct? No. The registers are just about the only thing that *isn't* restored. Continuations put the environment back. This includes things like the lexical pad stack, the namespace stack, the stack itself, any security credentials... basically everything that describes the environment. *Data*, on the other hand, is *not* restored. Data stays as it is. Registers are a special case of data, and they're just declared crud by fiat, since otherwise things get nasty and unpredictable. Then I am not sure what you mean by The return continuation PMC type, used to create return continuations used for call/return style programming, guarantees that registers 16-31 will be set such that the contents of those registers are identical to the content of the registers when the return continuation was Icreated. I read that as saying that registers will be restored by continuations. If that is not what it is intended to mean, could you clarify for me. Return continuations are special, basically. There are a number of specialized continuation forms, and this is one of 'em. Which makes things a bit more confusing but, well, there you go. It seems to me that it would simpilify much of the code, and reduce the number of special cases if we extended that to all continuations instead of just return ones. This would allow the register allocator to re-use registers as it chose without having to refetch everything from backing store (which is rather problematic for non-PMC registers). This does mean that if an N register wants to have its value change across continuations it needs to have a backing store somewhere, but even without this change things need to be fetched from backing store as the register allocator might clobber them. So this does not seem like a burden in that case, and it does seem like a win for the allocator. Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
At 4:10 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 15:54:48 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 3:39 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 15:25:24 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 3:12 PM -0500 11/16/04, Matt Fowles wrote: Dan~ On Tue, 16 Nov 2004 13:41:25 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 10:32 AM -0800 11/16/04, Jeff Clites wrote: The continuation preserves the frame (the mapping from logical variables to their values), but not the values of those variables at the time the continuation was created. This is one of the fundamental properties of continuations, but it does throw people. And it's why register contents have to be thrown away when a continuation is invoked, since the registers have values, and continuations don't preserve values. I think right here we have the crux of my failure to understand. I was/am under the impression that the continuation will restore the register frame to exactly as it was when the continuation was taken. Thus those registers which are values (I,N) will continue to have the value they had when the continuation was taken, while those registers which are pointers/references (S, P) will still point to the same place, but that data may have changed. Is this correct? No. The registers are just about the only thing that *isn't* restored. Continuations put the environment back. This includes things like the lexical pad stack, the namespace stack, the stack itself, any security credentials... basically everything that describes the environment. *Data*, on the other hand, is *not* restored. Data stays as it is. Registers are a special case of data, and they're just declared crud by fiat, since otherwise things get nasty and unpredictable. Then I am not sure what you mean by The return continuation PMC type, used to create return continuations used for call/return style programming, guarantees that registers 16-31 will be set such that the contents of those registers are identical to the content of the registers when the return continuation was Icreated. I read that as saying that registers will be restored by continuations. If that is not what it is intended to mean, could you clarify for me. Return continuations are special, basically. There are a number of specialized continuation forms, and this is one of 'em. Which makes things a bit more confusing but, well, there you go. It seems to me that it would simpilify much of the code, and reduce the number of special cases if we extended that to all continuations instead of just return ones. We could, but it would be wrong. Hell, it's arguably wrong for return continuations to do so, and it wouldn't be unreasonable to argue that I and N register contents are guaranteed crud and required refetching. I'm not particularly concerned with pressure on the register allocator, honestly -- it's a pleasant add-on, and one we will continue to do, but it's not strictly necessary. We deal with that after we get things correct. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, basic blocks, loops and register allocation
Dan~ On Tue, 16 Nov 2004 16:24:06 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: We could, but it would be wrong. Hell, it's arguably wrong for return continuations to do so, and it wouldn't be unreasonable to argue that I and N register contents are guaranteed crud and required refetching. I'm not particularly concerned with pressure on the register allocator, honestly -- it's a pleasant add-on, and one we will continue to do, but it's not strictly necessary. We deal with that after we get things correct. I can accept this, but I would like to make sure that I understand all of the represcussions of it. Thus you can consider all of the following questions (even though they will be phrased as statements). 1) After a full continuation is taken all of the registers must be considered invalid. 2) After a return continuation is taken, the registers can be trusted. 3) If someone takes a full continuation, all return continuations down the callstack must be promoted. 4) After a function call, some magic needs to happen so that the code knows whether it came back to itself via a return continuation and can trust its registers, or it came back via a full continuation and cannot trust them. Corrections welcome, Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
On Nov 14, 2004, at 3:03 AM, Leopold Toetsch wrote:
Matt Fowles [EMAIL PROTECTED] wrote:
Yes, but in the case of the continuation resuming after foo, the
continuation should restore the frame to the point where it was taken.
Thus all of the registers will be exactly as they were when the
continuation was taken (i.e. in the correct place).
Yes, but Jeff's example wasn't really reflecting the problem.
How come? (Not quibbling--just afraid I'm missing something.) It seems
that even this function body shows the problem:
a = 1
foo()
print a
b = 10
return b
It would seem (w/o continuations) that b should be able to re-use a's
register, but if it does then we'll print 10 instead of 1 the second
time.
So what to do:
1) Extending register frame size ad infinitum and never reuse a Parrot
register will definitely blow caches.
2) Generating an edge for every call to every previous calls will blow
the CFG and cause huge pressure on the register allocator. A lot of
spilling will be the result.
3) Using lexicals all over is slower (but HLL compilers will very
likely
emit code that does exactly that anyway). So the problem may not be a
real problem anyway. We just know that an optimizer can't remove the
refetch of lexicals in most of the subroutines.
It seems that, in term of cache locality, the same problem is there
with more registers v. spilling v. lexicals. That is, if you have 100
local variables whose lifetimes overlap (due to continuations), then
you need 100 distinct memory locations to (repeatedly) access.
4) Having an explicit syntax construct (call-with-current-continuation
that expresses verbatim, what's going on, like e.g. with a reserved
word placed as a label:
RESUMEABLE: x = choose(arr1)
I don't think that really helps either: If you have such a call, then
all the frames higher up the stack also can return multiple times, so
they have the behavior, even w/o the label.
On the other hand, this Ruby code really bugs me (note: $ variables
in Ruby are globals):
% cat continuation5.ruby
def strange
callcc {|continuation| $saved = continuation}
end
def outer
a = 0
strange()
a = a + 1
print a = , a, \n
a = hello
print a = , a, \n
end
outer()
$saved.call
% ruby continuation5.ruby
a = 1
a = hello
continuation5.ruby:8:in `+': failed to convert Fixnum into String
(TypeError)
from continuation5.ruby:8:in `outer'
from continuation5.ruby:14
What bugs me is that outer gets an error when the continuation is
invoked, because the second time strange() returns, a is a string
and so you can't add 1 to it. But looking at the definition of outer,
you'd expect that you could never get such an error. (Without the line
setting a to hello, you get an infinite loop, printing increasing
integers.)
JEff
Re: Continuations, basic blocks, loops and register allocation
Jeff Clites writes: On Nov 14, 2004, at 3:03 AM, Leopold Toetsch wrote: Matt Fowles [EMAIL PROTECTED] wrote: Yes, but in the case of the continuation resuming after foo, the continuation should restore the frame to the point where it was taken. Thus all of the registers will be exactly as they were when the continuation was taken (i.e. in the correct place). Yes, but Jeff's example wasn't really reflecting the problem. How come? (Not quibbling--just afraid I'm missing something.) It seems that even this function body shows the problem: a = 1 foo() print a b = 10 return b It would seem (w/o continuations) that b should be able to re-use a's register, but if it does then we'll print 10 instead of 1 the second time. It can. You can't reuse the same PMC (if you're using PMCs), but you can reuse the register. It all comes down to how the code is generated. I've done this in a project of mine, and it takes a little thought, but it works. When you take a continuation, you have to saveall before you take it, and restoreall at the point where the continuation is to resume. This is the trick I used (modulo brain code rot--I haven't written PIR in a really long time): saveall $P0 = new Continuation set_addr $P0, RESUME save $P0 restoreall restore $P0 # ... $P0 is your continuation RESUME: restoreall # ... On the other hand, this may be completely irrelavent, since I haven't been following the discussion. Luke
Re: Continuations, basic blocks, loops and register allocation
Dan Sugalski [EMAIL PROTECTED] wrote: At 5:53 PM +0100 11/13/04, Leopold Toetsch wrote: As the analysis of test errors of the new reigster allocator has shown, we have a problem WRT register allocation. This problem isn't new, but as the allocator is more efficiently reusing registers (or reusing them in a different way) it's exposed again. We don't really have that much of a problem. What we have is just something more simple -- the target of a continuation marks the start of a basic block. It is of course a new basic block. But setting the CFG correctly would need to create loops, that is an edge from all subcalls 1..n to previous subcalls 0..n-1. That could create big increases in CFG size. ... That means that we have to assume everything we don't get handed back from the function's dirty and should be refetched. I'm fine with refetching lexicals, as - you say it - the may got rebound. But what about more static languages? Or, alternately, if we declare that the top half of the register set is preserved on function call and return These are preserved anyway - as well as the lower half. Please forget the upper/lower half notion coming from old savetop times. The failing gc_13 test is not failing because the register isn't preserved. It's failing because there is no indication that this register isn't reassignable due to the loop-effect of the continuation. [ refetching lexicals/globals ] I'm perfectly fine in declaring that this is *only* legitimate in mainline code, and that code generators don't have to deal with the possibility that vtable or MMD function code has rebound names. Yes, as said I'm fine too with that. Perl/Python will do that anyway. But what about other languages? Are we forcing these to be as dynamic as the primary HLL targets? leo
Re: Continuations, basic blocks, loops and register allocation
Luke Palmer [EMAIL PROTECTED] wrote: Jeff Clites writes: a = 1 foo() print a b = 10 return b It would seem (w/o continuations) that b should be able to re-use a's register, but if it does then we'll print 10 instead of 1 the second time. It can. You can't reuse the same PMC (if you're using PMCs), but you can reuse the register. No. With the presence of a continuation the print a can be executed twice. If now Cb = 10 reuses a's register, it'll break. It all comes down to how the code is generated. I've done this in a project of mine, and it takes a little thought, but it works. When you take a continuation, you have to saveall before you take it, and restoreall at the point where the continuation is to resume. Please forget Csaveall. This was the way to go before we had register frames. This is the trick I used (modulo brain code rot--I haven't written PIR in a really long time): saveall $P0 = new Continuation set_addr $P0, RESUME save $P0 restoreall restore $P0 Sure. That's what we formerly used to do. Two memcpys á 640 bytes + 2 stack operations. The memcpys were killing performance. This isn't needed anymore. A continuation does restore the register frame. In your code above you emit all possible code to do the rigth thing. I'm proposing a much simpler syntax: RESUMABLE: foo() # code here might be executed more then once Luke leo
Re: Continuations, basic blocks, loops and register allocation
Bill Coffman [EMAIL PROTECTED] wrote: On Sun, 14 Nov 2004 17:03:33 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: We don't really have that much of a problem. What we have is just something more simple -- the target of a continuation marks the start of a basic block. That means that we have to assume everything we don't get handed back from the function's dirty and should be refetched. I tend to agree that this is not such a problem. Basically, Parrot has various control flow possibilities that were not previously considered. (1) An exception can happen in a try block, so CFG arcs need to be added from statements within the try block to the catch. I've already proposed a simple solution for the exception case: new eh, Exception_Handler set_eh eh, catch_label # try block catch_label: # catch block The try block is starting exactly at this point, where the exception handler gets pushed onto the contol stack. By connecting the Cset_eh opcode to the catch block with an edge in the CFG, we could easily prevent the reuse of registers located in front of the try block. (2) Continuations, which I don't pretend to understand, can also flow in previously unconsidered directions. Those arcs need to be added to the CFG. As said: there are no invisible continuations taken. From an HLL point of view, it's very clear what is happening. For continuations, however, it seems like those really are control flow arcs that need to be added. If analysis can trim a few of them, then that would be great, but if people are using continuations, maybe they shouldn't expect high performance, and extra register spilling may be another side effect. If you insert automatically these CFG edges you can't trim them down, there is no such analysis that could find points, where it isn't necessary. So we have the performance degradation for *all* subs, because w/o any compiler hints any subroutine invocation could act as a loop. Again - we'd get such loops: sub1() ---+ -+ ... || sub2() +-+ | ...| | sub3() ---+-+ The backward branches are going to the opcode after the invoke. You'd have to connect sub 1..n to sub 0..n-1. This are 81 loops for calling 10 subroutines in a row. This kills for sure all efforts the register allocator might take, we'll end up with spilling a lot. ~Bill leo
Re: Continuations, basic blocks, loops and register allocation
Jeff Clites [EMAIL PROTECTED] wrote: On Nov 14, 2004, at 3:03 AM, Leopold Toetsch wrote: Yes, but Jeff's example wasn't really reflecting the problem. How come? Your code didn't reuse Ca after the call. ... It seems that even this function body shows the problem: Yes, that one is reflecting it. a = 1 foo() print a b = 10 return b It would seem (w/o continuations) that b should be able to re-use a's register, but if it does then we'll print 10 instead of 1 the second time. Yep, if there is another call that uses the captured continuation of the foo() call and continues at print a. It seems that, in term of cache locality, the same problem is there with more registers v. spilling v. lexicals. Not quite. We can't extend just one register set, we'd do that for all 4 kinds. You can not easily have 64 PMC registers and just 10 INTVALs. A lexical access is just an array lookup (at least if the compiler uses the indexed addressing of lexicals). ... That is, if you have 100 local variables whose lifetimes overlap (due to continuations), then you need 100 distinct memory locations to (repeatedly) access. Sure. If the program is complex you need the storage anyway. 4) Having an explicit syntax construct (call-with-current-continuation that expresses verbatim, what's going on, like e.g. with a reserved word placed as a label: RESUMEABLE: x = choose(arr1) I don't think that really helps either: If you have such a call, then all the frames higher up the stack also can return multiple times, so they have the behavior, even w/o the label. The RESUMABLE label is of course at the invocation that might resume, somehwere up the call chain. Again: the HLL compiler (or the programmer) knows the effect of the continuation. Just the PIR code is too dumb, i.e. is lacking this information. On the other hand, this Ruby code really bugs me (note: $ variables in Ruby are globals): ... , you get an infinite loop, printing increasing integers.) Sure. With callcc you are calling the function again and again. JEff leo
Re: Continuations, basic blocks, loops and register allocation
All~ I think I may know a way around this problem. You will have to bear with me for a moment as I am not entirely used to speaking in terms of continuations (I find a similar difficulty in speaking about Math, but at least I have a commonly accepted lexicon for that ;-). The view from 10,000 feet. Full continuations do not operate on their context in place, but operate on a copy of it when invoked. The nitty gritty, consider (as provided by Jeff): a = 1 foo() print a b = 10 return b in the case where foo does not construct a full continuation an donly uses the return continuation, no extra copying is done and everything works. In the case where foo takes a full continuation and puts it in a global evil, when foo upgrades its return continuation to a full one (which happens automatically if foo or one of its children creates a full continuation of its own), all of the continuations down the tree will be marked as full. When a full continuation is invoked it *copies* its contenxt into place (thus it can be invoked multiple times and it will always have its original context). This means that invoking full continuations will have a speed hit associated with it (although that is to be expected), creatings full continuations has a smaller speed hit of marking the chain (also reasonably expected), but invoking and creating return continuations would still be cheap. Hopefully that made sense to someone other than me, Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
Matt Fowles [EMAIL PROTECTED] wrote: All~ ... When a full continuation is invoked it *copies* its contenxt into place (thus it can be invoked multiple times and it will always have its original context). If you mean by context Cstruct Parrot_Context then yes, this is what continuations are doing. But then nothing is solved. If you mean context + registers then there is another problem: returning via continuation would restore everything, including e.g. a loop-counter that keeps track of how often you loop via the continuation. A continuation isn't allowed to do that, you couldn't make any progress in that subroutine, when all register contents is restored. leo
Re: Continuations, basic blocks, loops and register allocation
On Nov 15, 2004, at 3:27 AM, Leopold Toetsch wrote: Jeff Clites [EMAIL PROTECTED] wrote: On Nov 14, 2004, at 3:03 AM, Leopold Toetsch wrote: Yes, but Jeff's example wasn't really reflecting the problem. How come? Your code didn't reuse Ca after the call. Oops. It seems that, in term of cache locality, the same problem is there with more registers v. spilling v. lexicals. Not quite. We can't extend just one register set, we'd do that for all 4 kinds. You can not easily have 64 PMC registers and just 10 INTVALs. A lexical access is just an array lookup (at least if the compiler uses the indexed addressing of lexicals). Ah. What I don't like, though, is that in the in the lexical case you have things sitting in an array, from which you need to move things back-and-forth to registers to work on them. In the more registers case, they're sitting in a quite similar array, but you can work on them directly there. Adding 2 such INTVALs is one op, instead of 4 (2 loads, 1 add, 1 store). Since the problem exists for all register types (unless HLLs only use PMCs, which is possible), then we either need 4 lexical arrays for maximum locality (so that they can be sized independently), or we need to be able to size the register frames independently for the 4 types. (I realize that currently lexicals must be PMCs, but it seems we have the same issue with other reg. types.) ... That is, if you have 100 local variables whose lifetimes overlap (due to continuations), then you need 100 distinct memory locations to (repeatedly) access. Sure. If the program is complex you need the storage anyway. But I think the real problem is that it's only due to CPS that the lifetimes are overlapping so much--that's what's biting us. (By expanding my example code, you could come up with simple code which uses 100 locals be would only need 1 register w/o continuations, and needs 100 spots with them.) It's just a pretty unfortunate price we're paying, if the feature is not extensively used. Now we're just figuring out how to survive it. 4) Having an explicit syntax construct (call-with-current-continuation that expresses verbatim, what's going on, like e.g. with a reserved word placed as a label: RESUMEABLE: x = choose(arr1) I don't think that really helps either: If you have such a call, then all the frames higher up the stack also can return multiple times, so they have the behavior, even w/o the label. The RESUMABLE label is of course at the invocation that might resume, somehwere up the call chain. Again: the HLL compiler (or the programmer) knows the effect of the continuation. Just the PIR code is too dumb, i.e. is lacking this information. Picture this call stack: main -- A -- B -- C -- D -- E The call from D to E uses the RESUMEABLE label, and E stores the resulting continuation in a global, and everything up to main returns. Then, main invokes the continuation, and we find ourselves back in D. Now, C, B, and A will return again, without any compile-time hint. On the other hand, this Ruby code really bugs me (note: $ variables in Ruby are globals): ... , you get an infinite loop, printing increasing integers.) Sure. With callcc you are calling the function again and again. I know--the infinite loop was the desired behavior (just mentioned it so that people wouldn't have to run it). What bugs me is that you can get that error, though looking at the code it should be impossible. The author of outer() might have no clue that could happen, so it's not really his bug, and the person using a continuation needs really detailed knowledge of everything in the call stack, to know if it will work. I guess that's just how it is, but it seems to mean that continuations have limited usefulness in languages with side-effects, except for very local usage (breaking out of a loop and such). JEff
Re: Continuations, basic blocks, loops and register allocation
On Mon, Nov 15, 2004 at 09:51:58AM +0100, Leopold Toetsch wrote: : Yes, as said I'm fine too with that. Perl/Python will do that anyway. : But what about other languages? Are we forcing these to be as dynamic as : the primary HLL targets? In Perl 6, any assumptions that cause inefficiency should be optional. An explicit pragma should be able to turn off such assumptions in either a lexical scope or the application as a whole. Then if some code needs the inefficiency for correct operation, it can turn it back on in a more limited scope. That's where we're headed with class finalization semantics, and it'd be nice if other optimizations were also possible based on a negotiation between the code that needs the speed and the code that needs the semantics. In the case of Perl, most code is not going to want to do hanky-panky with the caller's lexicals, and should not be punished for the crimes of the few bits of code that do. I do not mind forcing the rare code to use extra declarations so that the common code runs fast. For instance, I suppose that lexical rebinding code could be forced into predeclared subroutines rather than MMD or SD, so we can know at compilation time whether a call does funny things with $CALLER::_ and such. (In any event, no code is allowed to mess with the names in the caller's lexical symbol table unless the caller's code is in the process of being compiled.) Or maybe we can special-case $CALLER::_ without a pessimal generalization to $CALLER::foo. It'd be nice if stock Perl 6 ran blazingly with perfectly consistent and flexible semantics, but it's also important to have a knob you can turn up that says Damn the torpedoes, full speed ahead! So if you're going to assume anything, assume that all your assumptions are negotiable. :-) Larry
Re: Continuations, basic blocks, loops and register allocation
At 9:16 AM -0800 11/15/04, Larry Wall wrote: On Mon, Nov 15, 2004 at 09:51:58AM +0100, Leopold Toetsch wrote: : Yes, as said I'm fine too with that. Perl/Python will do that anyway. : But what about other languages? Are we forcing these to be as dynamic as : the primary HLL targets? In Perl 6, any assumptions that cause inefficiency should be optional. Okay, for this one if it's optional then we might as well not do it, since it'll work so rarely all it'll be is a massive source of bug reports. Why did the sub that has no idea that I'm messing with its lexical bindings only spottily and irregularly notice that I rebound them? I just don't want to go there. Compilers can assume lexicals aren't going to get rebound outside of their view. They're still going to have to deal with global rebinding. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, basic blocks, loops and register allocation
Jeff Clites [EMAIL PROTECTED] wrote: Picture this call stack: main -- A -- B -- C -- D -- E The call from D to E uses the RESUMEABLE label, and E stores the resulting continuation in a global, and everything up to main returns. Then, main invokes the continuation, and we find ourselves back in D. Now, C, B, and A will return again, without any compile-time hint. That's fine. The return is an expected operation. I don't think that's the problem. The error in gc_13 is a call path like: choose() - try (with_cc) - fail() - | (choose again) - + --+ | choose() - try (with_cc) - fail() -| || (choose again) - +| | fail() --+ The problem now is not per se the path in main from the two choose() calls down to fail is executed more then once (as it's the case with multiple returns). The problem is the loop in main. By denoting the loop from the call to fail() to the first choose() with some kind of syntax, the register allocator does the right thing. JEff leo
Re: Continuations, basic blocks, loops and register allocation
Leo~ On Mon, 15 Nov 2004 20:30:18 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: Matt Fowles wrote: Leo~ On Mon, 15 Nov 2004 17:36:20 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: Matt Fowles wrote: I do mean context + registers and it can do that. If you keep your loop-counter in a PMC, then it will be incremented Ok, but having suddenly such a difference between value and reference types would really cause weird behavior. I disagree. This is exactly the sort of distinction that has always been annoying novice programmers with most every language. Yes of course. But continue that sentence above: weird... depending on the presence of Continuation, which, by creating a loop from your code, start preserving your scalar data types. I am sorry, but I don't understand what you are trying to say here. Would you mind rewording it for me? I didn't mention the runtime impact yet. You said already that it's costy. This would make continuations unusable for backtracking in the rules/rx engine. The runtime inpact would be comparable to the speed of our previous calls where memory had to be copied off and restored (accept that we only need one of the copies instead of two). I am not saying that this is necessarily the correct solution, but it is a solution that would impose minimal breakage and would not put heavy constraints on the register allocator. One thing that worries me is the need to copy the entire callstack worth of return continuations into full ones when a continuation is created/promoted. This could be optimized for the regex case by taking an initial continuation and thereafter using its copied stack to initialize any newly taken continuations. Which gives me an evil idea. We could allow bytecode to specify that it wanted to start taking full continuations everywhere, but that these would never be used below it on the callstack. Thus the regex engine could do this and not suffer too much efficiency loss for taking new continuations for every backtrack point. Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
On Mon, 15 Nov 2004 17:19:01 -0500, Matt Fowles [EMAIL PROTECTED] wrote: Which gives me an evil idea. We could allow bytecode to specify that it wanted to start taking full continuations everywhere, but that these would never be used below it on the callstack. Thus the regex engine could do this and not suffer too much efficiency loss for taking new continuations for every backtrack point. This is not really evil - it's known as an escape continuation or weak continuation, or - more commonly - as an exception. Cheers, Michael
Re: Continuations, basic blocks, loops and register allocation
Matt Fowles [EMAIL PROTECTED] wrote: Jeff~ Yes, but in the case of the continuation resuming after foo, the continuation should restore the frame to the point where it was taken. Thus all of the registers will be exactly as they were when the continuation was taken (i.e. in the correct place). Yes, but Jeff's example wasn't really reflecting the problem. The case I've shown looks like: .local pmc arr1, arr2 arr1=[1,3,5] arr2=[1,5,9] x = choose(arr1) y = choose(arr2) # arr2 never used beyond $P0 = ... At the last line the register allocator happily reuses the register that arr2 had for $P0. That's totally legal in the absence of continuations. So it doesn't suffice that the register frame is restored and that variables are in the same place. The effect of the continuation is the creation of a loop in the CFG. Life time of variables and thus register allocation is different within loops. Exceptions handlers, on the other hand, are a different story, because anything that is used in the catch block must be kept in the correct place through out the entire try block. No they aren't really different. The presence of an exception handler (and the code for installing such a handler) is more visible in PIR. That's the only difference. But again up to the above continuation example. The scheme source of the relevant parts is this: (define (choose . all-choices) (let ((old-fail fail)) (call-with-current-continuation (lambda (continuation) ... (let ((x (choose 1 3 5)) (y (choose 1 5 9))) In that source it's obvious that the continuations of choose are captured in the local closures created by the lambda. So it's probably just a lack of the compiler (and a lack of PIR syntax) to express the relevant information that the call to choose has the possible side-effect of being resumed just after the created invokecc opcode. So from a HLL point of view that's all visible and clear. cite author=PiersAnd, damnit, making a full continuation isn't something a programmer should do lightly. /cite And of course an HLL compiler can't and doesn't emit some code that captures a continuation silently and w/o any reason. So what to do: 1) Extending register frame size ad infinitum and never reuse a Parrot register will definitely blow caches. 2) Generating an edge for every call to every previous calls will blow the CFG and cause huge pressure on the register allocator. A lot of spilling will be the result. 3) Using lexicals all over is slower (but HLL compilers will very likely emit code that does exactly that anyway). So the problem may not be a real problem anyway. We just know that an optimizer can't remove the refetch of lexicals in most of the subroutines. 4) Having an explicit syntax construct (call-with-current-continuation that expresses verbatim, what's going on, like e.g. with a reserved word placed as a label: RESUMEABLE: x = choose(arr1) leo
Re: Continuations, basic blocks, loops and register allocation
At 11:01 PM +0100 11/13/04, Leopold Toetsch wrote: Matt Fowles [EMAIL PROTECTED] wrote: I get the feeling that this is equivalent to requiring exception handlers to be a locally defined closure, which is another way we could go about this. Yes. That solves it. OTOH going all along with lexicals could be pretty inefficient. We're dealing with languages that pretty much mandate inefficiency in many ways. Since, for example, it's completely reasonable (well, likely at least) for a called sub to rebind lexicals in its parent, refetching's pretty much required. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, basic blocks, loops and register allocation
At 5:53 PM +0100 11/13/04, Leopold Toetsch wrote: As the analysis of test errors of the new reigster allocator has shown, we have a problem WRT register allocation. This problem isn't new, but as the allocator is more efficiently reusing registers (or reusing them in a different way) it's exposed again. We don't really have that much of a problem. What we have is just something more simple -- the target of a continuation marks the start of a basic block. That means that we have to assume everything we don't get handed back from the function's dirty and should be refetched. Or, alternately, if we declare that the top half of the register set is preserved on function call and return we can assume that the PMCs and values in there are acceptable for use, though any that map to lexicals or globals ought to be refetched, since we have the possibility that the names have been rebound. I'm perfectly fine in declaring that this is *only* legitimate in mainline code, and that code generators don't have to deal with the possibility that vtable or MMD function code has rebound names. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, basic blocks, loops and register allocation
On Nov 14, 2004, at 1:53 PM, Dan Sugalski wrote: Since, for example, it's completely reasonable (well, likely at least) for a called sub to rebind lexicals in its parent What does that mean, exactly? It seems like that directly contradicts the meaning of lexical. For instance, see Larry's comments from Re: Why lexical pads at September 25, 2004 10:01:42 PM PDT (the first of the 3 messages from him on that day). JEff
Re: Continuations, basic blocks, loops and register allocation
On Sun, 14 Nov 2004 17:03:33 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: At 5:53 PM +0100 11/13/04, Leopold Toetsch wrote: As the analysis of test errors of the new reigster allocator has shown, we have a problem WRT register allocation. This problem isn't new, but as the allocator is more efficiently reusing registers (or reusing them in a different way) it's exposed again. We don't really have that much of a problem. What we have is just something more simple -- the target of a continuation marks the start of a basic block. That means that we have to assume everything we don't get handed back from the function's dirty and should be refetched. I tend to agree that this is not such a problem. Basically, Parrot has various control flow possibilities that were not previously considered. (1) An exception can happen in a try block, so CFG arcs need to be added from statements within the try block to the catch. (2) Continuations, which I don't pretend to understand, can also flow in previously unconsidered directions. Those arcs need to be added to the CFG. Alternately, for exceptions, it may be possible to circumvent that process, and just add symbolic interfenence to all vars in the try block with all vars in the catch block. For continuations, however, it seems like those really are control flow arcs that need to be added. If analysis can trim a few of them, then that would be great, but if people are using continuations, maybe they shouldn't expect high performance, and extra register spilling may be another side effect. ~Bill
Re: Continuations, basic blocks, loops and register allocation
On Nov 13, 2004, at 8:53 AM, Leopold Toetsch wrote: 2) Continuations (t/op/gc_13.imc [Hi Piers]) Again we have a hidden branch done by a Continuation, or better a loop. The control flow of the main program is basically represented by this conventional code fragment: arr1=[...]; arr2=[...] loop1: x = choose(arr1) loop2: y = choose(arr2) ... failed = fail() goto (loop1, loop2)[failed] except that the gotos are performed by backtracking via the continuations. So we don't have these loop labels and the continuation continues at the next opcode after the invocation of choose() and not at the shown position above. So again, the register allocator doesn't see that there is a branch, the variable's arr2 register is clobbered, in this case by the fail closure. As we never know, if a subroutine captures the return continuation and creates such loops like above, we have in the absence of other syntax actually no chance to hold any variable in a register as far as I can see now. We'd have just to force using lexicals for all vars, except for leaf subroutines (that don't call other subs) or subs that just call one sub (they can't create loops). Another idea is to create edges from all 1..n function calls in a sub to the previos 0..n-1 calls, so that basically all possible loops done via possible continuations are represented in the CFG. That analysis looks correct to me--any time you have a function call, the subsequent op might be a branch target, if there is a subsequent function call. We'd have just to force using lexicals for all vars Having variable-size register sets would solve this, since you could have fixed assignments of variables to registers, and not have to suffer the overhead of moving data between registers and lexical pads over-and-over. Well, it doesn't really solve it--just makes it workable. JEff
Re: Continuations, basic blocks, loops and register allocation
All~ On Sat, 13 Nov 2004 10:52:38 -0800, Jeff Clites [EMAIL PROTECTED] wrote: On Nov 13, 2004, at 8:53 AM, Leopold Toetsch wrote: We'd have just to force using lexicals for all vars Having variable-size register sets would solve this, since you could have fixed assignments of variables to registers, and not have to suffer the overhead of moving data between registers and lexical pads over-and-over. Well, it doesn't really solve it--just makes it workable. I like the idea of mandating lexicals vars. This would also eliminate the need for spilling (I think), as the register allocator would only need to refetch the lexical rather than save it off somewhere to be restored later. I get the feeling that this is equivalent to requiring exception handlers to be a locally defined closure, which is another way we could go about this. Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
Matt Fowles [EMAIL PROTECTED] wrote: I like the idea of mandating lexicals vars. This would also eliminate the need for spilling (I think), as the register allocator would only need to refetch the lexical rather than save it off somewhere to be restored later. There are two issues: yes with refetch - no with store (probably). Lexicals and globals are references, so: add Plex, Px, Py stores already x+y in the variable lex. Well, that's a compiler issue and a reason to keep the current destination exists semantics of opcodes. (This usage doesn't cope with the generation of new values, though and morping Undef isn't a good solution) I get the feeling that this is equivalent to requiring exception handlers to be a locally defined closure, which is another way we could go about this. Yes. That solves it. OTOH going all along with lexicals could be pretty inefficient. Matt leo
Re: Continuations, basic blocks, loops and register allocation
On Nov 13, 2004, at 11:16 AM, Matt Fowles wrote: All~ On Sat, 13 Nov 2004 10:52:38 -0800, Jeff Clites [EMAIL PROTECTED] wrote: On Nov 13, 2004, at 8:53 AM, Leopold Toetsch wrote: We'd have just to force using lexicals for all vars Having variable-size register sets would solve this, since you could have fixed assignments of variables to registers, and not have to suffer the overhead of moving data between registers and lexical pads over-and-over. Well, it doesn't really solve it--just makes it workable. I like the idea of mandating lexicals vars. This would also eliminate the need for spilling (I think), as the register allocator would only need to refetch the lexical rather than save it off somewhere to be restored later. In a way I feel like they're both same thing, just under a different description: spilling means moving data back-and-forth between registers and some other storage, and so does using lexicals. But the only reason we have to do that sort of dance (under either description) is because we are RISC-ish: We have a limited number of registers, and calculations can only target registers (that is, you can't add 2 numbers directly in a lexical pad or other storage--they have to be moved to registers first). You don't have to move data back-and-forth if either you have an unlimited number of (preserved) registers, or you allow calculations to act directly on other memory locations. And I think this is again just two different ways of describing the same thing: you have an unlimited number of stable storage locations, and you do calculations directly from those locations. It's just that the former (unlimited preserved registers) feels cleaner, and doesn't require an explosion of op variants. That's oversimplifying a bit, but I feel like those are the core issues (stemming from the observation of Leo's that continuations in effect give all variables a lifetime that extends to their entire block, in most cases). JEff
Re: Continuations, basic blocks, loops and register allocation
Jeff~ On Sat, 13 Nov 2004 14:08:12 -0800, Jeff Clites [EMAIL PROTECTED] wrote: That's oversimplifying a bit, but I feel like those are the core issues (stemming from the observation of Leo's that continuations in effect give all variables a lifetime that extends to their entire block, in most cases). This does not give all variables extended lifetimes. It only gives variables that are used in the exception handler such a lifetime. Thus temporaries used in calculations can be safely overwritten. Perhaps we should try adding the control flow arcs to the basic block analysis and see how the allocator handles it then... Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, basic blocks, loops and register allocation
On Nov 13, 2004, at 2:46 PM, Matt Fowles wrote: On Sat, 13 Nov 2004 14:08:12 -0800, Jeff Clites [EMAIL PROTECTED] wrote: That's oversimplifying a bit, but I feel like those are the core issues (stemming from the observation of Leo's that continuations in effect give all variables a lifetime that extends to their entire block, in most cases). This does not give all variables extended lifetimes. It only gives variables that are used in the exception handler such a lifetime. Thus temporaries used in calculations can be safely overwritten. Perhaps we should try adding the control flow arcs to the basic block analysis and see how the allocator handles it then... Not all variables, but due to Leo's case (2), it should be all variables which are referenced after the first function call out of a subroutine, if there's a later function call; for instance, consider: ... foo(); a = 10; b = 12; ... use a and b bar(); ... never use a or b again c = 1; d = 2; ... use c and d baz(); ... never use c or d again zoo(); Normally, the lifetime of a and b would end at the call to bar, and that of c and d would end at the call to baz, but due to continuations, the call to zoo might resume at the op right after the call to foo (since the continuation created when calling foo may have been captured), so a,b,c,d have to persist at least until the last function call is made. We could teach the allocator about these possibilities as you mentioned, and that would give us correct program behavior, but we know a priori that we'll have much higher register pressure that you might expect, so a different overall strategy might work better. JEff
Re: Continuations, basic blocks, loops and register allocation
Jeff~ On Sat, 13 Nov 2004 17:35:02 -0800, Jeff Clites [EMAIL PROTECTED] wrote: Not all variables, but due to Leo's case (2), it should be all variables which are referenced after the first function call out of a subroutine, if there's a later function call; for instance, consider: ... foo(); a = 10; b = 12; ... use a and b bar(); ... never use a or b again c = 1; d = 2; ... use c and d baz(); ... never use c or d again zoo(); Normally, the lifetime of a and b would end at the call to bar, and that of c and d would end at the call to baz, but due to continuations, the call to zoo might resume at the op right after the call to foo (since the continuation created when calling foo may have been captured), so a,b,c,d have to persist at least until the last function call is made. Yes, but in the case of the continuation resuming after foo, the continuation should restore the frame to the point where it was taken. Thus all of the registers will be exactly as they were when the continuation was taken (i.e. in the correct place). Thus, it does not matter if we reuse a register later in the function, the continuation will restore the proper context for itself. Exceptions handlers, on the other hand, are a different story, because anything that is used in the catch block must be kept in the correct place through out the entire try block. However, the allocator will figure this out for itself if we provide it the branch information. Another reasonable option is to mandate that the exception handler starts without any preconception about the register contents and fetches everything as needed. This means that only lexicals can be used in the handler, but it is a slightly softer requirement then only lexicals everywhere. Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: Continuations, stacks, and whatnots
Dan Sugalski [EMAIL PROTECTED] writes: At 8:46 AM +0100 3/23/04, Leopold Toetsch wrote: Piers Cawley [EMAIL PROTECTED] wrote: Dan Sugalski [EMAIL PROTECTED] 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?
Re: Continuations, stacks, and whatnots
Leopold Toetsch wrote:
Matt Fowles [EMAIL PROTECTED] 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
Re: Continuations, stacks, and whatnots
At 8:46 AM +0100 3/23/04, Leopold Toetsch wrote: Piers Cawley [EMAIL PROTECTED] wrote: Dan Sugalski [EMAIL PROTECTED] 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. :) -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, stacks, and whatnots
All~ 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 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 Dan Sugalski wrote: At 12:59 AM + 3/23/04, Piers Cawley wrote: Leopold Toetsch [EMAIL PROTECTED] writes: Dan Sugalski [EMAIL PROTECTED] 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. Possibly some lexical pad stuff. (Though of that I'm less sure)
Re: Continuations, stacks, and whatnots
Matt Fowles [EMAIL PROTECTED] wrote: 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
Re: Continuations, stacks, and whatnots
Dan Sugalski [EMAIL PROTECTED] 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. 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 Climit member to protect against to many pushes and Cname for displaying error messages. leo
Re: Continuations, stacks, and whatnots
At 7:00 PM +0100 3/22/04, Leopold Toetsch wrote: Dan Sugalski [EMAIL PROTECTED] 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 Climit member to protect against to many pushes and Cname 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. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, stacks, and whatnots
Dan Sugalski [EMAIL PROTECTED] 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? leo
Re: Continuations, stacks, and whatnots
Dan Sugalski [EMAIL PROTECTED] 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=100 'new P10, .PerlInt' Time for 1M ins: 0.314813 $ parrot tools/dev/bench_op.imc --times=100 'new P10, .RetContinuation' Time for 1M ins: 1.679647 $ parrot tools/dev/bench_op.imc --times=100 '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
Re: Continuations, stacks, and whatnots
At 8:33 PM +0100 3/22/04, Leopold Toetsch wrote: Dan Sugalski [EMAIL PROTECTED] 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=100 'new P10, .PerlInt' Time for 1M ins: 0.314813 $ parrot tools/dev/bench_op.imc --times=100 '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. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, stacks, and whatnots
Leopold Toetsch [EMAIL PROTECTED] writes: Dan Sugalski [EMAIL PROTECTED] 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?
Re: Continuations, stacks, and whatnots
At 12:59 AM + 3/23/04, Piers Cawley wrote: Leopold Toetsch [EMAIL PROTECTED] writes: Dan Sugalski [EMAIL PROTECTED] 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. Possibly some lexical pad stuff. (Though of that I'm less sure) -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: Continuations, stacks, and whatnots
All~ 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 Dan Sugalski wrote: At 12:59 AM + 3/23/04, Piers Cawley wrote: Leopold Toetsch [EMAIL PROTECTED] writes: Dan Sugalski [EMAIL PROTECTED] 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. Possibly some lexical pad stuff. (Though of that I'm less sure)
Re: Continuations, stacks, and whatnots
Dan Sugalski [EMAIL PROTECTED] writes: At 12:59 AM + 3/23/04, Piers Cawley wrote: Leopold Toetsch [EMAIL PROTECTED] writes: Dan Sugalski [EMAIL PROTECTED] 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.
Re: Continuations (again)
I don't know about the continuation stuff, but you can't assume that running imc -- pasm -- exec does the same thing as imc -- exec. I ran into that before, and I don't think its going to get fixed until the new imcc lands, at which point old-school pasm might even be gone (although I don't know that I'm remembering that part right). Regards, -- Gregor On Sun, 2004-03-21 at 08:53, Piers Cawley wrote: So, I'm trying to get my head 'round parrot's continuations. It's my understanding that, at creation time, a Continuation closes over the current user stacks, control stack and lexical pad (and possibly some other stuff but those'll do for now). So, it seems to me that the following code should print Howdy, world. .sub main $P0 = new PerlUndef $P0 = Howdy, world\n save $P0 $P1 = newcont after #$P1 = new .Continuation #set_addr $P1, after invoker($P1) sub_end: .pcc_begin_return .pcc_end_return after: restore $P2 print $P2 branch sub_end .end .sub invoker .param pmc a_cont invoke a_cont .pcc_begin_return .pcc_end_return .end Except, what actually happens is: Parrot VM: PANIC: Illegal rethrow! C file src/exceptions.c, line 356 Parrot file (unknown file), line 0 Which isn't quite what I had in mind. Bizarrely, if I do: $ parrot -o howdy.pasm howdy.imc $ parrot howdy.pasm Howdy, world $ everything's fine. Weird hunh? -- Gregor Purdy[EMAIL PROTECTED] Focus Research, Inc. http://www.focusresearch.com/
Re: Continuations (again)
Piers Cawley [EMAIL PROTECTED] wrote: So, I'm trying to get my head 'round parrot's continuations. It's my understanding that, at creation time, a Continuation closes over the current user stacks, control stack and lexical pad (and possibly some other stuff but those'll do for now). Yes register stacks. Which is one problem of your code. The calling sequence has a savetop inside, which isn't in the Continuations context. I already posted an working example. Here is another one (comments indicate problems with your code: .sub main $P0 = new PerlUndef $P0 = Howdy, world\n save $P0 # create continuation inside, so that it has this in context savetop $P1 = newcont after P5 = $P1 P0 = find_global _invoker invokecc after: restoretop restore $P2 print $P2 end # end *is* needed in main .end .sub _invoker #^^ global labels have an underscore .param pmc a_cont invoke a_cont .end Weird hunh? As long as no one really can tell the semantics of Continuations, they have to be hand-crafted like above. leo
Re: Continuations (again)
Leopold Toetsch [EMAIL PROTECTED] writes: Piers Cawley [EMAIL PROTECTED] wrote: So, I'm trying to get my head 'round parrot's continuations. It's my understanding that, at creation time, a Continuation closes over the current user stacks, control stack and lexical pad (and possibly some other stuff but those'll do for now). Yes register stacks. Which is one problem of your code. The calling sequence has a savetop inside, which isn't in the Continuations context. But why do I need the savetop? I only care about the I already posted an working example. Here is another one (comments indicate problems with your code: .sub main $P0 = new PerlUndef $P0 = Howdy, world\n save $P0 # create continuation inside, so that it has this in context savetop $P1 = newcont after P5 = $P1 P0 = find_global _invoker invokecc after: restoretop restore $P2 print $P2 end # end *is* needed in main .end .sub _invoker #^^ global labels have an underscore .param pmc a_cont invoke a_cont .end Weird hunh? As long as no one really can tell the semantics of Continuations, they have to be hand-crafted like above. So why does the generated pasm work where the PIR doesn't? I can see why saving P0-2 would be a good idea, but after doesn't need any of the other registers.
Re: Continuations (again)
Piers Cawley [EMAIL PROTECTED] writes: Leopold Toetsch [EMAIL PROTECTED] writes: Piers Cawley [EMAIL PROTECTED] wrote: So, I'm trying to get my head 'round parrot's continuations. It's my understanding that, at creation time, a Continuation closes over the current user stacks, control stack and lexical pad (and possibly some other stuff but those'll do for now). Yes register stacks. Which is one problem of your code. The calling sequence has a savetop inside, which isn't in the Continuations context. But why do I need the savetop? I only care about the Oops... what happened to that sentence? Anyhoo, I looked again at the generated .pasm and noticed that P1 was getting copied up to P20 so, if you don't do the savetop you're never going to get the current continuation back. (I know, I'm telling you something you already know). It seems to me that there's a good case for saying that P1 should be closed over when a continuation is made and restored when it's invoked. Not having to manage P1 explicitly until and unless you want to promote it to a full continuation should help enormously when you're wanting to write code that does (amongst other things) tail call optimization because you know that, unless you've fiddled with it yourself, P1 is always the current continuation. (Right now you have to restore P1 from whichever hidden PMC register IMCC has hidden it in, set up the various call registers by hand, stick the sub in the right place and call it with invoke not invokecc. Since you don't actually know *where* IMCC has shoved the continuation this is a little tricky. You end up having to duplicate the work.) Dan? Could you mandate this? Please? Preserving self and the current function object could also be rather handy...
Re: Continuations (again)
Piers Cawley [EMAIL PROTECTED] wrote: [ Continuation usage ] Dan? Could you mandate this? Please? As long as there are no usage patterns that precisely describe how Continuations should work and how a PIR syntax could look like, there is little to mandate ;) Preserving self and the current function object could also be rather handy... Cself is preserved around (method only?) calls. The subroutine object currently not. This could be optional: $P0 = getprop sub_self, some# sub_self := P0 leo
Re: Continuations (again)
Piers Cawley [EMAIL PROTECTED] wrote: So why does the generated pasm work where the PIR doesn't? The generated PASM is all one compilation unit. Your (local) labels are fixed up properly. In your PIR code you had local labels (w/o) underscore refering to different compilation units. I can see why saving P0-2 would be a good idea, but after doesn't need any of the other registers. s. a different f'up. leo
Re: Continuations don't close over register stacks
Dan Sugalski [EMAIL PROTECTED] wrote: [ stack layout ] I'd rather not have the store statically inside the hunk: - small objects code currently has an upper limit for sized header pools Doesn't mean we have to use them, honestly. A separate arena for them is fine. Each sized item (a Buffer_like header of one size class) has its own arena. This isn't the problem. But the more different arenas we have, the more we have to walk during DOD. - more and differently sized pools impose negative effects on DOD times While true, we're already walking the stack frame areas, so I'm not sure it'll work out that way. Yes. But only one arena. With the register frames in place, we would have at least 2 more arenas with (1024+x) and (2048+x) bytes for x=12 currently (32-bit systems). And the question is: should we unify other stacks (Pad, User, Control) with the register frame stacks? stacks.c's implementation has additionally a stack-next pointer which keeps a spare junk against thrashing and it has a stack-limit to guard against wild running user code. leo
Re: Continuations don't close over register stacks
Picking the last entry in this thread to reply to...
Here's the scoop with register stacks, stacks in general, and continuations.
The pointers to all these stack tops *should* be part of a
continuation, the same as the registers themselves should be. When a
continuation is taken, all the frames to the top should be marked
COW, and any access to the frames should copy them.
This does have the interesting side-effect of preserving integer
and float values across continuations, while allowing string and PMC
values to fluctuate. That is, since string and PMC stack entries are
pointers, changes to their contents propagate across continuations,
while changes to ints and floats do not. This has some ramifications
for code saving loop counters and whatnot on the stack. Short (though
not all that satisfying) answer--deal with it, or use a PMC.
Stack frames should probably just be globs of stack frame entry
memory with a pobj stuck on the front, allocated in one big hunk
(with pointers fixed up on allocation), to make DODing the things
easier. That is, a stack chunk should have the structure:
struct hunk {
struct pobj header;
INTVAL used;
INTVAL avail;
struct hunk *upchain;
struct regframe RegisterFrame[FRAMES_PER_HUNK];
}
more or less. When one's allocated the pointers in the header get set
to point to the body, or whatever, with flags set appropriately.
Modifying one marked COW should just copy the whole wad to a new hunk
and adjust the header pointers as need be.
To avoid massive thrashing, we should add a frameclose op, to mark a
frame as closed and start a new one regardless of how many entries
might still be free in the frame. When the interpreter is about to do
something that'll result in a COW marking of the frame it closes the
frame off and starts a new one (though marking a topmost entry as COW
could automatically close it. There are issues there)
Also to avoid thrashing some, adding a multi-entry pop will help.
Dropping 2 or more stack entries may toss an entire COW'd frame,
avoiding the need to make a copy just for the purpose of messing
around with the used/avail counts to drop it two or three ops later.
--
Dan
--it's like this---
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
Re: Continuations don't close over register stacks
Dan Sugalski [EMAIL PROTECTED] wrote:
struct hunk {
struct pobj header;
INTVAL used;
INTVAL avail;
Only one of these is needed (and currently used: used)
struct hunk *upchain;
struct regframe RegisterFrame[FRAMES_PER_HUNK];
I'd rather not have the store statically inside the hunk:
- small objects code currently has an upper limit for sized header pools
- more and differently sized pools impose negative effects on DOD times
- it needs more code duplication
leo
Re: Continuations don't close over register stacks
At 5:47 PM +0100 1/12/04, Leopold Toetsch wrote:
Dan Sugalski [EMAIL PROTECTED] wrote:
struct hunk {
struct pobj header;
INTVAL used;
INTVAL avail;
Only one of these is needed (and currently used: used)
struct hunk *upchain;
struct regframe RegisterFrame[FRAMES_PER_HUNK];
I'd rather not have the store statically inside the hunk:
- small objects code currently has an upper limit for sized header pools
Doesn't mean we have to use them, honestly. A separate arena for them is fine.
- more and differently sized pools impose negative effects on DOD times
While true, we're already walking the stack frame areas, so I'm not
sure it'll work out that way.
- it needs more code duplication
True, unless we yank out existing special-purpose code. If stack
frame PMCs end up looking to the DOD like array PMCs, well... less
code to deal with, since we'll be using the array code that already
exists. The tradeoff is code in the allocator, but I'm not sure it'll
actually be more code, just different code.
--
Dan
--it's like this---
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
Re: Continuations don't close over register stacks
Melvin Smith [EMAIL PROTECTED] writes: At 06:37 PM 1/7/2004 -0700, Luke Palmer wrote: Leopold Toetsch writes: Jeff Clites [EMAIL PROTECTED] wrote: On Jan 7, 2004, at 1:46 AM, Leopold Toetsch wrote: That part is already answered: create a buffer_like structure. *But* again register backing stacks are *not* in the interpreter context. I don't understand what you are getting at. They are not physically part of Parrot_Interp.ctx, but it holds pointers to them, right? No, they were in the context but aren't any more. ... So, they need to be copied when the context is being duplicated. Is that your point, or are you trying to say that they are not _logically_ part of the context, or are not supposed to be? Exactly the latter: That was AFAIK a design decision, when Dan did introduce CPS. At this time register backing stacks went out of the continuation or whatelse context - IIRC did Dan commit that to CVS himself. In which case I feel obliged to contest that decision. The register backing stacks are as much a part of the current state as the program counter is. I tend to agree, but maybe Dan can explain. I looked back at the CVS history and when I put continuations in, I did originally have register stacks in the Parrot_Context (although they weren't yet garbage collected). Dan since reverted that and put them back to the top level interpreter object. I also agree. Continuations that don't save the register stacks are about as much use as a chocolate teapot. Maybe it was supposed to be a temporary reversion until GC got sorted.
Re: Continuations don't close over register stacks
On Jan 7, 2004, at 8:15 PM, Melvin Smith wrote:
Leopold Toetsch writes:
Jeff Clites [EMAIL PROTECTED] wrote:
On Jan 7, 2004, at 1:46 AM, Leopold Toetsch wrote:
Exactly the latter:
That was AFAIK a design decision, when Dan did introduce CPS. At
this
time register backing stacks went out of the continuation or
whatelse
context - IIRC did Dan commit that to CVS himself.
I tend to agree, but maybe Dan can explain. I looked back at the
CVS history and when I put continuations in, I did originally have
register stacks in the Parrot_Context (although they weren't yet
garbage collected). Dan since reverted that and put them back to
the top level interpreter object.
I think I'm just being dense, but looking at
include/parrot/interpreter.h it appears that they are in the context:
typedef struct Parrot_Context {
struct IRegChunk *int_reg_top;/* Current top chunk of int reg
stack */
struct NRegChunk *num_reg_top;/* Current top chunk of the float
reg
* stack */
struct SRegChunk *string_reg_top; /* Current top chunk of the string
* stack */
struct PRegChunk *pmc_reg_top;/* Current top chunk of the PMC
stack */
struct Stack_Chunk *pad_stack; /* Base of the lex pad stack */
struct Stack_Chunk *user_stack; /* Base of the scratch stack */
struct Stack_Chunk *control_stack; /* Base of the flow control
stack */
IntStack intstack; /* Base of the regex stack */
Buffer * warns; /* Keeps track of what warnings
* have been activated */
} parrot_context_t;
and
typedef struct Parrot_Interp {
struct IReg int_reg;
struct NReg num_reg;
struct SReg string_reg;
struct PReg pmc_reg;
struct Parrot_Context ctx; /* All the registers and stacks
that
matter when context
switching */
...
and in src/register.c we have:
void
Parrot_push_i(struct Parrot_Interp *interpreter, void *where)
{
/* Do we have any space in the current savestack? If so, memcpy
* down */
if (interpreter-ctx.int_reg_top-used FRAMES_PER_CHUNK) {
memcpy(interpreter-ctx.int_reg_top-
IRegFrame[interpreter-ctx.int_reg_top-used],
where, sizeof(struct IRegFrame));
interpreter-ctx.int_reg_top-used++;
}
...
The continuation code only saves interpreter-ctx, and not the stuff
that hangs off of it, but it seems pretty clear that the register save
stacks are attached to the interpreter context in the current sources.
So what am I missing?
JEff
Re: Continuations don't close over register stacks
Jeff Clites [EMAIL PROTECTED] wrote: I think I'm just being dense, but looking at include/parrot/interpreter.h it appears that they are in the context: Sorry, yes. They are in the context but not saved. I mixed that up with the registers themselves, which went out of the context. leo
Re: Continuations don't close over register stacks
On Jan 8, 2004, at 4:24 AM, Leopold Toetsch wrote: Jeff Clites [EMAIL PROTECTED] wrote: I think I'm just being dense, but looking at include/parrot/interpreter.h it appears that they are in the context: Sorry, yes. They are in the context but not saved. I mixed that up with the registers themselves, which went out of the context. Okay--thanks for the confirmation. So it looks like currently if a continuation is activated after the stack frame in which it was created has exited, then interpreter-ctx.int_reg_top may point to garbage (since the frame _pointers_ are inside of the saved/restored context), so we'll end up with indeterminate behavior. I don't think we have any guards against that in place. JEff
Re: Continuations don't close over register stacks
Luke Palmer [EMAIL PROTECTED] wrote:
It makes each chunk into a subclass of Buffer like so:
struct RegisterChunkBuf {
size_t used;
PObj* next;
};
That part is already answered: create a buffer_like structure.
*But* again register backing stacks are *not* in the interpreter context.
Luke
leo
Re: Continuations don't close over register stacks
On Jan 7, 2004, at 1:46 AM, Leopold Toetsch wrote:
Luke Palmer [EMAIL PROTECTED] wrote:
It makes each chunk into a subclass of Buffer like so:
struct RegisterChunkBuf {
size_t used;
PObj* next;
};
That part is already answered: create a buffer_like structure.
*But* again register backing stacks are *not* in the interpreter
context.
I don't understand what you are getting at. They are not physically
part of Parrot_Interp.ctx, but it holds pointers to them, right? So,
they need to be copied when the context is being duplicated. Is that
your point, or are you trying to say that they are not _logically_ part
of the context, or are not supposed to be?
JEff
Re: Continuations don't close over register stacks
Jeff Clites [EMAIL PROTECTED] wrote: On Jan 7, 2004, at 1:46 AM, Leopold Toetsch wrote: That part is already answered: create a buffer_like structure. *But* again register backing stacks are *not* in the interpreter context. I don't understand what you are getting at. They are not physically part of Parrot_Interp.ctx, but it holds pointers to them, right? No, they were in the context but aren't any more. ... So, they need to be copied when the context is being duplicated. Is that your point, or are you trying to say that they are not _logically_ part of the context, or are not supposed to be? Exactly the latter: That was AFAIK a design decision, when Dan did introduce CPS. At this time register backing stacks went out of the continuation or whatelse context - IIRC did Dan commit that to CVS himself. So register stacks are *not* included in any context swapping, being it a Continuation or some other context switch. That's it. JEff leo
Re: Continuations don't close over register stacks
Leopold Toetsch writes: Jeff Clites [EMAIL PROTECTED] wrote: On Jan 7, 2004, at 1:46 AM, Leopold Toetsch wrote: That part is already answered: create a buffer_like structure. *But* again register backing stacks are *not* in the interpreter context. I don't understand what you are getting at. They are not physically part of Parrot_Interp.ctx, but it holds pointers to them, right? No, they were in the context but aren't any more. ... So, they need to be copied when the context is being duplicated. Is that your point, or are you trying to say that they are not _logically_ part of the context, or are not supposed to be? Exactly the latter: That was AFAIK a design decision, when Dan did introduce CPS. At this time register backing stacks went out of the continuation or whatelse context - IIRC did Dan commit that to CVS himself. In which case I feel obliged to contest that decision. The register backing stacks are as much a part of the current state as the program counter is. I'm writing a compiler that makes heavy use of continuations for the purpose of backtracking. If the register backing stacks aren't closed over, and I am thus required to keep the state consistent myself, it is impossible to use continuations for that purpose. Indeed, it becomes impossible to use continuations for anything but simulating a control stack, which is precisely what they are designed to get around. Luke So register stacks are *not* included in any context swapping, being it a Continuation or some other context switch. That's it. JEff leo
Re: Continuations don't close over register stacks
At 06:37 PM 1/7/2004 -0700, Luke Palmer wrote: Leopold Toetsch writes: Jeff Clites [EMAIL PROTECTED] wrote: On Jan 7, 2004, at 1:46 AM, Leopold Toetsch wrote: That part is already answered: create a buffer_like structure. *But* again register backing stacks are *not* in the interpreter context. I don't understand what you are getting at. They are not physically part of Parrot_Interp.ctx, but it holds pointers to them, right? No, they were in the context but aren't any more. ... So, they need to be copied when the context is being duplicated. Is that your point, or are you trying to say that they are not _logically_ part of the context, or are not supposed to be? Exactly the latter: That was AFAIK a design decision, when Dan did introduce CPS. At this time register backing stacks went out of the continuation or whatelse context - IIRC did Dan commit that to CVS himself. In which case I feel obliged to contest that decision. The register backing stacks are as much a part of the current state as the program counter is. I tend to agree, but maybe Dan can explain. I looked back at the CVS history and when I put continuations in, I did originally have register stacks in the Parrot_Context (although they weren't yet garbage collected). Dan since reverted that and put them back to the top level interpreter object. It seems to me they should be part of the context structure or continuations become very messy and make save/restoring of register pads almost useless in combination. -Melvin
Re: Continuations don't close over register stacks
Melvin Smith writes: The downside to our implementation is in the return continuation case. The common case is to create the continuation that you plan to return with, and you already know there will be no need for copy-on-write in most cases because typically the execution path will return using that continuation, and that will then become the main execution context. The original interpreter context and all its associated stacks that existed at the time of the snapshot will usually immediately be readonly orphans as soon as you activate the return continuation (unless you saved the initial main context first). It'd be more optimal to skip marking COW altogether in certain cases. That's what the RetContinuation class does if I'm not mistaken. But RetContinuation is a bit presumptuous about what is going to be done above it. It must be guaranteed that nobody will try to use the RetContinuation as a regular continuation without first promoting it (I can see a way to make such promotion possible, described below). There are three ways I see to reduce this overhead. The first is to make the register stacks a linked list of single frames -- no chunks. We could make object pools for each of the register frame types to keep allocation quick. This would avoid copying altogether in the common case, but it wouldn't get by marking everything COW. Plus, the copying would still happen eventually (I can't think of a way to safely unmark things COW without copying), just not as much. In particular, the asymptotic complexity stays the same. The second is to move the used counter out of the chunk and into the stack structure. This way RetContinuations can be promoted into real Continuations as long as the stack frame associated with the RetContinuation has not yet exited. The last way is to keep a set of 16 flags in each chunk that mark whether a return continuation has been taken at that point, and if you try to pop beyond that point, the stack is marked COW and copied. This is effectively lazily promoting RetContinuations into real continuations. None of these seem optimal at this point, although #2 is definitely something that could be useful. Luke
Re: Continuations don't close over register stacks
At 07:53 AM 1/6/2004 -0700, Luke Palmer wrote: Aren't continuations supposed to close over the register stacks? In this code: I should hope to get 42, but instead I get no more I frames to pop. They're not very good continuations if you have to treat them just like an address stack! Currently the Copy-On-Write bit isn't being honored on the register pad stacks, so restoretop (Parrot_pop_*()) is ignoring the fact that the stack it is dealing with is a readonly copy (taken by the continuation). They are being marked, though, so its 1/2 complete. I didn't finish the continuation implementation at the time, but I had assumed someone had during my absence. (How is that for passing the blame? :) ) -Melvin
Re: Continuations don't close over register stacks
Melvin Smith wrote: At 07:53 AM 1/6/2004 -0700, Luke Palmer wrote: Aren't continuations supposed to close over the register stacks? In this code: Currently the Copy-On-Write bit isn't being honored on the register pad stacks, No. Register backing stacks are no more in the interpreter context and neither stored nor restored by the continuation. [ COWed stacks ] someone had during my absence. (How is that for passing the blame? :) ) Good. Pass it over to me :) COW copy of stacks and of other buffer-based items is still broken. These need distinct headers so that they work like COWed strings. -Melvin leo
Re: Continuations don't close over register stacks
On Jan 6, 2004, at 3:41 PM, Luke Palmer wrote:
Leopold Toetsch writes:
Good. Pass it over to me :) COW copy of stacks and of other
buffer-based
items is still broken. These need distinct headers so that they work
like COWed strings.
Alright, I've got a pretty big incomplete patch here (see, when one has
a deadline on a compiler written with the assumption of working
continuations, one can be pretty determined :-).
It makes each chunk into a subclass of Buffer like so:
struct RegisterChunkBuf {
size_t used;
PObj* next;
};
To do that properly, I think you need a pobj_t as the first struct
member, like string has:
struct parrot_string_t {
pobj_t obj;
UINTVAL bufused;
void *strstart;
UINTVAL strlen;
const ENCODING *encoding;
const CHARTYPE *type;
INTVAL language;
};
so maybe something like:
struct RegisterChunkBuf {
pobj_t obj;
UINTVAL bufused;
RegisterChunkBuf* next;
};
But also take a look at list.h and see if it's already doing what you
want to do; you may be able to do it directly.
And then, for example:
struct PRegChunkBuf {
struct RegisterChunkBuf buf;
struct PRegFrame PRegFrame[FRAMES_PER_CHUNK];
};
I want these things to be garbage collected, but DOD doesn't trace the
buffer. I can't seem to find a way to mark the frames without making
the chunks into PMCs (yuck). Is there a way to do this?
I think you'll need to add something to the root set tracing code
(probably trace_active_buffers() in src/dod.c). I'm not sure what all
of you stuff hangs off of, though.
Just some thoughts--I'm a little fuzzy on where these items are rooted.
JEff
Re: Continuations don't close over register stacks
Jeff Clites writes:
On Jan 6, 2004, at 3:41 PM, Luke Palmer wrote:
Leopold Toetsch writes:
Good. Pass it over to me :) COW copy of stacks and of other
buffer-based
items is still broken. These need distinct headers so that they work
like COWed strings.
Alright, I've got a pretty big incomplete patch here (see, when one has
a deadline on a compiler written with the assumption of working
continuations, one can be pretty determined :-).
It makes each chunk into a subclass of Buffer like so:
struct RegisterChunkBuf {
size_t used;
PObj* next;
};
To do that properly, I think you need a pobj_t as the first struct
member, like string has:
struct parrot_string_t {
pobj_t obj;
UINTVAL bufused;
void *strstart;
UINTVAL strlen;
const ENCODING *encoding;
const CHARTYPE *type;
INTVAL language;
};
Ah, no. That's how you create a new type of header. I need nothing
more than the simple buffer header. So I make a PObj and stick this
struct in its bufstart.
so maybe something like:
struct RegisterChunkBuf {
pobj_t obj;
UINTVAL bufused;
RegisterChunkBuf* next;
};
But also take a look at list.h and see if it's already doing what you
want to do; you may be able to do it directly.
And then, for example:
struct PRegChunkBuf {
struct RegisterChunkBuf buf;
struct PRegFrame PRegFrame[FRAMES_PER_CHUNK];
};
I want these things to be garbage collected, but DOD doesn't trace the
buffer. I can't seem to find a way to mark the frames without making
the chunks into PMCs (yuck). Is there a way to do this?
I think you'll need to add something to the root set tracing code
(probably trace_active_buffers() in src/dod.c). I'm not sure what all
of you stuff hangs off of, though.
Did that. That works for the main part, but continuations and
who-knows-what-else are going to be holding references to parts of
these, so I'd like to mark these automatically.
Unless... hey! You just gave me an idea. I'll make a mark_regstack
that anything that holds on to one of these has to call as part of its
mark routine. I know, it seems like a no-brainer. Mustn't have had a
brain earlier :-)
Just some thoughts--I'm a little fuzzy on where these items are rooted.
That's fine, and thanks. I learned most of these concepts earlier today
hacking on this patch...
Luke
Re: Continuations don't close over register stacks
At 04:41 PM 1/6/2004 -0700, Luke Palmer wrote: I want these things to be garbage collected, but DOD doesn't trace the buffer. I can't seem to find a way to mark the frames without making the chunks into PMCs (yuck). Is there a way to do this? I was about to answer your question when I saw your followup where you answered it yourself. Thats probably the way I would do it. A continuation can know how to mark everything it closes over, and it doesn't have to be a PMC. The brute force method is to copy the whole pad stack as soon as a register frame is pushed or popped. As long as the stack is tree based (where multiple copies of a set of frames can point to the same parent), you only need to copy the current chunk, not the whole stack, although most of the samples I ran at the time never used more than a single register pad stack chunk (I think it was 16 frames per chunk) so its probably an unnecessary short-cut, just copy all chunks. The downside to our implementation is in the return continuation case. The common case is to create the continuation that you plan to return with, and you already know there will be no need for copy-on-write in most cases because typically the execution path will return using that continuation, and that will then become the main execution context. The original interpreter context and all its associated stacks that existed at the time of the snapshot will usually immediately be readonly orphans as soon as you activate the return continuation (unless you saved the initial main context first). It'd be more optimal to skip marking COW altogether in certain cases. I think I've just confused myself so I'm sure I lost everyone. The short of it is: the general case of closing over everything and setting COW on everything for each return continuation is inefficient, because the pattern becomes: 1) Freeze continuation B (mark all stacks COW in A, stacks that B references) 2) Activate return continuation B (replaces old interpreter context/continuation A) 3) Continue execution which inevitably does stack modification and causes a COPY + CLEAR COW bit on everything in B's now private copy. B's private copy usually becomes the new permanent interpreter context, until the next continuation (C, etc.) is activated. Taking return continuations over and over has the effect of repeatedly making the main context readonly. Without reference counting (ugg) I'm not sure how else to implement continuations correctly and achieve any sort of shortcut to skip copying things. As I said to Dan when I first patched them in; hopefully someone smarter than me would come along and do it better/faster, I only care that it actually _works_, and for now, it doesn't, completely. Also, good papers on VM design with continuations seemed to be rare 2 yrs ago and I expect they still are. Now that I've taken you on a 2 mile tangent, back to the topic. I'd be happy to see your patch. -Melvin
Re: Continuations don't close over register stacks
On Jan 6, 2004, at 6:42 PM, Luke Palmer wrote:
Jeff Clites writes:
On Jan 6, 2004, at 3:41 PM, Luke Palmer wrote:
It makes each chunk into a subclass of Buffer like so:
struct RegisterChunkBuf {
size_t used;
PObj* next;
};
To do that properly, I think you need a pobj_t as the first struct
member, like string has:
struct parrot_string_t {
pobj_t obj;
UINTVAL bufused;
void *strstart;
UINTVAL strlen;
const ENCODING *encoding;
const CHARTYPE *type;
INTVAL language;
};
Ah, no. That's how you create a new type of header. I need nothing
more than the simple buffer header. So I make a PObj and stick this
struct in its bufstart.
Hmm, okay; I'm mildly confused then, but that's okay--I need to stare
at this a bit more. But if you put your struct inside the memory
pointed to by the bufstart of a simple buffer header, then I think that
compact_pool() is going to expect you to have a Buffer_Tail and such.
Since your struct is fixed-size, I would think it would make more sense
to make it a new type of header (like Stack_Chunk in stacks.h); but on
the other hand, I don't think we COW headers, and we need major COW
here. Hmm, still fuzzy.
I want these things to be garbage collected, but DOD doesn't trace
the
buffer. I can't seem to find a way to mark the frames without making
the chunks into PMCs (yuck). Is there a way to do this?
I think you'll need to add something to the root set tracing code
(probably trace_active_buffers() in src/dod.c). I'm not sure what all
of you stuff hangs off of, though.
Did that. That works for the main part, but continuations and
who-knows-what-else are going to be holding references to parts of
these, so I'd like to mark these automatically.
Yeah, I was on crack--what I said made no sense; of course these are
going to be hanging off of individual continuation PMCs, not directly
accessible from the interpreter struct, so these won't be part of the
root set.
Unless... hey! You just gave me an idea. I'll make a mark_regstack
that anything that holds on to one of these has to call as part of its
mark routine.
Yep, at least from the vtable-mark() of the Continuation PMC. I see
there's already a mark_stack() being called there (its impl. is in
src/method_util.c). That's the right spot--I should have thought of
that before.
I know, it seems like a no-brainer. Mustn't have had a brain earlier
:-)
Apparently, I didn't either! It must be going around.
JEff
Re: Coroutines, continuations, and iterators -- oh, my! (Was: Re: Continuations elified)
Damian Conway writes:
There's no second iterator. Just Cfor walking through an array.
( questions in the form of answers :-)
so :
* for impose array context for first argument and doesnt care about
nature of the array which it was given eventually as an argument .
no multiple streams -- use parallel and friends.
* parallel and friends return lazy array ( for performance
considerations ) _o_r_ for *notice* the parallel and ??? optimize
it away / dont know
for parallel(@a,@b) - ($x,$y) { ... }
* every object with next method can function as iterator ???
_o_r_ we always have to inherit from iterator class .
what about reset/rewind ???
* $fh = open myfile ;
for $fh { ... while $fh { ... } ... }
both $fh *ultimately* use *the same* method call $fh.next , but
second $fh does it explicitely , while the first -- from under the
cloth of lazy array returned by $fh.each and drived by for .
* what does it mean that for walks the array ( keeping in mind that
that array may be usual or lazy and for have to not to care )
What's the difference between a lazy array and an iterator? Is there
caching?
Yes. A lazy array is a wrapper-plus-cache around an iterator.
$fh = open file ;
@a := $fh ;
print @a[3] # 4 calls to $fh.next
print @a[0] # no calls to $fh.next
is that the meaning of ...-plus-cache
Some of questions about iterators and stuff:
1- Are iterators now considered a fundamental type?
Probably, since they're fundamental to I/O and Cfor loops.
so every class can define its own next method or inherit from
Iterator to be used as an iterator _o_r_ it ( class ) *always* have to
inherit from Iterator -- to be used as iterator ???
Naively , it seems that this is similar to booleans in perl -- no need to
inherit from special class to behave as boolean.
2a- Is there an CIterator.toArray() or C.toList() method?
Iterator::each.
2a1- The notion that Iterator.each() returns a lazy array seems a
little wierd. Isn't a lazy array just an iterator?
No. It's an array that populates itself on-demand using an iterator.
what is the difference between the arrays @a, @b , ... here
$a = Iterator.new( ... )
@a = $a.each ;
@b := $a.each ;
@c := $a ;
@d is lazy = ( 1, 2, 3 ) ;
@f is lazy = $a.each ;
Iterator: an object that returns successive values from some source
(such as an array, a filehandle, or a coroutine)
isnt it *anything* having method next ???
why do I need a special type iterator ?
thanks ,
arcadi .
Re: Continuations
Paul Johnson wrote: Is it illegal now to use quotes in qw()? Nope. Only as the very first character of a Paging Mr Cozens. ;-) It's just another instance of whitespace significance. print «\a b c»; Presumably without the backslash here too. Maybe. It depends on whether Larry decides to make « and synonyms in all contexts (in which case: no). Damian
