Bug 15879

Summary: Add evaluateToNumber fast path for numeric operations
Product: WebKit Reporter: Eric Seidel <eric@webkit.org>
Component: JavaScriptCoreAssignee: Eric Seidel <eric@webkit.org>
Status: RESOLVED FIXED    
Severity: Normal    
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Macintosh   
OS: Mac OS X 10.4   
Bug Depends on:    
Bug Blocks: 15884    
Attachments:
Description Flags
naive patch
none
Improved patch, still a wash for SunSpider
none
Improved patch, 0.7% improvement for Sunspider
darin: review+
patch addressing darin's concerns
none
patch ready for final review and landing oliver: review+

Description From 2007-11-07 00:06:59 PST
Add evaluateToNumber fast path for numeric operations

I've created a naive/first-cut, patch which I'm about to attach.

The idea is adding an evaluateToNumber() method which returns a double instead of a JSValue*.  In the default Node case, it just calls evaluate() followed by toNumber(), for nodes which already have a number (or deal exclusively with numbers) they can just avoid having their entire subtree ever touch any JSValue code, and instead deal only with doubles. :)

Sadly, my first-cut is a slowdown.
------- Comment #1 From 2007-11-07 00:08:35 PST -------
Created an attachment (id=17101) [details]
naive patch
------- Comment #2 From 2007-11-07 00:13:11 PST -------
One possible reason for the slowdown is the extra hadException() checks now after every toNumber() call (which we were previously missing, see bug 15878).  If I wanted this to only check as much as the old code, I would remove all KJS_CHECKHADEXCEPTIONVALUE calls directly following any evaluateToNumber() call.  Still investigating.
------- Comment #3 From 2007-11-07 01:25:20 PST -------
Created an attachment (id=17102) [details]
Improved patch, still a wash for SunSpider

For many tests this is a speedup, for a few though (like frannkuch) it's a slowdown (there 2.5%).  I think most of that is due to Node::evaluateToNumber() which not only adds a hadException check to places where it wasn't necessarily before, but *more importantly* is a virtual call in the first place.  So we end up making two virtual calls.  One way to get rid of that cost would be to have further deployment of the evaluteToNumber() technique.  LessNode is one example where I haven't yet tried.  Also all the ReadModifyAssignment nodes could use a evaluateToNumber() implementation.  All of the places where we currently deal with uints and ints instead of doubles could also benefit from evaluateToNumber usage so long as there are functions in JSImmediate.h to convert from double -> int/uint (and assuming that toNumber()->toWhateverTypeOfInt() is equivalent to the current behavior.
------- Comment #4 From 2007-11-07 02:12:07 PST -------
Created an attachment (id=17106) [details]
Improved patch, 0.7% improvement for Sunspider

I'm more interested in comments than I am a +/-.  It think this patch could probably still use some tweaking.

One thing I've considered is adding a non-virtual inlineEvaluateToNumber(ExecState*) call to certain nodes, which both evaluate() and evaluateToNumber() can use.  It would need to be a class method, which hopefully the compiler would be smart enough to inline.  Maybe I should just make it a static inline and pass "this" along, but then I'd need to improve the exception macros and possibly other functions (which could be done).
------- Comment #5 From 2007-11-07 08:45:50 PST -------
(From update of attachment 17106 [details])
Seems clear that ImmediateNumberNode should store both forms, not just the JSValue.

And yes, it's entirely practical to use an inline for cases like BracketAccessorNode::evaluateToNumber, since it's really identical to the normal evaluate followed by toNumber, and for MultNode::evaluate, which is identical to evaluateToNumber followed by jsNumber. ALWAYS_INLINE will work for such cases.

+    if (bothTypes == ((NumberType << 3) | NumberType))
+        return v1->toNumber(exec) + v2->toNumber(exec);
+    else if (bothTypes == ((StringType << 3) | StringType)) {

Please don't use else after return.

+    i2 = right->evaluate(exec)->toInt32(exec);

Obviously this should be using evaluateToNumber, unless you're planning on adding evaluateToInt32.

My general comment is that this looks good as-is.

My only complaint is that I think that both evaluate and evaluateToNumber should be moved down out of Node to some other class, perhaps named ExpressionNode. It's really unnecessary to have those functions in classes like StatementNode and I think eventually we could get some optimizations by not having them in all nodes. For example, in some nodes they don't need to be virtual functions.

r=me, as-is -- this is good the way it is.
------- Comment #6 From 2007-11-07 10:08:28 PST -------
(In reply to comment #5)
> (From update of attachment 17106 [details] [edit])
> Seems clear that ImmediateNumberNode should store both forms, not just the
> JSValue.

Yeah.  I'll try that.

> And yes, it's entirely practical to use an inline for cases like
> BracketAccessorNode::evaluateToNumber, since it's really identical to the
> normal evaluate followed by toNumber, and for MultNode::evaluate, which is
> identical to evaluateToNumber followed by jsNumber. ALWAYS_INLINE will work for
> such cases.

I was skeptical if a function declared in the cpp file would correctly always inline, but given that the header is simply included directly in the file (and processed by the preprocessor) it shouldn't matter to the compiler where the function is, so long as it's marked ALWAYS_INLINE :)

> +    if (bothTypes == ((NumberType << 3) | NumberType))
> +        return v1->toNumber(exec) + v2->toNumber(exec);
> +    else if (bothTypes == ((StringType << 3) | StringType)) {
> 
> Please don't use else after return.

Hum... I need to go back and find that case where SunSpider seemed to show removing an else as being a slowdown, and stare at both sets of assembly to prove to myself once and for-all that the generated code is identical.  I'll definitely remove this one when I abstract that into an inline.

> +    i2 = right->evaluate(exec)->toInt32(exec);
> 
> Obviously this should be using evaluateToNumber, unless you're planning on
> adding evaluateToInt32.

As I mentioned in my above comment, we don't yet have any way to convert a double to a UInt via our fancy JSImmediate functions, I could just cast it... assuming static_cast<uint32_t>(right->evaluateToNumber(exec)) the equivilent to toInt32().  I'll check.

> My general comment is that this looks good as-is.
> 
> My only complaint is that I think that both evaluate and evaluateToNumber
> should be moved down out of Node to some other class, perhaps named
> ExpressionNode. It's really unnecessary to have those functions in classes like
> StatementNode and I think eventually we could get some optimizations by not
> having them in all nodes. For example, in some nodes they don't need to be
> virtual functions.

Yeah, I like that idea.  But that's for a separate bug.  Filed as bug 15885.

> r=me, as-is -- this is good the way it is.

I'm going to remove some of the copy-paste code and investigate the toInt32()/static_cast<uint32_t>(evaluateToNumber()) change and re-post.
------- Comment #7 From 2007-11-07 10:48:28 PST -------
(In reply to comment #6)
> (In reply to comment #5)
> > (From update of attachment 17106 [details] [edit] [edit])
> > Seems clear that ImmediateNumberNode should store both forms, not just the
> > JSValue.
> 
done, also made ImmediateNumberNode a subclass of NumberNode (much cleaner!)
> 
> > And yes, it's entirely practical to use an inline for cases like
> > BracketAccessorNode::evaluateToNumber, since it's really identical to the
> > normal evaluate followed by toNumber, and for MultNode::evaluate, which is
> > identical to evaluateToNumber followed by jsNumber. ALWAYS_INLINE will work for
> > such cases.
> 
done.
> 
> > +    if (bothTypes == ((NumberType << 3) | NumberType))
> > +        return v1->toNumber(exec) + v2->toNumber(exec);
> > +    else if (bothTypes == ((StringType << 3) | StringType)) {
> > 
> > Please don't use else after return.
> 
done
> 
> > +    i2 = right->evaluate(exec)->toInt32(exec);
> > 
> > Obviously this should be using evaluateToNumber, unless you're planning on
> > adding evaluateToInt32.
> 
A static cast is not sufficient, saving such for a later patch.

Updating patch now... and then boarding... perf testing later.
------- Comment #8 From 2007-11-07 10:49:48 PST -------
Created an attachment (id=17113) [details]
patch addressing darin's concerns

I'll mark this for official review after I land in CA.  I'm pretty sure it's ready to go though.
------- Comment #9 From 2007-11-07 23:28:15 PST -------
Woohoo 1.0% speedup.  base64 slowed down a whole 4.5% though. Obviously *lots* of fat left on this one.  I think I might try to speed up base64 before I land though.

For the curious, the speed results:
http://paste.lisp.org/display/50509
------- Comment #10 From 2007-11-07 23:44:59 PST -------
Created an attachment (id=17118) [details]
patch ready for final review and landing

This has now been perf tested.  Most everything speeds up.  base64 slows down a little, unclear why.  Shark is unhelpful, except to show that base64 seems to be mallocing a ridiculous amount of Identifiers, likely due to failed array index lookups.
------- Comment #11 From 2007-11-08 00:23:57 PST -------
Landed as r27589!  Now on to bug 15884!