Bug 228052 - AirFixObviousSpills should be optimized
Summary: AirFixObviousSpills should be optimized
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Robin Morisset
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2021-07-17 19:46 PDT by Robin Morisset
Modified: 2021-11-19 01:38 PST (History)
8 users (show)

See Also:


Attachments
Patch (10.77 KB, patch)
2021-07-17 19:54 PDT, Robin Morisset
no flags Details | Formatted Diff | Diff
Patch (10.79 KB, patch)
2021-07-17 20:14 PDT, Robin Morisset
ews-feeder: commit-queue-
Details | Formatted Diff | Diff
Patch (10.87 KB, patch)
2021-08-02 12:48 PDT, Robin Morisset
ews-feeder: commit-queue-
Details | Formatted Diff | Diff
Patch (10.89 KB, patch)
2021-10-22 14:27 PDT, Robin Morisset
ysuzuki: review+
Details | Formatted Diff | Diff
Patch (10.93 KB, patch)
2021-11-18 22:14 PST, Robin Morisset
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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].