Bug 15884 – JavaScriptCore should use simple type inferencing to speed-up AddNode

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Eric Seidel (no email)]

JavaScriptCore should use simple type inferencing to speed-up AddNode (and other nodes which depend on input types).

I propose that this type inferencing be done in a separate walk of the AST tree, instead of at parse time.  That makes it easier to do const collapsing and const propagation before the type inferencing pass.  Maybe all of these get rolled into a single "optimize" pass in the end.

In this optimize method, we would inference the types of the node children (recursive call, probably) and then use that information to infer the types of this node.  Often the child node information is not needed to inferring the type, but propagating the call down the tree is needed for a full tree walk.  Based on the types, we would then placement new a more specific node instead of the generic AddNodeObjects (see below).

The idea is to have AddNodeObjects AddNodeNumbers AddNodeStrings, where Objects is where you have to call toPrimative first on both, Strings you only need to call evaluate() and cast to a StringImp and grab the value, we could add StringLeft and StringRight for the cases where one of them is a string and the other is not, but I think that'd be overkill for the first pass.

Numeric would be the big speedup, because you'd just immediately call evaluateToNumber (once bug 15879 is in) and not only would the AddNodeNumbers have no branches for types, but it would also be dealing with doubles directly (in both the evaluate and evaluateToNumber cases).

Other nodes could do the same sort of thing for a speedup, the comparison Nodes being a good example.

[Eric Seidel (no email)]

This is next on my list.

[Eric Seidel (no email)]

Created attachment 17167 [details]
A fix (SunSpider claims this is a wash)

This speeds up some tests, and slows down others (not sure why!?).  SunSpider claims this is an overall wash.

[Eric Seidel (no email)]

Created attachment 17168 [details]
Better fix (including LessNode), SunSpider claims this is 1.0% speedup

[Eric Seidel (no email)]

Created attachment 17170 [details]
Better fix (including LessNode), SunSpider claims this is > 0.5% speedup

Lots of noise on my system when running sunspider... I fixed one bug with this patch, it should be good to go now.

[Eric Seidel (no email)]

The re-write of the Bison %union was originally part of much larger parser fixes.  In later patches I decided those other fixes were not necessary and removed them.  The %union cleanup remained.  If necessary, I can pull that part from this patch.  I think the cleanup is good though.

[Eric Seidel (no email)]

One could still add AddNodeNumberLeft and AddNodeNumberRight for a probably small speedup.  These would avoid evaluateToNumber needing to fall back to evaluate for one of the values.  Currently AddNode::evaluateToNumber needs to call evaluate for both values instead of evaluateToNumber (at least to avoid branching).

[Darin Adler]

Comment on attachment 17170 [details]
Better fix (including LessNode), SunSpider claims this is > 0.5% speedup

You have this expression in a few places:

    const JSValue*&

If this is an out parameter of a JSValue*, it should be JSValue*&. The const doesn't make sense in this case.

I'm a little concerned about adding m_expectedReturnType to every Node -- isn't that going to make the node tree significantly bigger? If we are going to add it perhaps it could go in ExpressionNode rather than Node?

You'll also need to merge this with my evaluateToBoolean change.

+    NullNode() KJS_FAST_CALL { m_expectedReturnType = NullType; }

The base class constructor should take this type as a parameter. Otherwise, we're setting m_expectedReturnType twice, once in the base class constructor and once in the derived class.

Otherwise looks good.

[Eric Seidel (no email)]

(In reply to comment #7)
> (From update of attachment 17170 [details] [edit])
> You have this expression in a few places:
> 
>     const JSValue*&

> If this is an out parameter of a JSValue*, it should be JSValue*&. The const
> doesn't make sense in this case.

I agree.  I did it to allow returning "this" from getPrimitiveNumber (which is const), but better would have been to just remove the const on getPrimitiveNumber.

> I'm a little concerned about adding m_expectedReturnType to every Node -- isn't
> that going to make the node tree significantly bigger? If we are going to add
> it perhaps it could go in ExpressionNode rather than Node?

I put it on node so it could be a bit field.  I reduced the size of m_line by 3 bits, so it should be fine.

> You'll also need to merge this with my evaluateToBoolean change.
> 
> +    NullNode() KJS_FAST_CALL { m_expectedReturnType = NullType; }
> 
> The base class constructor should take this type as a parameter. Otherwise,
> we're setting m_expectedReturnType twice, once in the base class constructor
> and once in the derived class.

Yeah, I had that initially.  I can't remember why I didn't use it in the end.

[Eric Seidel (no email)]

(In reply to comment #8)
> (In reply to comment #7)
> > (From update of attachment 17170 [details] [edit] [edit])
> > You'll also need to merge this with my evaluateToBoolean change.
> > 
> > +    NullNode() KJS_FAST_CALL { m_expectedReturnType = NullType; }
> > 
> > The base class constructor should take this type as a parameter. Otherwise,
> > we're setting m_expectedReturnType twice, once in the base class constructor
> > and once in the derived class.
> 
> Yeah, I had that initially.  I can't remember why I didn't use it in the end.

Ah, so why I did this is that due to the fact that m_expectedReturnType is on Node instead of ExpressionNode (so it can be part of the bitfield and not bloat Node/ExpressionNode any).  Node() would need to take an extra parameter which makes no sense for StatementNode.  I could have a second protected constructor which took the return type... neither way is particularly pretty, but I guess the second protected constructor is "faster".

[Eric Seidel (no email)]

Created attachment 17181 [details]
Patch updated to TOT and addressing Darin's concerns

[Darin Adler]

Comment on attachment 17181 [details]
Patch updated to TOT and addressing Darin's concerns

 269 __ZN3KJS8JSObject18getPrimitiveNumberEPNS_9ExecStateERdRPNS_7JSValueE

Why does this need to be exported? Who calls it outside JavaScriptCore?

 925     // Both are objects (or unknown) -- fixme: this is kinda an inefficient way to get here.

I don't understand that comment, and the format seems strange.

 1928     double n2 = term2->evaluateToNumber(exec);
 1929     KJS_CHECKEXCEPTIONNUMBER
 1930     
 1931     return n1 + n2;

I don't think you really need this exception check here since it's the last call to evaluate in another evaluate. The inner evaluate will already have attached the file and line number and there's no need to optimize out the addition.

 1949     JSValue* v2 = term2->evaluate(exec);
 1950     KJS_CHECKEXCEPTIONVALUE

Same here.

 2134     KJS_CHECKEXCEPTIONVALUE
 2135     return jsBoolean(n1 < n2);

And here.

 2143     KJS_CHECKEXCEPTIONVALUE
 2144     return jsBoolean(static_cast<StringImp*>(v1)->value() < static_cast<StringImp*>(v2)->value());

and here.

 121     JSType expectedReturnType() const KJS_FAST_CALL { return m_expectedReturnType; }

Shouldn't this function move into ExpressionNode? I know that currently every Node has m_expectedReturnType, but it would be nice not to make the promise for the future.

 160     JSType m_expectedReturnType : 3;

I think to make this work properly on Windows this needs to be unsigned, not JSType.

 253       JSValue* m_value; // This is not a real JSValue, only ever a JSImmediate, thus no ProtectedPtr

I would word it as "never a JSCell", rather than "not a real JSValue".

I don't understand the line of code in the LocalVarTypeOfNode constructor that sets m_expectedReturnType to StringType. Isn't it guaranteed to already be StringType?

It seems AddNodeNumbers should be AddNumberNode, and AddNodeStrings should be AddStringsNode. For AddNodeStringLeft and AddNodeStringRight, AddStringLeftNode and AddStringRightNode are not great names, but probably OK unless we can think of something better.

r=me as long as you fix the m_expectedReturnType issue.

[Eric Seidel (no email)]

Darin and I discussed all the final changes over IRC.

[Eric Seidel (no email)]

r27695

[Eric Seidel (no email)]

I ran the tests again when landing, and found SunSpider actually reported the final patch as a 1.1% speedup.