On Fri, Aug 02, 2002 at 09:06:31PM +0100, Nicholas Clark wrote:
>  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