RR: Compiler optimization to inline delegation patterns in the JavaScript AST
BobV
Original Java:
Label l = new Label(String.valueOf(i));
DOM.setStyleAttribute(l.getElement(), "border-left", i
+ "px solid black");
Unoptimized JS:
l = $Label_0(new Label(), valueOf(i));
setStyleAttribute(l.element, 'border-left', i + 'px solid black');
function valueOf(x){
return '' + x;
}
function setStyleAttribute(elem, attr, value){
$clinit_8();
$setStyleAttribute(impl, elem, attr, value);
}
function $setStyleAttribute(this$static, elem, attr, value){
elem.style[attr] = value;
}
Optimized JS:
l = $Label_0(new Label(), '' + i);
$clinit_8() , l.element.style['border-left'] = i + 'px solid black';
Notice how the operation in the leaf setStyleAttribute function
(originally from the JSNI leaf method in a DOMImpl) gets hoisted into
the outer call site? This means that DOM.createTD() actually becomes
$doc.createElement('td') at the call site. Because the optimization
is taking place at the JS level, the optimizations can be hoisted into
JSNI methods.
Practical impact:
- Compiling the Hello, Dynatable, and the KitchenSink samples show a
roughly 20% reduction in the total number of functions defined in the
output.
- This results in a very slight reduction in total output size,
likely due to the fact that the "function" keyword is about the same
length as the average hoisted expression.
- The attached Hello demo times how long it takes to add N many
labels to a VerticalPanel and set a border style property on each
Label. In FF on my MBP, the optimized version is roughly 500ms faster
when setting up 5000 labels. Safari shows about a 300ms difference.
Nuts-and-bolts:
- This works by looking at all function invocations and examining
the function being invoked. It must:
- Consist of one statement or a clinit followed by a single statement
- JsNameRefs in the statement refer only to parameters or global
names (i.e. no instance references via this.x)
- Refer to all of its parameters, in their declaration order.
(this$static is exempt)
- If the function looks like a delegator, its expression is hoisted
into the original call site, and references to parameters are replaced
with the original call argument expressions (hence the need for proper
ordering.
- A second optimization pass removes unused functions from the global scope.
Todo:
- expand the hoistedExpression() function to include more expression types
- add a fixup visitor to remove redundant clinit() hoisted into a function
- add more testing to ensure it doesn't affect order-of-evaluation
Right now, I'm mainly looking for feedback on the correctness of the
implementation.
--
Bob Vawter
Google Web Toolkit Team
Matthew Mastracci
Awesome work!
Since unused parameters are silently ignored in JS, could you relax
this requirement:
> - Refer to all of its parameters, in their declaration order.
> (this$static is exempt)
to:
Refers to zero or more of its parameters in declaration order.
?
> js_delegation_remover_r1463_r3.patch
> 44KDownload
>
> Hello.java
> 2KDownload
John Tamplin
Practical impact:
- Compiling the Hello, Dynatable, and the KitchenSink samples show a
roughly 20% reduction in the total number of functions defined in the
output.
Great work!
- This results in a very slight reduction in total output size,
likely due to the fact that the "function" keyword is about the same
length as the average hoisted expression.
Is this before or after compression?
Nuts-and-bolts:
- This works by looking at all function invocations and examining
the function being invoked. It must:
- Consist of one statement or a clinit followed by a single statement
I assume this could be relaxed in the future if warranted -- such as looking at the size of the statement(s) to be inlined and the number of places to inline it, right? For example, if there is only one call site, it seems we should prefer to inline it regardless of the size.
- JsNameRefs in the statement refer only to parameters or global
names ( i.e. no instance references via this.x)
- Refer to all of its parameters, in their declaration order.
(this$static is exempt)
Is that necessary if the arguments passed from the call site are side effect free? Ie, if I pass some expression that doesn't produce a side-effect, I don't care if it is evaluated out-of-order or ignored entirely (you do still have to worry about other expressions with side effects referencing some portion of a side-effect-free expression).
--
John A. Tamplin
Software Engineer, Google
Bruce Johnson
on. I could imagine for a large large code base (e.g. QuePlix), the
inlined calls sites could start to outpace the saving from function
removal. If it's very close to the same size but measureably faster to
execute, then it's definitely a win.
FWIW, the compiled script size itself isn't actually what makes apps
slower, except to the extent that the download time increases
(although that itself is a function of the compressed script size). In
fact, the parsing of script text is immeasurably fast, even for
multiple-megabyte scripts. Fast context-free parsing is a well-solved
problem.
-- Bruce
P.S. This is excellent so far, but I'm reserving my unreserved w00t
for when you can remove redundant clinits :-)
On 10/11/07, BobV <bo...@google.com> wrote:
> /*
> * Copyright 2007 Google Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License"); you may not
> * use this file except in compliance with the License. You may obtain a copy of
> * the License at
> *
> * http://www.apache.org/licenses/LICENSE-2.0
> *
> * Unless required by applicable law or agreed to in writing, software
> * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
> * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
> * License for the specific language governing permissions and limitations under
> * the License.
> */
> package com.google.gwt.sample.hello.client;
>
> import com.google.gwt.core.client.EntryPoint;
> import com.google.gwt.user.client.DOM;
> import com.google.gwt.user.client.Window;
> import com.google.gwt.user.client.ui.Button;
> import com.google.gwt.user.client.ui.ClickListener;
> import com.google.gwt.user.client.ui.Label;
> import com.google.gwt.user.client.ui.RootPanel;
> import com.google.gwt.user.client.ui.TextBox;
> import com.google.gwt.user.client.ui.VerticalPanel;
> import com.google.gwt.user.client.ui.Widget;
>
> /**
> * HelloWorld application.
> */
> public class Hello implements EntryPoint {
> final TextBox tb = new TextBox();
>
> public void onModuleLoad() {
> tb.setText("100");
> Button b = new Button("Click me", new ClickListener() {
> VerticalPanel vp;
>
> public void onClick(Widget sender) {
> if (vp != null) {
> vp.removeFromParent();
> }
> vp = new VerticalPanel();
> RootPanel.get().add(vp);
>
> long startTime = System.currentTimeMillis();
> int num = Integer.decode(tb.getText()).intValue();
> for (int i = 0; i < num; i++) {
> Label l = new Label(String.valueOf(i));
> vp.add(l);
> DOM.setStyleAttribute(l.getElement(), "border-left", i
> + "px solid black");
> }
> Window.alert(String.valueOf(System.currentTimeMillis() - startTime));
> }
> });
>
> RootPanel.get().add(tb);
> RootPanel.get().add(b);
> }
> }
>
>
>
John Tamplin
We should also compile a large application with this inlining turned
on. I could imagine for a large large code base (e.g. QuePlix), the
inlined calls sites could start to outpace the saving from function
removal. If it's very close to the same size but measureably faster to
execute, then it's definitely a win.
I would think we can calculate the size impact of inlining something (which might be an overestimate if later optimization removes clinit calls, for example). We can do testing and come up with a threshold -- ie, inlining this will give a 5% speedup so we are willing to pay 8% increase in script size, or whatever.
FWIW, the compiled script size itself isn't actually what makes apps
slower, except to the extent that the download time increases
(although that itself is a function of the compressed script size). In
fact, the parsing of script text is immeasurably fast, even for
multiple-megabyte scripts. Fast context-free parsing is a well-solved
problem.
Right, I was just thinking of script size issues when talking about the size of the code to be inlined. Ie, one very long statement might not need to be inlined into even two call sites, while something with several shorter statements might well be inlined.
Matthew Mastracci
noticeable startup delay which seems to be the execution of the object
prototypes. Reducing the number of prototypes that need to be created
should help here.
I just ran in against my codebase to check things out. I saw a pretty
decent savings re: number of functions removed. These numbers are
from the default obfuscated mode.
Before size: 202269 (gzip -9 = 58133)
After size: 195976 (gzip -9 = 55580)
Approximate function count (grep "function" | wc -l) went from 2426 to
1921 (20% reduction).
Not only did it reduce the codesize (3.1%), but it helped it compress
significantly better (4.3% reduction in compressed code size).
I'd say this is a win all around. Well done!
BTW, feel free to contact me privately to discuss any further details
of my investigation.
On Oct 11, 9:39 am, "Bruce Johnson" <br...@google.com> wrote:
> We should also compile a large application with this inlining turned
> on. I could imagine for a large large code base (e.g. QuePlix), the
> inlined calls sites could start to outpace the saving from function
> removal. If it's very close to the same size but measureably faster to
> execute, then it's definitely a win.
>
> FWIW, the compiled script size itself isn't actually what makes apps
> slower, except to the extent that the download time increases
> (although that itself is a function of the compressed script size). In
> fact, the parsing of script text is immeasurably fast, even for
> multiple-megabyte scripts. Fast context-free parsing is a well-solved
> problem.
>
> -- Bruce
>
> P.S. This is excellent so far, but I'm reserving my unreserved w00t
> for when you can remove redundant clinits :-)
>
> > *http://www.apache.org/licenses/LICENSE-2.0
BobV
> Since unused parameters are silently ignored in JS, could you relax
> this requirement:
It can be relaxed if the argument at the call site has no
side-effects. A separate effort that I'm working on is to link as
many of the JsNodes as possible back to the Java AST from which they
were generated. Once that's done, it should be possible to perform
this optimization. It would also be possible to squeeze
un-referenced, though non-side-effect-free arguments into comma
expressions, but that starts to seem like too much of a corner case
for the initial pass.
Ray Cromwell
This is awesome work. At first, I was confused as to why you chose
to do this in the Js AST instead of the Java AST, but after thinking
about it, I think I know why.
I think eventually being able to hoist expressions with instance
references will show major savings on JS wrappers. (hint hint)
-Ray
mP
:)
> -Ray
BobV
Here's an updated version of the patch:
- Makes a pass at removing redundant clinit calls. It's not
completely optimal with regards to merging branches together, but it
handles the 80% case of multiple DOM calls stacked together.
- Moves the hoistedExpression() to its own class to declutter
JsDelegationRemover
- Increases the variety of expressions that can be hoisted. [ The
~(~x) construct now works.]
@Scott
I'm calling it feature-complete at this point, so please take this
as the version to review.
BobV
functions that are not defined statically (e.g. function literals in
JSNI).
Attached is a demo app that makes use of functions-as-objects, and
the resulting JavaScript. Notice that while the static function
"alert" is hoisted into the function literals, the function literals
themselves are not inlined. If the function is accessed via a field
of parameter (e.g. this$static.blah = someFunction), this form is not
inlined and remains this$static.blah(args) at the original call site.
Scott Blum
This looks great! Just a few things, really, and several of them are nitpicks.
- Several of the files could use an autoformat, I can see extra whitespace in the diff tool
- JsNameRef can now implement HasName?
- Now that you've caught all the calls to the JsFunction constructor, perhaps it'd be good to go back to the null calls and have them call a 2 argument version?
- How important is it to actually have a backreference from the JS AST to the Java AST? Seems like that could get in the way of merging with the backend of JS compiler. I'm just wondering if a smaller piece of information would be enough. Not a big concern, just thought I'd ask.
- HasOriginator is probably overkill for now; no one ever calls getOriginator().
JsDelegationRemover.findPenultimate() has a stray cast
RemoveDelegationVisitor.visit():
- We don't typically finalize params and locals unless there's a specific reason to?
- The comment "Don't descend into JsInvocation that we just replaced" made me realize that the typical pattern we would use is to actually use endVisit() rather than visit(), and know that all of my subexpressions would have already been inlined if needed. This should actually allow for faster convergence. Is there something that made you decide to do visit() instead?
NameRefReplacerVisiter:
- Fields should typically be private unless accessed externally
- Oddly, "arguments" and "parameters" don't seem to need to even be fields at all
- "broken" should be removed, ne?
- The visit implementation confuses me.. instead trying to prewalk down a qualifier chain, why not just let visitation reach the JsNameRef you actually want to replace and do the replacement then? This is another case endVisit() is typically the right thing to do.
IsDelegatingVisitor:
- I'm kind of leery of the special-casing for "this$static".. can you justify it?
- endVisit() would save you from having to do your own traversal of the qualifier chains; all you really care about here is unqualified name refs.
- "leftmost will be null if the left-most is a JsThisRef or a literal" - what's wrong with accessing name refs off a literal?
DuplicateClinitRemover
- maybe should have a no-arg ctor as well
- there is a bug here I think; you allow natural traversal into for and while loops, but for/while loops are not guaranteed to execute at all
- manual traversal of JsBinaryOperations is the right call here, I think!
JsUnusedFunctionRemover:
- totalFunctions stray code
- I think you should only remove functions that you can verify came from Java code; this would remove the need to special-case gwtOnLoad.
Cloner:
- I think you're trying to swim upstream with this one.. you must flow with the river. You've basically rewritten all the traversal logic that the visitor pattern gives you for free. The best pattern I've yet found for cloning a tree is to use endVisits() and push nodes on a stack as you clone them. Then when you instantiate the parent, you know the children have already been cloned, which often lets you use a multi arg constructor to build the parent in one shot. See GenerateJavaScriptAST for an example of this; you can think of JS AST generation as walking the Java tree and "cloning" it into a parallel AST.
- The whole InternalCompilerException.getCause() instanceof CannotHoistExpression seems *extremely* fishy to me
Scott
BobV
> This looks great! Just a few things, really, and several of them are
> nitpicks.
Nitpicks are good. This code has to be solid from day one, or we'll
have strange errors all over the place.
> - Several of the files could use an autoformat, I can see extra whitespace
> in the diff tool
Fixed. I didn't autoformat the larger files like
JavaToJavaScriptCompiler to avoid unrelated changes.
> - JsNameRef can now implement HasName?
Done.
> - Now that you've caught all the calls to the JsFunction constructor,
> perhaps it'd be good to go back to the null calls and have them call a 2
> argument version?
Done.
> - How important is it to actually have a backreference from the JS AST to
> the Java AST? Seems like that could get in the way of merging with the
> backend of JS compiler. I'm just wondering if a smaller piece of
> information would be enough. Not a big concern, just thought I'd ask.
> - HasOriginator is probably overkill for now; no one ever calls
> getOriginator().
I added getOriginator to support JsUnusedFunctionRemover removing only
static/Java functions.
>
> JsDelegationRemover.findPenultimate() has a stray cast
findPenultimate and findLeftMost have been removed after restructing
the visitors to use the endVisit pattern.
>
> RemoveDelegationVisitor.visit():
> - We don't typically finalize params and locals unless there's a specific
> reason to?
Older versions had some inner classes. Fixed.
> - The comment "Don't descend into JsInvocation that we just replaced" made
> me realize that the typical pattern we would use is to actually use
> endVisit() rather than visit(), and know that all of my subexpressions would
> have already been inlined if needed. This should actually allow for faster
> convergence. Is there something that made you decide to do visit() instead?
Most of the visitors have been reworked to use endVisit. I didn't do
it initially because I didn't really have any reason to know why one
would be better than the other.
> NameRefReplacerVisiter:
> - Fields should typically be private unless accessed externally
Fixed, except for one public final field.
> - Oddly, "arguments" and "parameters" don't seem to need to even be fields
> at all
Fixed.
> - "broken" should be removed, ne?
Fixed. Old debugging code.
> - The visit implementation confuses me.. instead trying to prewalk down a
> qualifier chain, why not just let visitation reach the JsNameRef you
> actually want to replace and do the replacement then? This is another case
> endVisit() is typically the right thing to do.
Reworked with endVisit.
> IsDelegatingVisitor:
> - I'm kind of leery of the special-casing for "this$static".. can you
> justify it?
It was to support the DOM leaf methods, which never refer to
this$static. I've reworked this to eliminate the special case by
assigning parameters into two buckets, "strict" and "flexible".
Strict parameters must be used exactly one in their declaration order.
Flexible parameters may be re-ordered and used any number (or zero)
times. Currently, only literals, JsNameRefs, and JsThisRefs are
considered flexible.
> - endVisit() would save you from having to do your own traversal of the
> qualifier chains; all you really care about here is unqualified name refs.
Done.
> - "leftmost will be null if the left-most is a JsThisRef or a literal" -
> what's wrong with accessing name refs off a literal?
This has been rewritten.
> DuplicateClinitRemover
> - maybe should have a no-arg ctor as well
Done.
> - there is a bug here I think; you allow natural traversal into for and
> while loops, but for/while loops are not guaranteed to execute at all
Added explicit visit methods for For, ForIn, and While
> - manual traversal of JsBinaryOperations is the right call here, I think!
> JsUnusedFunctionRemover:
> - totalFunctions stray code
Removed.
> - I think you should only remove functions that you can verify came from
> Java code; this would remove the need to special-case gwtOnLoad.
Fixed. This was what the getOriginator() was supposed to support.
> Cloner:
Cloner has been rewritten to use a stack-based approach. It's now
sensitive to the internal traversal order of the JsNodes (which
determines the order of elements on the stack), but it's a lot
cleaner.
> - The whole InternalCompilerException.getCause() instanceof
> CannotHoistExpression seems *extremely* fishy to me
CHE extends ICE now and the check isn't necessary. I wanted an
exception to be able to short-circuit all evaluation.
Scott Blum
- I disagree with the decision to subclass ICE. ICE is an exception that should never get thrown and automatically spells disaster. Unless I'm missing it, CannotHoistException is expected. If you want to use an exception here, don't subclass ICE, and don't expose the exception publically. Just return null from hoist() if you can't.
JsDelegationRemover:
- 216: these guys should be private
- 251: you should assert that strictParameters.get(0) == name
- 278: should be final
- 493: you need to recursively check the qualifier
- 550: should be an ICE or assertion
IsDelegatingVisitor: are you certain the our JS AST visitation order matches actual evaluation order in all the cases you case about? If you find a case where it doesn't, I might argue for changing the JS AST visit order.
- You might add a TODO to JsDelegationRemover that if we normalize the JS AST such that all complex statements have JsBlocks, it would remove a lot of the special casing.
JsUnusedFunctionRemover:
- need format
- 99: make these private
Rest looks good. More comments inline.
> - How important is it to actually have a backreference from the JS AST to
> the Java AST? Seems like that could get in the way of merging with the
> backend of JS compiler. I'm just wondering if a smaller piece of
> information would be enough. Not a big concern, just thought I'd ask.
> - HasOriginator is probably overkill for now; no one ever calls
> getOriginator().
I added getOriginator to support JsUnusedFunctionRemover removing only
static/Java functions.
My point is that you don't actually care what the JMethod is at all, do you? Really all you really need is a boolean flag to tell you whether a function was generated from Java or not. So why entangle the JS AST with the Java AST?
> IsDelegatingVisitor:
> - I'm kind of leery of the special-casing for "this$static".. can you
> justify it?
It was to support the DOM leaf methods, which never refer to
this$static. I've reworked this to eliminate the special case by
assigning parameters into two buckets, "strict" and "flexible".
Strict parameters must be used exactly one in their declaration order.
Flexible parameters may be re-ordered and used any number (or zero)
times. Currently, only literals, JsNameRefs, and JsThisRefs are
considered flexible.
Nice.
Scott
BobV
> JsHoister:
> - I disagree with the decision to subclass ICE. ICE is an exception that
> should never get thrown and automatically spells disaster. Unless I'm
> missing it, CannotHoistException is expected. If you want to use an
> exception here, don't subclass ICE, and don't expose the exception
> publically. Just return null from hoist() if you can't.
CannotHoistException has been removed in favor of setting a flag and
pushing a null onto the stack. With the current implementation of
JsVisitor, there's no way to emit a runtime exception to be caught at
the call to accept() without catching an ICE and looking at the cause.
An exception that extends ICE will be thrown from accept() without
modification, though.
> JsDelegationRemover:
> - 216: these guys should be private
Done.
> - 251: you should assert that strictParameters.get(0) == name
I've made it an if() {throw ICE}
> - 278: should be final
Done.
> - 493: you need to recursively check the qualifier
Done.
> - 550: should be an ICE or assertion
A mismatch between the number of parameters and arguments can happen
if the user is using a varargs-style JavaScript function. I've added
a comment to that effect.
> IsDelegatingVisitor: are you certain the our JS AST visitation order matches
> actual evaluation order in all the cases you case about? If you find a case
> where it doesn't, I might argue for changing the JS AST visit order.
I've taken a pass over the implementations of traverse() in the JsNode
hierachy, and it looks like everything does the standard left-to-right
traversal order.
> - You might add a TODO to JsDelegationRemover that if we normalize the JS
> AST such that all complex statements have JsBlocks, it would remove a lot of
> the special casing.
Added.
> JsUnusedFunctionRemover:
> - need format
> - 99: make these private
Done.
> > I added getOriginator to support JsUnusedFunctionRemover removing only
> > static/Java functions.
>
> My point is that you don't actually care what the JMethod is at all, do you?
> Really all you really need is a boolean flag to tell you whether a function
> was generated from Java or not. So why entangle the JS AST with the Java
> AST?
This has been replaced with a flag boolean value "fromJava".
Matthew Mastracci
I think I've found a bug in the inliner.
When I compile this code in obfuscated mode, it seems to mangle in
inlining of Array.cloneSubRange and ends up assigning a local variable
to its undefined self instead of the parameter:
Object[] a = new Object[] { 1, 2, 3 };
Arrays.sort(a);
This is the obfuscated code (notice the a=a):
_=uib.prototype=new oUb();_.eQ=Cib;_.hC=Dib;_.tS=Fib;_.tN=B5b
+kw;_.tI=232;function fjb(b,c,e){var
a,d;a=a;d=a.slice(c,e);kjb(a.tN,a.tI,a.qI,d);return a;}
Here's cloneSubRange in pretty mode. It looks like that "a=a" should
be "a=b".
function cloneSubrange(array, fromIndex, toIndex){
var a, result;
a = array;
result = a.slice(fromIndex, toIndex);
initValues(a.typeName$, a.typeId$, a.queryId$, result);
return array;
}
> js_delegation_remover_r1480.patch
> 56KDownload
BobV
> I think I've found a bug in the inliner.
I can't recreate this using the given example at r1480 with or
without the patch.
The inliner wouldn't affect the assignment of names within the
function scope. Notice how the parameter and the local variable have
both been reduced to "a"? Could you have some stray modifications
from the compiler work in your client?
BobV
> Notice how the parameter and the local variable have
> both been reduced to "a"?
No, wait, I can't read what's on the screen in front of me.
When I compile the output, I get:
function yb(b,c,e){var a,d;a=b;d=a.slice(c,e);Cb(a.tN,a.tI,a.qI,d);return d;}
The a=b is being correctly assigned.
Matthew Mastracci
patch. Everything seems to be working now:
_=hc.prototype=new de();_.tN=tf+s;_.tI=12;function pc(b,c,e){var
a,d;a=b;d=a.slice(c,e);tc(a.tN,a.tI,a.qI,d);return d;}
It even works when I apply my parameter pruner patch, scott's enum
patch et. al. Sorry about that.
On Oct 17, 6:06 pm, BobV <b...@google.com> wrote:
Scott Blum
GenerateJavaScriptAST(1396): Can you please explain this change?
JsName(29): Comment incomplete
JsDelegationRemover(70): This should either be moved into the javadoc comment or put in a non-javadoc multiline comment just *inside* the class def.
JsDelegationRemover(73): should be private
JsDelegationRemover(555): this could have an interaction with mmastrac's parameter removal patch; sometimes we'll end up with more arguments than params. But, I guess we wouldn't be able to inline in those cases anyway, because the extra arguments would have never been evaluated by the inlined code. So I think it's ok after all, glad I talked myself through that.
Scott
BobV
> GenerateJavaScriptAST(1396): Can you please explain this change?
It actually doesn't make sense, as that's a polymorphic method to begin with.
> JsName(29): Comment incomplete
Fixed.
> JsDelegationRemover(70): This should either be moved into the javadoc
> comment or put in a non-javadoc multiline comment just *inside* the class
> def.
Now a block comment inside the class.
> JsDelegationRemover(73): should be private
Fixed.
Scott Blum
Scott
Bruce Johnson
BobV
> Looks great, feel free to commit! You might want to add a blank line
> between that internal class comment in JsDelegationRemover and the "called"
> field, otherwise the comment appears to be on the field.
Fixed. Committed at r1481.
Comparing the number of named functions in the sample apps in the
1.4.60 release versus r1481:
cat */www/com*/*.cache.js | egrep -o 'function [^(]+\(' | wc -l
1.4.60: 31697
r1481: 23366 (A 26% reduction)
The cache.js files are smaller overall by 3.2%.