Bug 228052

Summary: AirFixObviousSpills should be optimized
Product: WebKit Reporter: Robin Morisset <rmorisset>
Component: JavaScriptCoreAssignee: Robin Morisset <rmorisset>
Status: RESOLVED FIXED    
Severity: Normal CC: ews-watchlist, keith_miller, mark.lam, msaboff, saam, tzagallo, webkit-bug-importer, ysuzuki
Priority: P2 Keywords: InRadar
Version: WebKit Nightly Build   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
none
Patch
ews-feeder: commit-queue-
Patch
ews-feeder: commit-queue-
Patch
ysuzuki: review+
Patch none

Description Robin Morisset 2021-07-17 19:46:26 PDT
It has two problems:
- It visit blocks even when their state at head has not changed
- Worse, the "merge()" function on its State has quadratic time complexity
The result of these is that it is the 5th slowest phase on average in JetStream2, at 390ms on an M1 MBP (for comparison, all of Air is 2.2s and all of B3+Air is 3.3s), and we spend 105ms in it for a single function as a result of the quadratic blow-up in merge().
Both problems are fairly easy to fix.
Comment 1 Robin Morisset 2021-07-17 19:54:06 PDT
Created attachment 433739 [details]
Patch
Comment 2 Robin Morisset 2021-07-17 20:14:43 PDT
Created attachment 433744 [details]
Patch

Fix style nitpicks
Comment 3 Radar WebKit Bug Importer 2021-07-24 19:47:15 PDT
<rdar://problem/81064637>
Comment 4 Robin Morisset 2021-08-02 12:48:46 PDT
Created attachment 434786 [details]
Patch
Comment 5 Robin Morisset 2021-10-22 14:27:27 PDT
Created attachment 442200 [details]
Patch

just rebased.
Comment 6 Yusuke Suzuki 2021-11-18 11:52:32 PST
Comment on attachment 442200 [details]
Patch

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

r=me

> Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp:92
> +                    // Before we call merge we must make sure that the two states are sorted.
> +                    m_state.sort();

Do we need to call `sort()` inside this loop? Can we sort() before starting this loop?

> Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp:-568
> +                    it = std::find_if_not(it, end, [&] (const T& otherAlias) {
> +                        return otherAlias < alias;
> +                    });
> +                    if (it == end)
>                          return true;
> -                    return false;

How about using std::lower_bound or the other binary-searching since other is also sorted?
Comment 7 Robin Morisset 2021-11-18 22:13:14 PST
Thanks for the review.

> > Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp:92
> > +                    // Before we call merge we must make sure that the two states are sorted.
> > +                    m_state.sort();
> 
> Do we need to call `sort()` inside this loop? Can we sort() before starting
> this loop?

Good idea, it is a small improvement (total time 139-146ms before, 133-136ms after)

> > Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp:-568
> > +                    it = std::find_if_not(it, end, [&] (const T& otherAlias) {
> > +                        return otherAlias < alias;
> > +                    });
> > +                    if (it == end)
> >                          return true;
> > -                    return false;
> 
> How about using std::lower_bound or the other binary-searching since other
> is also sorted?

I tried this, and it turned out to be measurably slower, probably we rarely skip over enough elements of the vector to be worth the branch mispredictions.
Comment 8 Robin Morisset 2021-11-18 22:14:13 PST
Created attachment 444781 [details]
Patch
Comment 9 EWS 2021-11-19 01:38:35 PST
Committed r286053 (244440@main): <https://commits.webkit.org/244440@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 444781 [details].