Bug 158892 - Switching on symbols should be fast
Summary: Switching on symbols should be fast
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2016-06-17 15:58 PDT by Filip Pizlo
Modified: 2016-07-21 02:43 PDT (History)
10 users (show)

See Also:


Attachments
something like this (12.98 KB, patch)
2016-06-17 15:59 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
maybe the patch (30.54 KB, patch)
2016-06-18 16:44 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
better patch (27.34 KB, patch)
2016-06-19 12:56 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
awesome patch (27.34 KB, patch)
2016-06-25 20:10 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
patch (29.76 KB, patch)
2016-06-25 20:12 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (29.87 KB, patch)
2016-07-18 22:43 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (30.69 KB, patch)
2016-07-18 22:54 PDT, Filip Pizlo
fpizlo: review-
Details | Formatted Diff | Diff
the patch (41.89 KB, patch)
2016-07-19 00:16 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (63.76 KB, patch)
2016-07-19 13:18 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
performance (80.31 KB, text/plain)
2016-07-19 15:09 PDT, Filip Pizlo
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2016-06-17 15:58:10 PDT
Patch forthcoming.
Comment 1 Filip Pizlo 2016-06-17 15:59:35 PDT
Created attachment 281595 [details]
something like this
Comment 2 Filip Pizlo 2016-06-18 16:44:03 PDT
Created attachment 281620 [details]
maybe the patch

This does the trick.

What's sad about this is that this optimization really belongs in lower tiers, but currently it's not feasible to do it in DFG IR.  You really need B3 IR to do it.  But without the optimization, the code runs so incredibly slow that it takes a long time to get to FTL.

It's starting to become quite clear that we need tier-up checks in straight-line code.
Comment 3 Filip Pizlo 2016-06-19 12:56:05 PDT
Created attachment 281622 [details]
better patch
Comment 4 Filip Pizlo 2016-06-19 16:46:51 PDT
Looks like this has a bug:

stress/float64-array-nan-inlined.js.default: test_script_12303: line 2: 55586 Segmentation fault: 11  ( "$@" ../../.vm/JavaScriptCore.framework/Resources/jsc --useFTLJIT\=false --useFunctionDotArguments\=true float64-array-nan-inlined.js )
stress/float64-array-nan-inlined.js.default: ERROR: Unexpected exit code: 139

Maybe it's latent so I'm still testing without the patch.
Comment 5 Filip Pizlo 2016-06-19 17:09:23 PDT
(In reply to comment #4)
> Looks like this has a bug:
> 
> stress/float64-array-nan-inlined.js.default: test_script_12303: line 2:
> 55586 Segmentation fault: 11  ( "$@"
> ../../.vm/JavaScriptCore.framework/Resources/jsc --useFTLJIT\=false
> --useFunctionDotArguments\=true float64-array-nan-inlined.js )
> stress/float64-array-nan-inlined.js.default: ERROR: Unexpected exit code: 139
> 
> Maybe it's latent so I'm still testing without the patch.

Wait, it has to be latent!  It's a non-FTL test and this patch only changes FTL.
Comment 6 Filip Pizlo 2016-06-20 15:23:57 PDT
(In reply to comment #5)
> (In reply to comment #4)
> > Looks like this has a bug:
> > 
> > stress/float64-array-nan-inlined.js.default: test_script_12303: line 2:
> > 55586 Segmentation fault: 11  ( "$@"
> > ../../.vm/JavaScriptCore.framework/Resources/jsc --useFTLJIT\=false
> > --useFunctionDotArguments\=true float64-array-nan-inlined.js )
> > stress/float64-array-nan-inlined.js.default: ERROR: Unexpected exit code: 139
> > 
> > Maybe it's latent so I'm still testing without the patch.
> 
> Wait, it has to be latent!  It's a non-FTL test and this patch only changes
> FTL.

Yeah, it was an unrelated bug, and I fixed it.
Comment 7 Filip Pizlo 2016-06-25 20:10:17 PDT
Created attachment 282086 [details]
awesome patch
Comment 8 Filip Pizlo 2016-06-25 20:12:23 PDT
Created attachment 282087 [details]
patch
Comment 9 Filip Pizlo 2016-07-18 22:43:51 PDT
Created attachment 283979 [details]
the patch
Comment 10 Filip Pizlo 2016-07-18 22:54:38 PDT
Created attachment 283980 [details]
the patch
Comment 11 Filip Pizlo 2016-07-18 23:06:18 PDT
Comment on attachment 283980 [details]
the patch

Oh man, this doesn't quite work!  Fixing...
Comment 12 Filip Pizlo 2016-07-19 00:16:01 PDT
Created attachment 283981 [details]
the patch
Comment 13 Saam Barati 2016-07-19 00:23:33 PDT
Comment on attachment 283981 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=283981&action=review

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:439
> +            // put them. We're not actually smart enough things to move things around at random.

"smart enough things" => "smart enough"

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:466
> +            if (m_blockInsertionSet.execute() | m_changedCFG) {

Should be "||"
Comment 14 Filip Pizlo 2016-07-19 10:11:21 PDT
(In reply to comment #13)
> Comment on attachment 283981 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=283981&action=review
> 
> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:439
> > +            // put them. We're not actually smart enough things to move things around at random.
> 
> "smart enough things" => "smart enough"

Fixed.

> 
> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:466
> > +            if (m_blockInsertionSet.execute() | m_changedCFG) {
> 
> Should be "||"

That was sort of deliberate.  I wanted to emphasize that every subexpression should execute for side-effects.  I changed it to:

m_changedCFG |= m_blockInsertionSet.execute();
if (m_changedCFG) {
Comment 15 Filip Pizlo 2016-07-19 13:18:46 PDT
Created attachment 284037 [details]
the patch
Comment 16 Filip Pizlo 2016-07-19 15:09:25 PDT
Created attachment 284059 [details]
performance
Comment 17 Keith Miller 2016-07-20 12:26:16 PDT
Comment on attachment 284037 [details]
the patch

r=me. Out of curiosity does this optimization kick in if the user doesn't write a switch explicitly? If so, maybe it would be worth adding a test. For example:

if (a === sym1)
    ...
if (a === sym2)
    ...
...
Comment 18 Filip Pizlo 2016-07-20 19:28:46 PDT
(In reply to comment #17)
> Comment on attachment 284037 [details]
> the patch
> 
> r=me. Out of curiosity does this optimization kick in if the user doesn't
> write a switch explicitly? If so, maybe it would be worth adding a test. For
> example:
> 
> if (a === sym1)
>     ...
> if (a === sym2)
>     ...
> ...

It does kick in for this!  Good idea, I will add a test for it.
Comment 19 Filip Pizlo 2016-07-20 22:42:02 PDT
(In reply to comment #18)
> (In reply to comment #17)
> > Comment on attachment 284037 [details]
> > the patch
> > 
> > r=me. Out of curiosity does this optimization kick in if the user doesn't
> > write a switch explicitly? If so, maybe it would be worth adding a test. For
> > example:
> > 
> > if (a === sym1)
> >     ...
> > if (a === sym2)
> >     ...
> > ...
> 
> It does kick in for this!  Good idea, I will add a test for it.

Yeah, I wrote a test like this - basically a scripted rewrite of bigswitch-indirect-symbol to use if - and it gets a speed-up from this patch.
Comment 20 Filip Pizlo 2016-07-20 23:24:23 PDT
Landed in https://trac.webkit.org/changeset/203491