Hi Andy,
On Jan 25, 2012, at 9:27 AM, Andy Wingo wrote:
> For me, it's hard to separate the "activation" concept from a function
> call -- where you also store return addresses, you have a register for
> the arguments, etc. Is that really a concept that is worth importing
> here? To me, block scope implies a local extension of the register
> file: a binding construct, rather than a control-flow construct.
Understood. It's certainly true that activations are currently tied to the
concept of function calls, in so much that they do currently always capture not
only the local variables but also the arguments. But this isn't really an
inherent property of activations so much as it is a current limitation of the
implementation that needs to be fixed – it is sub-optimal in cases where
variables are captured but arguments are not. Activations should support
capturing only local variables and not the arguments.
Just to clarify the benefits of the JSActivation class in JSC is, an activation
is a scope object capable of capturing:
* a set of local variables
* in functions, the arguments to the function
* capable of supporting additional variables being introduced
dynamically (e.g. from a nested direct eval).
In addition the activation object supports two important optimizations:
function f(arg)
{
x = random();
if (unlikely())
return function() { return x; };
}
Activations may be lazily allocated, only created if a code path is reached
that requires the scope to be captured – in the example if unlikely() returns
false and the closure return is not reached, then no scope object will be
allocated.
function f(arg)
{
var x = 0;
eval(arg);
while (x < 100000)
x += x;
return x;
}
Lazy tear-off. Even if a variable is captured its storage remains within the
register file (and all access from within this function will be via virtual
register access) until we leave the scope (i.e. the function returns).
> There are ways that these strategies could apply to lazy tear-off as
> well. The common denominator here is that we need a compile-time
> representation of the block-scoped locals, and that we need to make a
> decision at compile-time as to their allocation policy (e.g. in a
> register, lazily torn off, in a scope object, etc).
Yes – let's talk about this in terms of what types of scopes we need to
support, and the variables we will need to store, and how these can be
represented within the compiler.
An important point to recognize is that we don't need separate mechanisms in
the engine to support let and var, since the requirements for var are a subset
of those of let. Beyond the differences in parsing, a var variable is almost
completely indistinguishable from a let variable in the outermost scope:
function f()
{
var v = random();
return function() { return v; }
}
function f()
{
let l = random();
return function() { return l; }
}
Clearly let has a richer set of requirements – specifically that it may also be
block scoped – but any mechanism capable of supporting let should be perfectly
capable of supporting var, and const too (with state in the symbol table to
indicate the type of a variable, allowing const variables to be treated as read
only, and var variables possibly having some subtly different handling in the
case of a non-strict direct eval). Furthermore, not only is is possible for
the same scope object to be used to hold all three types of variables, it is
necessary to do so for an optimal implementation:
function f()
{
var v = random();
let l = random();
const c = random();
return function() { return v + l + c; };
}
Where the outermost scope of a function contains a mix of the three types of
variables, we should not need to create more than one node on the scope chain,
a single instance of a unified scope object capable of holding var, let, and
const values should sufficient.
Whatever scope object we use to store local variables at the outermost scope
needs to support capturing all three types of locals, capturing arguments,
having new vars introduced from a nested direct eval, and support important
optimizations including lazy creation and lazy tear-off. In short, it really
needs to be a JSActivation. :-)
What about the requirements for nested block scopes? Consider the following
example:
function f(arg1, arg2)
{
let x = 0;
eval(arg1);
{
let y = 0;
eval(arg2);
while (x < 100000) {
x += x;
y += y;
}
return x + y;
}
}
Regardless of the scope a variable is declared in, it should be optimized
equally – it would not make sense to implement 'x' as a variable with lazy
tear-off but place 'y' in an eagerly created scope object.
> Of course the aspect of activations that does apply directly would be
> that they can have symbol tables, and thus are useful for nested
> functions with eval(). You might be right that this is the important
> aspect.
Yes - TC-39 are currently keen to spec support for let into non-strict mode.
This is at an early stage and the semantics aren't nailed down, but it may mean
that a direct eval within a nested block scope will need to be able to
introduce new let variables onto the nearest block scope – if so, scope objects
implementing block scoped may need the ability to introduce new variables,
dynamically too – if so, block scopes will need pretty much all of the
capabilities of activations other than the ability to capture arguments.
> My current patches push on static scope objects, but they do resolve the
> bindings at compile-time. They also allow access to var-bound locals
> via registers, not by traversing the scope chain. There are a couple of
> easy optimizations that one could do to improve this: a block scope with
> no captured lexicals could be allocated as registers, and doesn't need a
> symbol table. A block scope with one captured lexical and two
> uncaptured lexicals doesn't need to store the uncaptured lexicals in its
> symbol table if no nested function uses eval().
The latter of these optimizations is partially supported for activations, and
fully fixing this would be a great step towards generalizing the activation
object to be able to be used to support let and const.
When we allocate the virtual registers for a function we allocate registers for
the captured variables first, and then allocate registers for the vars that are
not captured. However I believe when we tear off the activation, we tear off
all of the functions locals variables (and arguments) – whereas we should be
able to restrict to copying only the range of the virtual register bank that
needs capturing. And that extends to the argument registers, too – if a
closure only captures local variables, we should not be copying the arguments.
If the activation object was capable of supporting capture for ranges of the
register file, this would make activations suitable for implementing capture of
block scoped variables.
function f(arg, str)
{
let x = random();
let result = [];
let y = random();
result.push(function(){ return x + y; })
{
let i;
for (i in arg) {
let z = arg[i];
if (i & 1)
result.push(function(){ return x + y + z; })
}
return result;
}
}
In compiling the the above code, the bytecompiler should be able to perform a
register similar to the following:
r0: activation0
r1: x
r2: y
r3: result
r3: i
r4: activation1
r5: z
Upon entry to the outermost scope r0 is cleared. Upon reaching the first
closure, activation0 is created, capturing only the range of virtual registers
r2 – r3. The block scope containing i does not require an activation (i is not
captured). Upon entering the block scope for the body of the for loop r4 is
cleared. If the capturing closure is reached, the activation is created,
capturing the virtual register range r5 – r5. Upon reaching the end of the
block scope of the for loop body, perform tear-off activation on r4 (copying
values out of the register file and onto a heap object, if a capture occurred).
Upon reentering the head of the loop, r4 will be cleared again (ensuring the
same activation is not reused). When the loop completes, and the function
returns the containing scope's activation should be torn-off, copying the
values from the register file to a heap object and ensuring that they remain
available once the callframe for the has been unwound from the stack.
>> 1) Activations are faster.
>
> For captured variables, yes, but only assuming that you get register
> access to identifiers bound in outer blocks. Do you?
Well, activations are currently only allocated for the outermost block of a
function, so currently there is no outer block. :-)
But I see no reason why this would not work.
>> 2) Let, const and var may appear in the same block scope, and it would
>> not make sense to add two separate objects onto the scope chain, one
>> for each of the two types of declarations.
>
> Not sure what you mean here. Var bindings are hoisted to the function
> level; let and const bindings are hoisted to the block level. You would
> get a function activation, and then the block activations, as many as
> there are nested blocks -- minus one, it seems, given the current "one
> scope, function parameters are var-bound" discussion.
Sorry, My statement here wasn't very clear. I'm specifically talking about the
case where a let and var both appear in the outermost scope – highlighting that
this should only require one entry on the scope chain.
>> 3) Many optimizations will be equally applicable to all types of
>> variables (e.g. capture analysis), and we should not need this work to
>> be duplicated to operate over separate sets of data structures used to
>> represent the different variable types.
>
> I'm not sure how this point applies. Are you referring to the capture
> analysis in the parser or something deeper in the JIT?
The capture analysis propagates through to the JIT in the form of lazy scope
object creation and lazy tear-off – it would be undesirable to duplicate these
in the JIT. Furthermore these optimizations may want to become more advanced,
e.g. though applying escape analysis to capturing closures we may be able to
determine that in some cases the lazy tear-off can be avoided; if we do go down
this route it would be desirable not to have to duplicate this unnecessarily
for different types of scope objects.
>> I think the right route forwards is to rework these changes to be
>> oriented around an activation rather than a static scope object.
>> Landing these changes as is doesn't seem like the best move, since
>> they will only be introduce unnecessary complexity if our intention is
>> to switch to an activation based solution.
>
> I'm fine with doing it like that. However, I wonder: the current set of
> patches don't appear to add much complexity, and they use existing
> concepts. We could get a working implementation quickly with them, and
> refactor to use activations over time, helped by unit tests.
>
> But, as you like ;-)
>
> I'm interested in your feedback on what you think the ultimate compiled
> form of the examples I had at the start of the mail should be. Then
> once we agree I can make it happen :) Let me know!
I think that in an initial implementation, the example you gave is best
implemented in a similar fashion to the example I walked through above –
allocating one activation for the outer scope (to capture the argument x), and
one for the inner scope (to capture z). This should work, and not regress
performance for any existing code, so would be a good waypoint. Beyond this,
one could optimize further by adding logic to merge nest activations into outer
scopes, where it is safe to do so. In this case, we don't have separate
iterated captures of z so, it is safe to hoist z onto the outer activation, so
that only one activation is required. In done so, we should ensure the virtual
register allocation is sorted such that z gets lower numbered virtual register
than y, and as such the activation can capture x & z without capturing y. Hope
this makes sense.
I think it's important not to see the work to implement const and let as a new,
niche and experimental feature, but rather as a refactoring of a core and
universally used mechanism of the engine – supporting all local variables
including var. It is also important to bear in mind that we do not want to
land this compiled out, or in any way restricted – this mechanism should
immediately go live for const in all modes of execution (one javascript! – no
guts no glory!). As such, there is huge value in doing this right from the
outset. We want to encourage users over to the new features of let & const, so
don't want to land an implementation that will regress const performance in
some cases (allocating unnecessary additional scope object, losing lazy
creation, or losing lazy tear-off). GIven all this, I think it's really
important that we do this right from the outset, and I don't think it makes
sense to land an interim solution. To me it looks like doing this right means
using activations.
cheers,
G.
_______________________________________________
squirrelfish-dev mailing list
[email protected]
http://lists.webkit.org/mailman/listinfo.cgi/squirrelfish-dev
