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.
Created attachment 433739 [details] Patch
Created attachment 433744 [details] Patch Fix style nitpicks
<rdar://problem/81064637>
Created attachment 434786 [details] Patch
Created attachment 442200 [details] Patch just rebased.
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?
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.
Created attachment 444781 [details] Patch
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].