Optimizing property lookup across scope objects
Hi, Currently SquirrelFish doesn't optimize/cache access to properties across scope objects if the scope object is "dynamic", i.e. can gain properties at any time. This makes sense since a new property could be introduced in the scope object that shadows a previously cached one. For bindings to native objects, such as QObjects, we have the case of a JS object that's not fully dynamic (in the sense that properties can't be added to it ad hoc), but the only way to achieve the scope optimization seems to be to pre-populate a static scope object's symbol table with the object's available properties (in order for the bytecompiler to determine that the optimization is safe). Would it make sense to introduce a notion of a "semi-static" scope object, in which case a special bytecode is produced that 1) does the fully scoped lookup the first time; 2) patches itself to cache / look up the property directly subsequently (knowing that it's safe to skip the "semi-static" objects where the lookup failed the first time)? An alternative approach: Always cache the object where the property was resolved, and have hooks at property creation and deletion time that take care of invalidating the cache when properties are added to / removed from an object that's in some scope chain. This is more generic (works for all types of objects), but is probably more expensive (works under the assumption that property creation+deletion is a lot rarer than assigning to an existing property). Example use case: with (qtObject) { for (i = 0; i < 10000; ++i) Math.sin(i); } In this case, qtObject could have a property called Math that would shadow the Global Object's Math. But after the first lookup, we know whether this is the case. If it's not, it's safe to cache the Global Object's Math. On the other hand, if qtObject _does_ have a Math property, it can be cached / looked up directly in qtObject henceforth, since it's never going away (native Qt properties can't be deleted). Here's a benchmark I've been using: a = 123; o = {}; with (o) { (function() { for (var i = 0; i < 100000; ++i) { a; a; a; a; a; a; } })(); } Commenting out the "with" makes it 5x faster, because JSC is then permitted to do the caching. I'd like to achieve that if "o" were a QObject wrapper with no property "a", the benchmark would be about as fast with "with" as without. Kent
On May 5, 2010, at 7:36 AM, Kent Hansen wrote:
Hi, Currently SquirrelFish doesn't optimize/cache access to properties across scope objects if the scope object is "dynamic", i.e. can gain properties at any time. This makes sense since a new property could be introduced in the scope object that shadows a previously cached one.
For bindings to native objects, such as QObjects, we have the case of a JS object that's not fully dynamic (in the sense that properties can't be added to it ad hoc), but the only way to achieve the scope optimization seems to be to pre-populate a static scope object's symbol table with the object's available properties (in order for the bytecompiler to determine that the optimization is safe).
Would it make sense to introduce a notion of a "semi-static" scope object, in which case a special bytecode is produced that 1) does the fully scoped lookup the first time; 2) patches itself to cache / look up the property directly subsequently (knowing that it's safe to skip the "semi-static" objects where the lookup failed the first time)?
An alternative approach: Always cache the object where the property was resolved, and have hooks at property creation and deletion time that take care of invalidating the cache when properties are added to / removed from an object that's in some scope chain. This is more generic (works for all types of objects), but is probably more expensive (works under the assumption that property creation+deletion is a lot rarer than assigning to an existing property).
Example use case:
with (qtObject) { for (i = 0; i < 10000; ++i) Math.sin(i); }
In this case, qtObject could have a property called Math that would shadow the Global Object's Math. But after the first lookup, we know whether this is the case. If it's not, it's safe to cache the Global Object's Math. On the other hand, if qtObject _does_ have a Math property, it can be cached / looked up directly in qtObject henceforth, since it's never going away (native Qt properties can't be deleted).
Here's a benchmark I've been using:
a = 123; o = {}; with (o) { (function() { for (var i = 0; i < 100000; ++i) { a; a; a; a; a; a; } })(); }
Commenting out the "with" makes it 5x faster, because JSC is then permitted to do the caching. I'd like to achieve that if "o" were a QObject wrapper with no property "a", the benchmark would be about as fast with "with" as without.
It is not possible to optimise inside a |with| block -- we can't prove in advance that you will be using a inextensible object as your scope object so the fact that you can't add new properties to it is irrelevant, we have to assume that the object may change, and deoptimise accordingly. That said |with| has a significant amount of baggage that leads to unexpected semantic behaviour, enough to make ES5 strict mode disallow |with| entirely. Good JS should never use |with| so there's no point in trying to optimise it. A better example of something where we currently don't optimise but _could_ is cross scope look up with dynamic insertion -- eg. optimising access to the global object from a function that uses eval. --Oliver
ext Oliver Hunt wrote:
It is not possible to optimise inside a |with| block -- we can't prove in advance that you will be using a inextensible object as your scope object so the fact that you can't add new properties to it is irrelevant, we have to assume that the object may change, and deoptimise accordingly.
Right, except in the benchmark I posted, a closure is created inside the with block. When the resulting function is compiled, the compiler has the scope object available and could query it. The compiler already does this for instances of JSVariableObject via isDynamicScope(). isDynamicScope() would have to be moved to JSObject, be renamed and rather return an enum with entries StaticScope, DynamicScope, and SemiStaticScope, so that the compiler could apply scope optimizations to a wider range of objects.
That said |with| has a significant amount of baggage that leads to unexpected semantic behaviour, enough to make ES5 strict mode disallow |with| entirely. Good JS should never use |with| so there's no point in trying to optimise it.
Yeah. :)
A better example of something where we currently don't optimise but _could_ is cross scope look up with dynamic insertion -- eg. optimising access to the global object from a function that uses eval.
Like the following? a = 123; (function() { var i; eval("1"); for (i = 0; i < 100000; ++i) { a; a; a; a; a; a; } })(); I see it's generating op_resolve instead of op_resolve_global now. That causes a 4x slowdown. Similarly for this one: a = 123; (function() { eval("1"); (function() { for (var i = 0; i < 100000; ++i) { a; a; a; a; a; a; a; a; } })(); })(); With V8 version 2.2.3.2 the eval doesn't have any performance impact. Any suggestions on how to approach this optimization? I'm guessing this is the case that would still need to work: a = 2; (function(code) { eval(code); return a + a; })("var a = 4"); // must return 8, not 4 So "a" is not going to be in the symbol table at function compile time, but the eval could introduce it... How about a bytecode that does a dynamic lookup the first time, but patches itself to become e.g. resolve_global if appropriate? It would potentially have to be un-patched again after a subsequent eval, though... I created https://bugs.webkit.org/show_bug.cgi?id=38644. Regards, Kent
On May 6, 2010, at 7:18 AM, Kent Hansen wrote:
ext Oliver Hunt wrote:
It is not possible to optimise inside a |with| block -- we can't prove in advance that you will be using a inextensible object as your scope object so the fact that you can't add new properties to it is irrelevant, we have to assume that the object may change, and deoptimise accordingly.
Right, except in the benchmark I posted, a closure is created inside the with block. When the resulting function is compiled, the compiler has the scope object available and could query it. The compiler already does this for instances of JSVariableObject via isDynamicScope(). isDynamicScope() would have to be moved to JSObject, be renamed and rather return an enum with entries StaticScope, DynamicScope, and SemiStaticScope, so that the compiler could apply scope optimizations to a wider range of objects.
That said |with| has a significant amount of baggage that leads to unexpected semantic behaviour, enough to make ES5 strict mode disallow |with| entirely. Good JS should never use |with| so there's no point in trying to optimise it.
Yeah. :)
This is quite a lot of complexity for very little real world win. You should never use |with|. Here's the problem: var myProperty = "foo!"; function f(o) { with(o) { return function(){ return myProperty; } } } g = f(myAwesomeMagicalObject); alert(g()) // foo! yay!!! You want this to say "i know i can't have any additional properties on this object", but then i do Object.prototype.myProperty = "bar!" alert(g()) // bar! yay!!! So unless you're object also does not inherit from the Object prototype (the hell?) and somehow prevents its prototype being reassigned (i don't think this is possible in the API) the object can always have new properties added. The net effect of all of this is that if you want to do a resolve over a |with| you have to record the full scope structure chain, which while possible, would be very complicated to make correct. This gets me back to what i said in my first reply: There's no point going to the effort of making a feature faster when we are telling people to not use it. If you're writing code in JS that makes use of |with| it's highly likely that bad stuff can happen unintentionally.
A better example of something where we currently don't optimise but _could_ is cross scope look up with dynamic insertion -- eg. optimising access to the global object from a function that uses eval.
Like the following?
a = 123; (function() { var i; eval("1"); for (i = 0; i < 100000; ++i) { a; a; a; a; a; a; } })();
I see it's generating op_resolve instead of op_resolve_global now. That causes a 4x slowdown. Similarly for this one:
a = 123; (function() { eval("1"); (function() { for (var i = 0; i < 100000; ++i) { a; a; a; a; a; a; a; a; } })(); })();
With V8 version 2.2.3.2 the eval doesn't have any performance impact.
I would check with eval not being a static string -- it would be trivial (albeit relatively pointless) to detect an eval that wouldn't introduce local variables if the input is a string.
Any suggestions on how to approach this optimization? I'm guessing this is the case that would still need to work:
a = 2; (function(code) { eval(code); return a + a; })("var a = 4"); // must return 8, not 4
So "a" is not going to be in the symbol table at function compile time, but the eval could introduce it... How about a bytecode that does a dynamic lookup the first time, but patches itself to become e.g. resolve_global if appropriate? It would potentially have to be un-patched again after a subsequent eval, though...
You can't repatch to resolve_global because your function maybe called multiple times, and just because the first time you succeed doesn't mean you will the next time so you need additional opcodes. There'd also be no reason to limit this just to global resolution as the special op_resolve_global logic is purely to avoid walking the scope chain, and if you're trying to be fast in the presence of |eval| you have to check that the |eval| has not actually done anything in each effected level in the scope chain. So you'd want something like op_resolve_with_stupid dst, levelsUpScopeChain, offset, propertyName Once again this feels like optimising stupid behaviour however.
I created https://bugs.webkit.org/show_bug.cgi?id=38644.
Regards, Kent
--Oliver
ext Oliver Hunt wrote:
This is quite a lot of complexity for very little real world win. You should never use |with|.
Here's the problem:
[...] Yep, makes sense, thanks for the example.
With V8 version 2.2.3.2 the eval doesn't have any performance impact.
I would check with eval not being a static string -- it would be trivial (albeit relatively pointless) to detect an eval that wouldn't introduce local variables if the input is a string.
Hehe, indeed... a = 2; (function(code) { eval(code); (function() { for (var i = 0; i < 100000; ++i) { a; a; a; a; a; a; a; a; } })(); })(String.fromCharCode(0x76, 0x61, 0x72, 0x20, 0x63, 0x3D, 0x34)); // var c=4 5x slowdown in V8 now due to the eval, about the same as with jsc.
You can't repatch to resolve_global because your function maybe called multiple times, and just because the first time you succeed doesn't mean you will the next time so you need additional opcodes. There'd also be no reason to limit this just to global resolution as the special op_resolve_global logic is purely to avoid walking the scope chain, and if you're trying to be fast in the presence of |eval| you have to check that the |eval| has not actually done anything in each effected level in the scope chain. So you'd want something like
op_resolve_with_stupid dst, levelsUpScopeChain, offset, propertyName
Once again this feels like optimising stupid behaviour however.
Yeah, the complexity doesn't seem warranted. Any way to add caching in op_resolve, e.g. could it cache if the property is found in the Global Object (last scope object)? That could speed up the eval case quite a bit; there would still be a call to the activation object's getPropertySlot() every time, but the call to Global Object would be avoided (basically dynamic fallback to resolve_global). Regards, Kent
participants (2)
-
Kent Hansen
-
Oliver Hunt