543097 - Better inlining of closure creation to avoid the cost of needlessly looking up Function.prototype anew every time

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[David Mandelin [:dmandelin]]

Test case:

function f() {
  for (var i = 0; i < 1000000; ++i) {
    var g = function () {
      ++i;
    }
  }
}

f();

Shark results, focused on js_CloneFunctionObject:

	3.4%	100.0%	js	js_CloneFunctionObject	
	5.0%	96.1%	js	 js_NewObject	
	13.9%	62.4%	js	  js_GetClassPrototype	
	16.3%	27.6%	js	  js_NewObjectWithGivenProto	

We spend 2/3 of the time getting the class prototype, which presumably is the same for all functions.

Comment 1

[Jeff Walden [:Waldo]]

Attachment: Patch (also fixes equivalent problem for regular expression literals)

This patch is atop the one for bug 540985.

Comment 2

[Jason Orendorff [:jorendorff]]

Comment on attachment 424698 [details] [diff] [review]
Patch (also fixes equivalent problem for regular expression literals)

Thanks for fixing this.

Comment 3

[Jeff Walden [:Waldo]]

http://hg.mozilla.org/tracemonkey/rev/c842be0e6143

Comment 4

[David Mandelin [:dmandelin]]

With this patch, and with -j, I get a 2x speedup on the microbenchmark in comment 0, which corresponds to a 3-4x speedup for the closure creation operation.

But it doesn't speed up the interpreter without -j. Do we want to fix that, or is perf there less critical?

Comment 5

[Brendan Eich [:brendan]]

Interp perf matters, we know this cuz tracing fails to cover all cases. Not sure interp closure-creation perf matters but at this point we should rather unify and not worry. Unifying is good for consistency, not just perf.

/be

Comment 6

[Jeff Walden [:Waldo]]

The patch relies on tracing applying only to a single global object at a time.  The interpreter doesn't have a similar concept, so Function.prototype might vary each time the script is interpreted.  Fixing this in the interpreter in the same way requires new fundamental restrictions there that would at least be much bigger than the minimal tracing-only change made here.

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #6)
> The patch relies on tracing applying only to a single global object at a time. 
> The interpreter doesn't have a similar concept, so Function.prototype might
> vary each time the script is interpreted.  Fixing this in the interpreter in
> the same way requires new fundamental restrictions there that would at least be
> much bigger than the minimal tracing-only change made here.

How do you know how much bigger the changes would be? Fewer words, more evidence, please -- or this looks like an excuse :-/.

The interpreter does have the compiler and COMPILE_N_GO helping to pre-set global parents in function objects (all <script> tags including functions nested in them benefit from this). Where the function object must be cloned anyway (not a null closure set or init'ed as a method), but has the same parent as the compiler-preset one in its clone-parent, the clone could use the compiler-created function object's proto.

Two-line patch next.

/be

Comment 8

[Brendan Eich [:brendan]]

Attachment: js_CloneFunctionObject optimization

Comment 9

[Igor Bukanov]

(In reply to comment #7)
> The interpreter does have the compiler and COMPILE_N_GO helping to pre-set
> global parents in function objects (all <script> tags including functions
> nested in them benefit from this). Where the function object must be cloned
> anyway (not a null closure set or init'ed as a method), but has the same parent
> as the compiler-preset one in its clone-parent, the clone could use the
> compiler-created function object's proto.

I do not see how the patch above can help: a function in a <script> tag does not need to cloned. Only closures or top-level functions without COMPILE_N_GO would need to be cloned. But in those cases the compiler-time functions would have null prototype and their parent slot cannot match the runtime one.

Comment 10

[Brendan Eich [:brendan]]

(In reply to comment #9)
> I do not see how the patch above can help:

Oh, but it does, using the benchmark in comment 0:

$ time ~/Hacking/hg.mozilla.org/mozilla-central/js/src/Darwin_OPT.OBJ/js funbench.js

real	0m0.421s
user	0m0.207s
sys	0m0.048s
$ !time
time ~/Hacking/hg.mozilla.org/mozilla-central/js/src/Darwin_OPT.OBJ/js funbench.js

real	0m0.332s
user	0m0.206s
sys	0m0.044s
$ !time
time ~/Hacking/hg.mozilla.org/mozilla-central/js/src/Darwin_OPT.OBJ/js funbench.js

real	0m0.304s
user	0m0.207s
sys	0m0.044s
$ time ./Darwin_OPT.OBJ/js funbench.js

real	0m0.333s
user	0m0.198s
sys	0m0.045s
$ time ./Darwin_OPT.OBJ/js funbench.js

real	0m0.321s
user	0m0.199s
sys	0m0.044s
$ time ./Darwin_OPT.OBJ/js funbench.js

real	0m0.310s
user	0m0.198s
sys	0m0.045s

> a function in a <script> tag does not need to cloned.

That's true of function definitions, but not of function expressions (other than null closures set as methods), which must be evaluated to a fresh object each time. It's also not true of nested functions.

> Only closures or top-level functions without COMPILE_N_GO
> would need to be cloned. But in those cases the compiler-time functions would
> have null prototype and their parent slot cannot match the runtime one.

JSCompiler::newFunction presets compile-n-go function object proto and parent using the scope chain (global object) given to the compiler. This is done for nested as well as outer functions. It can succeed for nested functions and even top-level function expressions to match parent and shortcut proto-defaulting from having to js_GetClassObject, etc. -- the perf problem this bug is about.

/be

Comment 11

[Brendan Eich [:brendan]]

Oops, my mozilla-central optimized shell is slower for other reasons (I didn't think tracemonkey would differ in interpreter perf much from mozilla-central; I should know better).

Worse, the patch does not add code triggered by the benchmark in comment 0! More in a bit, but ignore the results in comment 10 for now -- sorry about that.

/be

Comment 12

[Brendan Eich [:brendan]]

Attachment: fix js_CloneFunctionObject optimization to kick in when it should

Now we are talking:

$ !time
time ./Darwin_OPT.OBJ/js funbench.js

real	0m0.407s
user	0m0.120s
sys	0m0.044s
Yoyodyne:src brendaneich$ !time
time ./Darwin_OPT.OBJ/js funbench.js

real	0m0.217s
user	0m0.121s
sys	0m0.044s
Yoyodyne:src brendaneich$ !time
time ./Darwin_OPT.OBJ/js funbench.js

real	0m0.218s
user	0m0.122s
sys	0m0.043s

This is apples-to-apples with respect to the ./Debug_OPT/js runs in comment 10, which were with the last version of this patch applied to tm tip.

/be

Comment 13

[Brendan Eich [:brendan]]

(In reply to comment #7)
> Two-line patch next.

Ok, eight-line (net of comments ;-).

I'm thinking we have interpreter low-hanging fruit to fix, not just bypass via tracing or even JaegerMonkey (in this case a common helper function was the place to put the targeted optimization).

/be

Comment 14

[Igor Bukanov]

Comment on attachment 426322 [details] [diff] [review]
fix js_CloneFunctionObject optimization to kick in when it should

>diff --git a/js/src/jsfun.cpp b/js/src/jsfun.cpp
> js_CloneFunctionObject(JSContext *cx, JSFunction *fun, JSObject *parent, JSObject *proto)
> {
>+    if (!proto) {
...
>+        for (JSObject *tmp = parent; tmp; tmp = tmp->getParent()) {
>+            if (tmp == fun->getParent()) {
>+                proto = fun->getProto();
>+                break;
>+            }
>+        }
>+    }

This should benefit indeed the nested functions in addition to script-level function expressions. I have missed that case with the previous path.

But for a nested function this still requires quite a few checks to execute. Perhaps we should just cache the last used [global, Function.prototype] pair in JSThread if not here but in another bug.

Comment 15

[Brendan Eich [:brendan]]

To show where nested functions need cloning but need benefit (there are many variations), change comment 0's benchmark to

function f() {
  for (var i = 0; i < 1000000; ++i) {
    var g = function () { }
  }
}

f();

No upvar means f is lightweight, so the clone created 1e6 times for each evaluation of g's initializer is parented by the global object. This speeds up big time too (user time from 200ms to 116ms).

/be

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #14)
> But for a nested function this still requires quite a few checks to execute.

Short loop, prefetched in predicted order, should hit icache and dcache well. More to the point, scope chains are shallow -- dmandelin has some figures in one of the "ClosurePerf" bugs.

/be

Comment 17

[Brendan Eich [:brendan]]

Waldo, I didn't put the js_CloneFunctionObject in a separate bug because this bug is not marked TM:, but it does say "inlining" -- either way is fine, I'm happy to spin out, happier still if you roll up the two patches into one and ride on igor's r+.

/be

Comment 18

[Brendan Eich [:brendan]]

Attachment: fix js_CloneFunctionObject optimization to avoid if-in-loop

I was thinking branch prediction thoughts that were not reflected in the code. This should be winning, even if it uses more instructions statically. Igor, what do you think?

/be

Comment 19

[Igor Bukanov]

(In reply to comment #18)
> Created an attachment (id=426332) [details]
> fix js_CloneFunctionObject optimization to avoid if-in-loop

For me it feels like over-optimization for a particular case while the issue here is that js_GetClassId(cx, clasp, &id) and js_GetClassPrototype(cx, parent, id, &proto)) are slow. If we inline js_GetClassId (or even have a version of js_NewObject that takes the id as a parameter) and add a cache to JSThread that js_GetClassPrototype can use to store the lookup results for the standard classes, then we would have something that benefits the rest of code as well.

Comment 20

[Jeff Walden [:Waldo]]

(In reply to comment #17)
> Waldo, I didn't put the js_CloneFunctionObject in a separate bug because this
> bug is not marked TM:, but it does say "inlining" -- either way is fine, I'm
> happy to spin out, happier still if you roll up the two patches into one and
> ride on igor's r+.

The first patch already landed, I think we're past the point of being able to treat as a single patch.  I don't mind if it stays here, others might -- seems best to err on the side of caution/simplicity and make a new bug.

Your trick didn't occur to me when I was writing the first patch (obviously), or I'd have run with it.  I was speaking with respect to a more general solution -- one which would address all object-valued literals in real use -- {}, [], /a/, function(){}.  This addresses function, I think regex could be addressed similarly, but {} and [] -- no such luck I think, unless we want to do a similar squirrel-away-ur-objects/arrays thing (following this patch's lead) or something else entirely (what I referred to as being beyond this bug's scope).

I echo Igor: we need to make the property-lookup path broadly faster for overall gains, not just narrow cases like prototype lookups.

Comment 21

[Brendan Eich [:brendan]]

(In reply to comment #19)
> (In reply to comment #18)
> > Created an attachment (id=426332) [details] [details]
> > fix js_CloneFunctionObject optimization to avoid if-in-loop
> 
> For me it feels like over-optimization for a particular case while the issue
> here is that js_GetClassId(cx, clasp, &id) and js_GetClassPrototype(cx, parent,
> id, &proto)) are slow.

Could be, but we have specific knowledge here about preset parent of compile-n-go compiled functions (same could go for regexps).

> If we inline js_GetClassId (or even have a version of
> js_NewObject that takes the id as a parameter) and add a cache to JSThread that
> js_GetClassPrototype can use to store the lookup results for the standard
> classes, then we would have something that benefits the rest of code as well.

I seem to recall gal hacking this up once but it didn't land. Cc'ing him.

/be

Comment 22

[Brendan Eich [:brendan]]

Ok, I filed bug 545529 -- sorry to spam this one, let's move over there.

/be

Comment 23

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/c842be0e6143