Lexical variables, scratchpads, closures, ...
Jerome Vouillon
Let us think a bit about the implementation of lexical variables.
Assignement
First, let us consider how to compile a variable assignement such
as:
$x = $y
where both $x and $y are lexical variables. At first, one may think
that this can be compiled simply into a register assignment:
P0 = P1
where P0 and P1 are the PMC registers standing respectively for $x
and $y.
But, I we look at the example below, we see that this will not work
in general.
sub foo {
my $x = 13;
my $y = 17;
return (sub { print "$x\n"; },
sub { $x = $y; });
}
($print, $assign) = foo();
&$assign();
&$print();
Indeed, the returned subroutines will not have access to the registers
nor to the stack frame of the subroutine "foo". This implies that
variables must be allocated in the heap.
It turns out that PMCs provide the right operations to implement
variables: we can compile
my $x = 13;
my $y = 17;
$x = $y
into
new P0, .PerlInt # Create e new integer variable ($x)
set P0, 13 # Set its value to 13
new P1, .PerlInt # Create e new integer variable ($y)
set P1, 17 # Set its value to 17
set_pmc P0, P1 # Assigns the value of $y to $x
("set" invokes the "set_integer_native" method;
"set_pmc" is not implemented yet, but is mentioned in PDD02.)
So, we should really view a PMC not as a Perl value, but
rather as a Perl variable.
:= operator
Actually, things are a bit more complicated if we take the :=
operator into account. There seems to be two ways to implement it:
- use an "alias" PMC which forward all method calls to another PMC:
the operation "$x := $y" would then turns $x into an "alias" PMC
pointing to $y;
- implement a variable not as a PMC, but as a heap-allocated pointer
to a PMC.
The first possibility is probably more efficient because we avoid
some memory allocations and indirections, but it is more complex to
implement. So I will only consider the second one.
Scratchpads
We need to allocate an area in the heap for each lexical variable.
Instead of allocating this area one variable at a time, we can
allocate a single "scratchpad" value for all variables of a block:
this is more efficient.
The compiler can keep track of the index of the variables in the
scratchpad. So, the scratchpad can be implemented as an array of
PMCs. (We will probably need some faster opcodes to access the
array: there is no need to perform a method call, nor to do any
bound checking.)
MY
To implement MY, we need to be able to access to a variable by its
name. For this, the compiler can generate statically a hash mapping
the variable name to its index in the scratchpad. Then,
MY{"foo"} will look up the index of the variable "foo" in the
hash and use the index to get the variable PMC in the scratchpad.
To access the scratchpad of an outer block, we need a way to move
from a scratchpad to its parent scratchpad. This is trivial if we
always set the field 0 of a scratchpad to point to its parent
scratchpad. Likewise, we need a statically generated linked-list of
hashes, which describe each scratchpad.
Closures
A subroutine must have access to the scratchpads of all the
englobing blocks. As the scratchpads are linked, it is sufficient
to add a pointer to the immediately englobing scratchpads to the
closure (Sub class).
Then, the exemple
sub foo {
my $x = 13;
my $y = 17;
return (sub { print "$x\n"; },
sub { $x = $y; });
}
would be compiled into
foo: # We assume the closure is in P0
# We extract the parent scratchpad from the closure and put it
# in P1
get_pad P1, P0
# We allocate a new scratchpad
new P2, .Array
# The first field of the scratchpad contain the parent scratchpad
set P2[0], P1
# We allocate the $x variable
new P3, .Int
set P3, 13
set P2[1], P3
# We allocate the $y variable
new P4, .Int
set P4, 13
set P2[2], P4
# We create the first closure
new P5, .Sub
set_code P5, sub1
set_pad P5, P2
# We create the second closure
new P6, .Sub
set_code P6, sub2
set_pad P6, P2
# We put them into an array
new P0, .Perlarray
set P0[0], P5
set P0[1], P6
# We return the array
ret
sub1: # We assume the closure is in P0
# We extract the parent scratchpad from the closure and put it
# in P1
get_pad P1, P0
# We get the $x variable and put it in P2
set P2, P1[1]
# ... we print the variable value
ret
sub1: # We assume the closure is in P0
# We extract the parent scratchpad from the closure and put it
# in P1
get_pad P1, P0
# We get the $x and $y variables
set P2, P1[1]
set P3, P1[2]
# We assign the value of $y to $x
set_pmc P2, P3
ret
Conclusion
It seems to me that to implement lexical variables, we only need to
implement the set_pmc method and to extend the Sub class so that it
contains both a code pointer and a scratchpad.
In particular, we don't need any special support for scratchpads, at
least for the moment.
What do you think?
-- Jerome
Jonathan Sillito
>
> Let us think a bit about the implementation of lexical variables.
Thanks for spelling this out in such detail.
Here is a variation based on the lexical ops (new_pad, pop_pad,
store_lex, find_lex) committed yesterday. Note that lexical pads are
stored in the Parrot_Context struct's pad_stack field (see
include/parrot/interpreter.h).
In what follows I assume that all lexicals are stored as pointers
(instance of classes/pointer.pmc?) in the pad and that each scope will
have a reference to all of the pointers it needs to know about. In other
words a each pad has a pointer to all lexical variables declared or
referenced in the scope associated with the pad. A given pointer object
may live in multiple pads.
So:
- store_lex does not change the object that is in the hash, it just
changes what the object points to,
- and find_lex does not return the (pointer) object in the hash, it
returns the object pointed to by the object in the hash.
So here is my take on a slightly simpler example:
sub foo {
my $x = 13;
return sub { print "$x\n"; };
}
$foo()
main:
new_pad # push this on the lexical stack
# some constant descriptor should also be passed
# to the new_pad op which would then know about
# the lexical variable 'x', and would create an
# associated pointer object
new P0, .Sub # gets current lexicals from interp's context
set_addr I0, foo
set P0, I0 # current hack to get the correct address in sub
pop_pad
invoke # assumes sub is in P0
# on invoke the sub pmc fixes the current
# context to have the correct lexicals
end
foo: # We assume the closure is in P0
new P1, .Int
store_lex P1, "x" # probably by number not by name but ...
# the store would then store the new int in a
# the pointer object already allocated
set P1, 13
new_pad # again a constant descriptor should be passed
# to the new_pad op which would then know about
# the lexical variable 'x', and would get a pointer
# object from the parent scope (ie would not
# allocated a new pointer)
new P0, .Sub # this would then get the correct lexical
# info from interp's context so no need for a
# set_pad op
set_addr I0, sub
set P0, I0 # current hack to get the correct address in sub
pop_pad
ret # return the sub object
sub:
# on invoke the correct lexicals are in the current scope
find_lex P1, "x" # again probably by index not name
# after this P1 holds the int pmc
# print
ret
Does that make sense?
--
Jonathan Sillito
Jerome Vouillon
> new_pad # push this on the lexical stack
> # some constant descriptor should also be passed
> # to the new_pad op which would then know about
> # the lexical variable 'x', and would create an
> # associated pointer object
Do you really need a stack?
When is the pointer object created?
> invoke # assumes sub is in P0
> # on invoke the sub pmc fixes the current
> # context to have the correct lexicals
Can you elaborate on this? What is done precisely to fix the current
context?
-- Jerome
Jonathan Sillito
> On Wed, Jul 31, 2002 at 11:40:39AM -0600, Jonathan Sillito wrote:
> > new_pad # push this on the lexical stack
> > # some constant descriptor should also be passed
> > # to the new_pad op which would then know about
> > # the lexical variable 'x', and would create an
> > # associated pointer object
>
> Do you really need a stack?
A stack is how it is currently implemented. As Melvin suggested, this
makes it easy to push an pop scopes as each block is entered and exited.
There is an example of this in examples/assembly/lexicals.pasm
Of course other approaches's are possible.
> When is the pointer object created?
This part is not implemented currently. Once there is a pad descriptor
that the assembler understands, the pointer object could be created
immediately (maybe pointing to an instance of the PerlUndef pmc?).
BTW: is anyone working on or thinking about pad descriptors right now?
>
> > invoke # assumes sub is in P0
> > # on invoke the sub pmc fixes the current
> > # context to have the correct lexicals
>
> Can you elaborate on this? What is done precisely to fix the current
> context?
This also is not implemented (unless Sean O'Rourke's recent patch does
this?) However the Sub (or Coroutine, or Continuation, or ...) PMC could
have the responsibility of putting the correct context in place before
actually jumping to the body of the sub. Melvin's code in sub.c has a
start on this, I think ...
I am kind of just thinking out loud here, but does that clear up
anything?
--
Jonathan Sillito
Melvin Smith
>Scratchpads
>
> We need to allocate an area in the heap for each lexical variable.
> Instead of allocating this area one variable at a time, we can
> allocate a single "scratchpad" value for all variables of a block:
> this is more efficient.
>
> The compiler can keep track of the index of the variables in the
> scratchpad. So, the scratchpad can be implemented as an array of
> PMCs. (We will probably need some faster opcodes to access the
> array: there is no need to perform a method call, nor to do any
> bound checking.)
That is exactly what we are doing. However, the scratchpads themselves
are kept in a data structure, currently a stack, so discarding one
scratchpad activates the previous.
>MY
>
> To implement MY, we need to be able to access to a variable by its
> name. For this, the compiler can generate statically a hash mapping
> the variable name to its index in the scratchpad. Then,
> MY{"foo"} will look up the index of the variable "foo" in the
> hash and use the index to get the variable PMC in the scratchpad.
I think this is the plan.
> To access the scratchpad of an outer block, we need a way to move
> from a scratchpad to its parent scratchpad. This is trivial if we
Currently it is as a linked-list.
>Closures
>
> A subroutine must have access to the scratchpads of all the
> englobing blocks. As the scratchpads are linked, it is sufficient
> to add a pointer to the immediately englobing scratchpads to the
> closure (Sub class).
And they need to be COW, as closures have access to their
own copies of lexicals. I asked Jonathan to reuse the stack code
I had already written because it was using the same semantics
with COW as control and user stacks.
>Conclusion
>
> It seems to me that to implement lexical variables, we only need to
> implement the set_pmc method and to extend the Sub class so that it
> contains both a code pointer and a scratchpad.
I agree with you. It can be done without special ops that we just added.
I see no reason why we can't add an op that allows you to get the
scratchpad into a Px reg and use it just as a Hash or Array. I expect
we might want to.
> In particular, we don't need any special support for scratchpads, at
> least for the moment.
>
> What do you think?
I think you have the same idea that we do. We chose to implement
the access as ops, and you prefer using a PMC Array directly. I can
at least see one advantage to the explicit ops: they don't require
a register to use them in the general case.
-Melvin
Jerome Vouillon
> At 06:25 PM 7/31/2002 +0200, Jerome Vouillon wrote:
> >Closures
> >
> > A subroutine must have access to the scratchpads of all the
> > englobing blocks. As the scratchpads are linked, it is sufficient
> > to add a pointer to the immediately englobing scratchpads to the
> > closure (Sub class).
>
> And they need to be COW, as closures have access to their
> own copies of lexicals. I asked Jonathan to reuse the stack code
> I had already written because it was using the same semantics
> with COW as control and user stacks.
I'm confused here. In Jonathan's code, the stack is COW, not the
scratchpads. If instead of using stacks you make each scratchpad
contains a pointer to its parent, there is no need to copy anything:
several scratchpads can then share the same parent.
By the way, I don't understand how you intend to implement subroutine
invocation. Are you going to push the caller scratchpad stack on a
stack and replace it by (a copy of) the callee scratchpad stack?
> We chose to implement
> the access as ops, and you prefer using a PMC Array directly. I can
> at least see one advantage to the explicit ops: they don't require
> a register to use them in the general case.
Adding special opcodes has a cost: they then need to be implemented
for all architectures supported by the JIT compiler.
But I'm especially frightened by opcodes such as new_pad. The Perl
compiler may well be able to perform more optimizations if it does not
use this opcode but rather generate specialized code. (And the JIT
compiler may then be able to generate some inlined assembly code
instead of a call to a generic C function.)
So, I would feel more comfortable trying to reuse existing opcodes for
the moment, especially as I don't think we have a clear view of the
"right" way to implement lexical variables yet. It will still be
possible to add new opcodes to improve performances when we have a
working compiler to benchmark them.
-- Jerome
Jerome Vouillon
>
> sub foo {
> my $x = 13;
> return sub { print "$x\n"; };
> }
>
> $foo()
Melvin, I think it would really help if you could explain us how you
would compile this code. Also, you should describe precisely what
"invoke" and "new_pad" (and maybe the other scratchpad-related
opcodes) do as far as scratchpads are concerned.
-- Jerome
Melvin Smith
>On Wed, Jul 31, 2002 at 11:22:56PM -0400, Melvin Smith wrote:
>> At 06:25 PM 7/31/2002 +0200, Jerome Vouillon wrote:
>> >Closures
>> >
>> > A subroutine must have access to the scratchpads of all the
>> > englobing blocks. As the scratchpads are linked, it is sufficient
>> > to add a pointer to the immediately englobing scratchpads to the
>> > closure (Sub class).
>>
>> And they need to be COW, as closures have access to their
>> own copies of lexicals. I asked Jonathan to reuse the stack code
>> I had already written because it was using the same semantics
>> with COW as control and user stacks.
>
>I'm confused here. In Jonathan's code, the stack is COW, not the
>scratchpads. If instead of using stacks you make each scratchpad
>contains a pointer to its parent, there is no need to copy anything:
>several scratchpads can then share the same parent.
1) Our stacks are being reworked to be tree-based, so multiple children
can point to the same parent.
>By the way, I don't understand how you intend to implement subroutine
>invocation. Are you going to push the caller scratchpad stack on a
Neither do I, really. :(
-Melvin Smith
IBM :: Atlanta Innovation Center
mel...@us.ibm.com :: 770-835-6984
Sean O'Rourke
> > > invoke # assumes sub is in P0
> > > # on invoke the sub pmc fixes the current
> > > # context to have the correct lexicals
> >
> > Can you elaborate on this? What is done precisely to fix the current
> > context?
>
> This also is not implemented (unless Sean O'Rourke's recent patch does
> this?) However the Sub (or Coroutine, or Continuation, or ...) PMC could
> have the responsibility of putting the correct context in place before
> actually jumping to the body of the sub. Melvin's code in sub.c has a
> start on this, I think ...
Melvin did have stubs in place to do this, and I've played with it a bit.
The version on the list does not do this, however.
/s
Sean O'Rourke
> On Wed, Jul 31, 2002 at 11:22:56PM -0400, Melvin Smith wrote:
> > We chose to implement
> > the access as ops, and you prefer using a PMC Array directly. I can
> > at least see one advantage to the explicit ops: they don't require
> > a register to use them in the general case.
>
> [snip]
>
> But I'm especially frightened by opcodes such as new_pad. The Perl
> compiler may well be able to perform more optimizations if it does not
> use this opcode but rather generate specialized code.
Putting my "amateur compiler writer" hat on for a moment, I'll have to
agree for a couple of reasons. First, supporting Perl 6's introspective
features (e.g. %MY) is much easier if the internals and language
implementation use the same data structures where practical. Sure, it's
possible to write some glue code to make a stack act like a PerlArray, but
it's more work, and in this case I'm not sure it's necessary. There is
the unfortunate fact that all of a sudden the lexical implementation will
be tied to a particular language's PMC's, but this seems like another
reason to push lexicals out of the interpreter core.
Second, I've been playing with implementing lexicals "the right way" in
P6C, and haven't really found new_pad and pop_pad all that useful. Of
course, I don't have a working implementation yet, and I may be completely
misunderstanding how the ops should be used. I suspect that getting them
to "do the right thing" would involve adding lex-playing-with code to bsr
and ret, plus maybe a couple more ops. Plus adding more ops to push
lexical stacks onto the lexical stack-stack (for your Befunge fans ;).
> So, I would feel more comfortable trying to reuse existing opcodes for
> the moment, especially as I don't think we have a clear view of the
> "right" way to implement lexical variables yet.
My naive implementation would have an array of hashes for each sub, with
one entry for each level of scope within. This is just like the
pad_stack, but implemented using only language features. (Dynamic)
lexical lookup works its way through this stack. Static lookups can
probably be resolved to registers, with code inserted to fetch values out
of the pad the first time they are used, and store them back when a scope
is exited.
Returning a closure would make a copy of the scope array, containing
references to the pad hashes (here's where GC makes me happy, and where I
may make the GC unhappy). So the Sub PMC has a code pointer and a scope
stack pointer, which is either set up automatically when creating a new
Sub, or is accessible as a method.
Another alternative would be single-level pads for each scope containing
all accessible lexicals. Unfortunately, I think %OUTER and %MY make this
very complicated (or impossible) to get right.
Waving my hands somewhat more quickly, as an optimization, lexicals can
just live in registers when the compiler sees no references to %MY or
closures. Nastiness like eval and caller.MY can be handled by inserting
fixup code to reconstruct the lexical array on demand.
Hopefully I can get some of this working soon, and put it up on the list
for people to play with and improve.
/s
Sean O'Rourke
> Jerome Vouillon writes:
> >On Wed, Jul 31, 2002 at 11:22:56PM -0400, Melvin Smith wrote:
> >> And they need to be COW, as closures have access to their
> >> own copies of lexicals. I asked Jonathan to reuse the stack code
> >> I had already written because it was using the same semantics
> >> with COW as control and user stacks.
> >
> >I'm confused here. In Jonathan's code, the stack is COW, not the
> >scratchpads. If instead of using stacks you make each scratchpad
> >contains a pointer to its parent, there is no need to copy anything:
> >several scratchpads can then share the same parent.
>
> 1) Our stacks are being reworked to be tree-based, so multiple children
> can point to the same parent.
COW is a win when you may be able to avoid copying large amounts of data.
In a world of 4-character indents and 80-column editor windows, I'm not
sure the extra machinery of COW is a win -- an immediate copy of a stack 3
or 4 deep will be fast, and won't take much memory.
/s
Dan Sugalski
>>Conclusion
>>
>> It seems to me that to implement lexical variables, we only need to
>> implement the set_pmc method and to extend the Sub class so that it
>> contains both a code pointer and a scratchpad.
>
>I agree with you. It can be done without special ops that we just added.
>I see no reason why we can't add an op that allows you to get the
>scratchpad into a Px reg and use it just as a Hash or Array. I expect
>we might want to.
I'd rather keep the separate interface to lexicals and globals.
That'll make it much easier to change the implementation without
breaking existing bytecode.
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Jerome Vouillon
> My naive implementation would have an array of hashes for each sub, with
> one entry for each level of scope within.
I would use an array of arrays or a linked-list of arrays. This is
hardly more difficult to implement (you just need to keep track of the
variable indices during compilation) and the generated code will be a
lot more efficient.
> This is just like the
> pad_stack, but implemented using only language features. (Dynamic)
> lexical lookup works its way through this stack. Static lookups can
> probably be resolved to registers, with code inserted to fetch values out
> of the pad the first time they are used, and store them back when a scope
> is exited.
You would probably need to store them back each time you perform a
function call. I think it is good enough for the moment to always go
through the stack.
> Returning a closure would make a copy of the scope array, containing
> references to the pad hashes (here's where GC makes me happy, and where I
> may make the GC unhappy).
You don't need to make a copy at this point. Instead, the copy should
happen each time you enter a block containing lexical variables. (You
should also allocate and fill a new pad at this time.)
> Waving my hands somewhat more quickly, as an optimization, lexicals can
> just live in registers when the compiler sees no references to %MY or
> closures. Nastiness like eval and caller.MY can be handled by inserting
> fixup code to reconstruct the lexical array on demand.
caller.MY is especially nasty because you have to pay for it even when
you don't use it: you can't know whether a function has to support it
just by looking at the function code. It will be really tricky to
implement any optimization if one can write things like:
caller(1).MY{'$y'} := $x
-- Jerome
Nicholas Clark
> On Thu, Aug 01, 2002 at 10:57:34AM -0700, Sean O'Rourke wrote:
> > My naive implementation would have an array of hashes for each sub, with
> > one entry for each level of scope within.
>
> I would use an array of arrays or a linked-list of arrays. This is
> hardly more difficult to implement (you just need to keep track of the
> variable indices during compilation) and the generated code will be a
> lot more efficient.
Sorry if I've got confused and missed a bit, but if anyone is able to
eval new code in your scope, then you'll also have to keep the mapping of
variable names to array indexes somewhere. Although I agree that numeric
lookup in the generated code ought to be much much faster.
> > Waving my hands somewhat more quickly, as an optimization, lexicals can
> > just live in registers when the compiler sees no references to %MY or
> > closures. Nastiness like eval and caller.MY can be handled by inserting
> > fixup code to reconstruct the lexical array on demand.
>
> caller.MY is especially nasty because you have to pay for it even when
> you don't use it: you can't know whether a function has to support it
> just by looking at the function code. It will be really tricky to
> implement any optimization if one can write things like:
> caller(1).MY{'$y'} := $x
You can't know whether a function has to support it by looking at all the
bytecode in the interpreter at any given time. Some "nasty" programmer only
needs to dynamicly load a library that goes up from its scope into yours and
your careful check is worthless.
Nicholas Clark
Sean O'Rourke
> On Thu, Aug 01, 2002 at 10:57:34AM -0700, Sean O'Rourke wrote:
> > My naive implementation would have an array of hashes for each sub, with
> > one entry for each level of scope within.
>
> I would use an array of arrays or a linked-list of arrays. This is
> hardly more difficult to implement (you just need to keep track of the
> variable indices during compilation) and the generated code will be a
> lot more efficient.
I don't see how you can cope with '%MY' unless you have a hash. You could
have a hash in addition to the array, I suppose. In any case, Dan has
promised us some sort of indexed "back-door" access to our hashes, so I
get the feeling the point is moot -- hashes will be arrays in some sense.
> > This is just like the
> > pad_stack, but implemented using only language features. (Dynamic)
> > lexical lookup works its way through this stack. Static lookups can
> > probably be resolved to registers, with code inserted to fetch values out
> > of the pad the first time they are used, and store them back when a scope
> > is exited.
>
> You would probably need to store them back each time you perform a
> function call.
You're right.
> I think it is good enough for the moment to always go through the
> stack.
Without performance numbers, this is hard to test, but it can potentially
turn a single "a = b + c", which is just "add P0, P1, P2" if a, b, and c
have been referenced, into a hideous five instructions:
fetch_lex P0, 'a' # Because how we store result depends on a's type
fetch_lex P1, 'b'
fetch_lex P2, 'c'
add P0, P1, P2
store_lex P0, 'a'
> > Returning a closure would make a copy of the scope array, containing
> > references to the pad hashes (here's where GC makes me happy, and where I
> > may make the GC unhappy).
>
> You don't need to make a copy at this point. Instead, the copy should
> happen each time you enter a block containing lexical variables. (You
> should also allocate and fill a new pad at this time.)
Making a copy on every scope entry would solve the problem (the Befunge
stack-stack metaphor grows stronger!), but I was hoping we could do
better, since most lexical scopes won't be creating closures. The more I
think about it, though, the more complicated that gets. And actually,
thanks to %MY and caller.MY, we need a new pad even for scopes without
lexicals, since they can be inserted later.
> > Waving my hands somewhat more quickly, as an optimization, lexicals can
> > just live in registers when the compiler sees no references to %MY or
> > closures. Nastiness like eval and caller.MY can be handled by inserting
> > fixup code to reconstruct the lexical array on demand.
>
> caller.MY is especially nasty because you have to pay for it even when
> you don't use it: you can't know whether a function has to support it
> just by looking at the function code. It will be really tricky to
> implement any optimization if one can write things like:
> caller(1).MY{'$y'} := $x
Yes. Not impossible, I think, but more likely just tricky enough that we
never get around to it.
/s
Jerome Vouillon
> On Fri, 2 Aug 2002, Jerome Vouillon wrote:
>
> > On Thu, Aug 01, 2002 at 10:57:34AM -0700, Sean O'Rourke wrote:
> > > My naive implementation would have an array of hashes for each sub, with
> > > one entry for each level of scope within.
> >
> > I would use an array of arrays or a linked-list of arrays. This is
> > hardly more difficult to implement (you just need to keep track of the
> > variable indices during compilation) and the generated code will be a
> > lot more efficient.
>
> I don't see how you can cope with '%MY' unless you have a hash. You could
> have a hash in addition to the array, I suppose.
Sure, you need a hash. But this can be a statically allocated hash,
mapping variable names to indices.
> In any case, Dan has
> promised us some sort of indexed "back-door" access to our hashes, so I
> get the feeling the point is moot -- hashes will be arrays in some sense.
Allocating a hash will certainly remain a lot more expensive than
allocating an array. And we are going to allocate pads pretty
often...
> > > This is just like the
> > > pad_stack, but implemented using only language features. (Dynamic)
> > > lexical lookup works its way through this stack. Static lookups can
> > > probably be resolved to registers, with code inserted to fetch values out
> > > of the pad the first time they are used, and store them back when a scope
> > > is exited.
>
> > I think it is good enough for the moment to always go through the
> > stack.
>
> Without performance numbers, this is hard to test, but it can potentially
> turn a single "a = b + c", which is just "add P0, P1, P2" if a, b, and c
> have been referenced, into a hideous five instructions:
>
> fetch_lex P0, 'a' # Because how we store result depends on a's type
> fetch_lex P1, 'b'
> fetch_lex P2, 'c'
> add P0, P1, P2
> store_lex P0, 'a'
Sure, but this seems to be a non-trivial optimization (I may be
wrong). I think we should implement a larger part of the language
first.
By the way, the code should probably be:
fetch_lex P0, 'a' # Get the PMC of variable 'a'
fetch_lex P1, 'b' # Get the PMC of variable 'b'
fetch_lex P2, 'c' # Get the PMC of variable 'c'
add P0, P1, P2 # Add the values contained in the PMC of 'b' and 'c'
and store them in the PMC of 'a'
The opcode store_lex is only needed for the operator := (and maybe for
variable initialization).
> > > Returning a closure would make a copy of the scope array, containing
> > > references to the pad hashes (here's where GC makes me happy, and where I
> > > may make the GC unhappy).
> >
> > You don't need to make a copy at this point. Instead, the copy should
> > happen each time you enter a block containing lexical variables. (You
> > should also allocate and fill a new pad at this time.)
>
> Making a copy on every scope entry would solve the problem (the Befunge
> stack-stack metaphor grows stronger!), but I was hoping we could do
> better, since most lexical scopes won't be creating closures. The more I
> think about it, though, the more complicated that gets.
Note that when you have a loop you need to allocate some fresh lexical
variables at each iteration (so, you need to create a new pad each
time). Furthermore, you can create loops with callcc, so the piece of
code below could be a loop, if the function foo captures the current
continuation and the function bar resumes it.
foo();
do { my $x = ... }
bar();
> And actually, thanks to %MY and caller.MY, we need a new pad even
> for scopes without lexicals, since they can be inserted later.
I really hope %MY and caller.MY will not be able to extend the lexical
scope: we would get a really huge speed penalty for a feature which
would hardly ever be used.
-- Jerome
Melvin Smith
>Without performance numbers, this is hard to test, but it can potentially
>turn a single "a = b + c", which is just "add P0, P1, P2" if a, b, and c
>have been referenced, into a hideous five instructions:
>
> fetch_lex P0, 'a' # Because how we store result depends on a's type
> fetch_lex P1, 'b'
> fetch_lex P2, 'c'
> add P0, P1, P2
> store_lex P0, 'a'
The last instruction (store_lex) isn't needed since P0 is a pointer to the
lexical.
-Melvin
Sean O'Rourke
You are correct, sir. Though interestingly enough, you do need a
store_lex (and not a fetch_lex) for "a" in "a = b", at least until we have
an assign op.
/s
Melvin Smith
>Melvin, I think it would really help if you could explain us how you
>would compile this code. Also, you should describe precisely what
>"invoke" and "new_pad" (and maybe the other scratchpad-related
>opcodes) do as far as scratchpads are concerned.
I'll try to do this as soon as I can get time to think about it again, if I
can still add value to the thread.
-Melvin
Jonathan Sillito
> Sure, you need a hash. But this can be a statically allocated hash,
> mapping variable names to indices.
Could two parallel arrays work? One stores the lexicals (accessed by
index) and the other stores the names of the lexicals. Then to access a
lexical by name involves a sequential search through the (probably not
large) array of names, to get the index, then the index is used to get
the lexical from the other array.
Or would that make access by name too slow?
--
Jonathan Sillito
Dave Mitchell
> Could two parallel arrays work? One stores the lexicals (accessed by
> index) and the other stores the names of the lexicals. Then to access a
> lexical by name involves a sequential search through the (probably not
> large) array of names, to get the index, then the index is used to get
> the lexical from the other array.
>
> Or would that make access by name too slow?
It's how Perl5 does it (very roughly speaking)
--
"You're so sadly neglected, and often ignored.
A poor second to Belgium, When going abroad."
Monty Python - "Finland"
Nicholas Clark
> On Fri, Aug 02, 2002 at 08:50:27AM -0700, Sean O'Rourke wrote:
> > I don't see how you can cope with '%MY' unless you have a hash. You could
> > have a hash in addition to the array, I suppose.
>
> Sure, you need a hash. But this can be a statically allocated hash,
> mapping variable names to indices.
Which probably still works even with %MY - providing we have some way that the
pad is pointing to the static version, until something run time fiddles with
our scope, at which point we copy it to a dynamic version, and from then on
that lexical scope is dynamic.
(and only then is it slower)
We don't have to even have much of a hit of following the pointer if a
static structure looks like this
struct pad {
struct runtime_pad *in_use_pad;
struct runtime pad {
...
} default_static_pad;
};
where default_static_pad is the compile-time job, and in_use_pad points to it
until %MY is written to.
> > In any case, Dan has
> > promised us some sort of indexed "back-door" access to our hashes, so I
> > get the feeling the point is moot -- hashes will be arrays in some sense.
>
> Allocating a hash will certainly remain a lot more expensive than
> allocating an array. And we are going to allocate pads pretty
> often...
Are we? Or are we just going to copy them a lot at runtime?
[but actually allocate the beasts only at compile time, or when someone
mucks around with them using string eval or %MY]
> > And actually, thanks to %MY and caller.MY, we need a new pad even
> > for scopes without lexicals, since they can be inserted later.
>
> I really hope %MY and caller.MY will not be able to extend the lexical
> scope: we would get a really huge speed penalty for a feature which
> would hardly ever be used.
I think we need to be aware of this, but I don't think it has to be that
painful. If all scopes have a pad pointer, but lexical-free scopes start
with it null, then there won't be a really huge speed penalty.
[it might actually be faster, as this way all pads *are* equal, so there
doesn't need to be special case code distinguishing between scopes with
lexicals and scopes without.]
Nicholas Clark
--
Even better than the real thing: http://nms-cgi.sourceforge.net/
Melvin Smith
Here is an attempt. I'm assuming the stack of pads is a singly-linked list
of pads with children pointing to parents, and multiple children can refer
to the same parent. If they are created on the fly, the creation of
a Sub or Closure will simply hold a pointer to its parent, and pads will
be garbage collected.
Disclaimer: I'm only speaking my ideas which may not coincide with
what Dan has in mind.
# Assuming we have no symbol table or pad "descriptor"
# then to do it dynamically with the new_pad/store_lex ops...
foo:
new_pad # lexical scope 1
new P0, .PerlInt
set P0, 13
store_lex "$x", P0 # or store_lex 0, P0
new P1, .PerlSub # captures the current lexical pad tree/stack
set P1, anon_closure # set bytecode address
store P1 # return value
ret # ret may close current pad which now is only
# referred to by anon_closure
anon_closure:
new_pad # activate new pad which inherits previous pad
# for any lexicals.
# lexical scope 2
fetch_lex P0, "$x" # or fetch_lex P0, 0
print P0
print "\n"
ret
new P0, .PerlSub, foo # lexical scope 0
invoke P0
restore P1 # get closure sub returned from foo into P1
invoke P1 # closure contains a lexical stack of: [0,1]
and will
# push lex scope 2 which in this example
doesn't
# create any new lexicals.
end
Simon Cozens
> > Or would that make access by name too slow?
> It's how Perl5 does it (very roughly speaking)
This is a reminder that people new to developing VMs may find it useful
to leaf through http://www.netthink.co.uk/downloads/internals.pdf and
http://www.netthink.co.uk/downloads/internals for the Perl 5 internals
tutorial; there's stuff on lexical variables there, for instance.
--
You want to read that stuff, fine. You want to create a network for such
things, fine. You want to explore the theoretical boundaries of free speech,
fine. But when it starts impacting *people* trying to *communicate*, then
that is where I draw the line. - Russ Allbery, http://www.slacker.com/rant.html
Jerome Vouillon
> On Fri, Aug 02, 2002 at 06:43:49PM +0200, Jerome Vouillon wrote:
> > Allocating a hash will certainly remain a lot more expensive than
> > allocating an array. And we are going to allocate pads pretty
> > often...
>
> Are we? Or are we just going to copy them a lot at runtime?
> [but actually allocate the beasts only at compile time, or when someone
> mucks around with them using string eval or %MY]
When we enter a block we need to:
- create a new pad
- copy the current pad array and add the new pad to the copy
- allocate a PMC for each lexical variable introduced in the block and
insert the PMCs in the new pad
The creation of the pad could be done either by copying a template
pad. This would not make any difference compared to allocating from
scratch for an array, but this must be faster for a hash. Still, I
think using an array will remain faster.
> > I really hope %MY and caller.MY will not be able to extend the lexical
> > scope: we would get a really huge speed penalty for a feature which
> > would hardly ever be used.
>
> I think we need to be aware of this, but I don't think it has to be that
> painful. If all scopes have a pad pointer, but lexical-free scopes start
> with it null, then there won't be a really huge speed penalty.
> [it might actually be faster, as this way all pads *are* equal, so there
> doesn't need to be special case code distinguishing between scopes with
> lexicals and scopes without.]
I think this make a large difference for variable access. Here is a
comparison.
Consider the following example:
$x = 1;
my $y = 1;
sub foo () {
bar ();
print "$x $y\n";
}
We consider the two possibilities:
* The lexical scopes cannot be extended
We can implement the lexical scopes with an array of arrays. For this
example, we don't need to allocate a pad for the subroutine foo, as it
has no lexical variable. So, in subroutine foo, the layout of the
lexical scopes is the following :
outer
array pad
+--+ +--+
| -+--->| -+--> $y PMC
+--+ +--+
So, accessing the $y variable require 5 memory reads (5 assembly
instructions on a i386 machine):
- one read to get the address of the outer array from a parrot register
- two reads to get the address of the pad
- two reads to get the address of the PMC.
This could be further improved:
- the address of the outer array could probably be placed in a machine
register, which would save one memory read
- we may be able to save one memory read per array look-up if we can
avoid wrapping them in a PMC.
This would get us down to 2 memory reads.
On architectures which are not register starved (about anything but
the i386 architecture), it may be worthwhile to store some of the pad
addresses in machine register: this would save yet another memory
read.
I believe accessing a global variable such as $y can be made hardly
more costly: just one ore two more memory reads. In particular, we
can avoid a hash look-up.
* The lexical scopes can be extended
I think we need to implement pads as hashes, not arrays, in this case.
Also, we need a pad even for blocks that does not introduce any
lexical variable, because a variable may be inserted latter. So, for
the example, the layout of the lexical scopes looks like:
Pads
(hashes)
+--+ +--+
| -+--->| | (empty pad for subroutine foo)
+--+ +--+
| -+-
+--+ \ +--+
->| -+--> $y PMC
+--+
Now, if we want to access $y, we first need to perform a look-up in
the first pad, usually empty, but which may contain a lexical variable
$y if bar is defined as:
sub bar () {
caller.MY{$y} = 2;
}
Then, if this fails, we perform a look-up in the outer scope.
Most of the time, lexical variables will be defined in one of the
first pads, so I think we can expect the cost of accessing a lexical
variable to be around one or two hash lookup. This is already a lot
more costly than a few memory reads.
For global variables ($x and &print in this example), I think this is
worse: we must look into all the hashes, just in case they become
shadowed by a lexical variable, for instance if bar is defined as:
sub bar () {
caller.MY{$x} = 2;
}
or as:
sub bar () {
caller.OUTER.MY{$x} = 2;
}
-- Jerome
Jerome Vouillon
> Here is an attempt. I'm assuming the stack of pads is a singly-linked list
> of pads with children pointing to parents, and multiple children can refer
> to the same parent. If they are created on the fly, the creation of
> a Sub or Closure will simply hold a pointer to its parent, and pads will
> be garbage collected.
This should work. I think you still need a "real" stack of pads. The
opcode "new_pad" creates a new pad whose parent is the top of the
stack, and replace this parent by the new pad in the stack. The opcode
"invoke" push the subrouting pad onto the stack. The opcode "ret" pop
the top of the stack.
-- Jerome
Dan Sugalski
> > Waving my hands somewhat more quickly, as an optimization, lexicals can
>> just live in registers when the compiler sees no references to %MY or
>> closures. Nastiness like eval and caller.MY can be handled by inserting
>> fixup code to reconstruct the lexical array on demand.
>
>caller.MY is especially nasty because you have to pay for it even when
>you don't use it: you can't know whether a function has to support it
>just by looking at the function code. It will be really tricky to
>implement any optimization if one can write things like:
> caller(1).MY{'$y'} := $x
Please note that, regardless of what this sort of thing gets in the
way of, it'll *still* be as fast or faster than perl 5. Which is the
ultimate goal, the rest being a bit of a bonus.
Jerome Vouillon
> Copying the entire stack doesn't sound that good an idea since you
> want code like the following to work.
>
> {
> my $invocation_count = 0;
> sub counter_maker {
> my $base = shift || 0;
> return sub { $invocation_count++; return ++$base }
> }
> sub invocations { $invocation_count }
> }
It will work, because only the stack is copied, not its contents. So,
both the pads and the PMCs will remain shared.
So, the first block will use the stack 1 below, and the first
invocation of subroutine counter_maker will use the stack 2 (each
invocation of this subroutine creates a new stack, together with a pad
and a PMC for the lexical variable $base). The anonymous subroutine
does not need to copy the stack 2 and can use it directly. Likewise,
the subroutine "invocation" can use stack (1) directly.
stacks pads PMCs
+-+ +-+ +-+
(1) -->| |------>| |------>| |---> 0 ($invocation_count)
+-+ -->+-+ +-+
/
+-+ /
(2) -->| |--
+-+ +-+ +-+
| |------>| |------>| |---> 10 ($base)
+-+ +-+ +-+
The expression "$invocation_count++;" increments the value of the
shared PMC, so the subroutine "invocations" will return the new value.
-- Jerome
pdca...@bofh.org.uk
Copying the entire stack doesn't sound that good an idea since you
want code like the following to work.
{
my $invocation_count = 0;
sub counter_maker {
my $base = shift || 0;
return sub { $invocation_count++; return ++$base }
}
sub invocations { $invocation_count }
}
$counter_a = counter_maker(10);
$counter_b = counter_maker(0);
print $counter_a.(); # prints 11
print $counter_b.(); # prints 1
print invocations(); # print 2.
Copy on Write sounds a little scary too, to be honest. I rather think
we should be very careful about copy on write of anything but strings...
--
Piers
"It is a truth universally acknowledged that a language in
possession of a rich syntax must be in need of a rewrite."
-- Jane Austen?
Melvin Smith
>"Sean O'Rourke" <soro...@cs.ucsd.edu> writes:
>
> > On Thu, 1 Aug 2002, Melvin Smith wrote:
> >
> > > Jerome Vouillon writes:
> > > >On Wed, Jul 31, 2002 at 11:22:56PM -0400, Melvin Smith wrote:
> > > >> And they need to be COW, as closures have access to their
> > > >> own copies of lexicals. I asked Jonathan to reuse the stack code
> > > >> I had already written because it was using the same semantics
> > > >> with COW as control and user stacks.
> > > >
> > > >I'm confused here. In Jonathan's code, the stack is COW, not the
> > > >scratchpads. If instead of using stacks you make each scratchpad
> > > >contains a pointer to its parent, there is no need to copy anything:
> > > >several scratchpads can then share the same parent.
> > >
> > > 1) Our stacks are being reworked to be tree-based, so multiple children
> > > can point to the same parent.
> >
> > COW is a win when you may be able to avoid copying large amounts of data.
> > In a world of 4-character indents and 80-column editor windows, I'm not
> > sure the extra machinery of COW is a win -- an immediate copy of a stack 3
> > or 4 deep will be fast, and won't take much memory.
>
>Copying the entire stack doesn't sound that good an idea since you
>want code like the following to work.
Firstly, I think I mispoke about closures. Since we allocate pads on the fly,
there is no need for any copy-on-write magic, at the point of taking a closure,
we will usually be on a privately referenced stack frame anyway, so
we can just save it without COW flags.
Closures and continuations should all work together with the current hack.
>Copy on Write sounds a little scary too, to be honest. I rather think
>we should be very careful about copy on write of anything but strings...
Well, I won't argue, since it was my first time implementing continuations,
however the literature I read indicates that many other implementations
use the same method. I'm open to discussions about other methods
of capturing them, though.
-Melvin
Dan Sugalski
COW is the way to go here, definitely. We can do two-level COW for
extra efficiency. (Copying the stack chunk header and the stack chunk
separately) Otherwise things get a bit dicey.