Bug 15879 - Add evaluateToNumber fast path for numeric operations
Summary: Add evaluateToNumber fast path for numeric operations
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Macintosh OS X 10.4
: P2 Normal
Assignee: Eric Seidel (no email)
URL:
Keywords:
Depends on:
Blocks: 15884
  Show dependency treegraph
 
Reported: 2007-11-07 00:06 PST by Eric Seidel (no email)
Modified: 2007-11-08 00:23 PST (History)
0 users

See Also:


Attachments
naive patch (10.43 KB, patch)
2007-11-07 00:08 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
Improved patch, still a wash for SunSpider (18.48 KB, patch)
2007-11-07 01:25 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
Improved patch, 0.7% improvement for Sunspider (22.24 KB, patch)
2007-11-07 02:12 PST, Eric Seidel (no email)
darin: review+
Details | Formatted Diff | Diff
patch addressing darin's concerns (26.93 KB, patch)
2007-11-07 10:49 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
patch ready for final review and landing (29.50 KB, patch)
2007-11-07 23:44 PST, Eric Seidel (no email)
oliver: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Eric Seidel (no email) 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 Eric Seidel (no email) 2007-11-07 00:08:35 PST
Created attachment 17101 [details]
naive patch
Comment 2 Eric Seidel (no email) 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 Eric Seidel (no email) 2007-11-07 01:25:20 PST
Created attachment 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 Eric Seidel (no email) 2007-11-07 02:12:07 PST
Created attachment 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 Darin Adler 2007-11-07 08:45:50 PST
Comment on attachment 17106 [details]
Improved patch, 0.7% improvement for Sunspider

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 Eric Seidel (no email) 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 Eric Seidel (no email) 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 Eric Seidel (no email) 2007-11-07 10:49:48 PST
Created attachment 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 Eric Seidel (no email) 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 Eric Seidel (no email) 2007-11-07 23:44:59 PST
Created attachment 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 Eric Seidel (no email) 2007-11-08 00:23:57 PST
Landed as r27589!  Now on to bug 15884!