1647332 - Use a better first guess to reduce the range for the binary search in column balancing

Status: RESOLVED FIXED

(Core :: Layout: Columns, enhancement)

Description

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Currently, our column balancing algorithm can set a reasonable small range of infeasible bsize (lower bound) and feasible bsize (upper bound) in the second iteration [1] if it guesses a feasible bsize in the first iteration. However, if the first guess is infeasible, the lower becomes the first guess bsize, but the upper bound remains the sum of all the content's bsize [2] because we measure the total content bsize via unconstrainted available bsize prior to balancing the columns). That leaves us a much broader range for the binary search to converge.

heycam noticed that the infeasible first guess can be easily observed by opening a wikipeda page that has a large "Reference" section such as [3]. On my screen resolution, the column container containing those references is about 1683px wide and is laid in into four columns. The balancing algorithm takes 15 iterations to find the optimal bsize.

heycam suggested we can use a better first guess than a fixed 600 app units [4] to reduce the rate of failed first guess.

[1] https://searchfox.org/mozilla-central/rev/1304678d837c17811617754fd446794b774afe94/layout/generic/nsColumnSetFrame.cpp#1005-1018
[2] https://searchfox.org/mozilla-central/rev/1304678d837c17811617754fd446794b774afe94/layout/generic/nsColumnSetFrame.cpp#1020-1038
[3] https://en.wikipedia.org/wiki/Coronavirus_disease_2019
[4] https://searchfox.org/mozilla-central/rev/1304678d837c17811617754fd446794b774afe94/layout/generic/nsColumnSetFrame.cpp#1074-1077

Comment 1

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Attachment: Bug 1647332 Part 1 - Print more information in column set log.

• childContentBEnd: this value can be larger than
  kidDesiredSize.BSize(wm) if -moz-column-content anonymous blocks has a
  child which is overflow-incomplete.

• mLastBSize: last column's block-size is important in column balancing
  algorithm because it sets mKnownInfeasibleBSize when a balancing
  iteration is feasible.

• The iteration count in column balancing. This is an easy way to
  observe column balancing performance.

Comment 2

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Attachment: Bug 1647332 Part 2 - Output the number of columns in ColumnBalanceData, and replace nsFrameList::GetLength().

The motivation is to replace mFrames.GetLength() in
FindBestBalanceBSize() since it is O(N), where N is the number of
columns.

Also, counting the column number from 1 so that it matches mUsedColCount
without needing to subtract 1 at some places.

Depends on D80568

Comment 3

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Attachment: Bug 1647332 Part 3 - Extract the constant 600 app units when estimating balancing column block-size.

Depends on D80569

Comment 4

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Attachment: Bug 1647332 Part 4 - Keep doubling the extra block-size that adds to the estimate column block-size until finding a feasible one.

In FindBestBalanceBSize(), suppose we have aUnboundedLastColumn equals
to true, and the measuring reflow of all the columns is feasible. This
setting represents the most common scenario of multi-column layout as
the multi-column footnote on Wikipedia.

We used to use 600 as the extra block-size added to the estimate column
block-size. However, if the first guess of the column block-size, say
G1, is infeasible, the feasible block-size is still bound to the sum of
all columns S. That leaves us a massive range between G1 and S to
search.

We don't want to use a larger fixed extra block-size. Although it can
reduce the possibility of failing the first guess, but for cases where a
smaller extra block-size is sufficient, it increases the search range
and the iteration number before the binary search converges.

Instead, we can spend the first few iterations doubling the extra
block-size E added to the estimate column block-size until we find the
first feasible block-size. This gives us a smaller upper bound S / N +
E, where N is the number of columns.

Depends on D80570

Comment 5

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Note: With my patches, the number of iteration should probably the same if the first guess is correct since I use half of the line-height as a start. The default line-height is 19px or 1140 app units, so we'll start at 570 app units where on trunk 600 app units.

The following is the number of balancing iteration of loading https://en.wikipedia.org/wiki/Coronavirus_disease_2019 as of writing this comment. The line-height is 1210 app units.

./mach run with windows maximized, where the "Reference" section is laid out in 4 columns

• trunk: 15 iterations (first guess failed)
• With my patches: 9 iterations (the guess becomes feasible in iteration 3, where the extraBlockSize (see patch D80571) used in iteration 1, 2, 3 are 605, 1210, 2420, respectively.

Comment 6

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/0443a7d3c6d3
Part 1 - Print more information in column set log. r=heycam
https://hg.mozilla.org/integration/autoland/rev/c8183555a356
Part 2 - Output the number of columns in ColumnBalanceData, and replace nsFrameList::GetLength(). r=heycam
https://hg.mozilla.org/integration/autoland/rev/f80f7cbfc7c3
Part 3 - Extract the constant 600 app units when estimating balancing column block-size. r=heycam
https://hg.mozilla.org/integration/autoland/rev/91c26c5b1e33
Part 4 - Keep doubling the extra block-size that adds to the estimate column block-size until finding a feasible one. r=heycam

Comment 7

[Alexandru Michis [:malexandru]]

https://hg.mozilla.org/mozilla-central/rev/0443a7d3c6d3
https://hg.mozilla.org/mozilla-central/rev/c8183555a356
https://hg.mozilla.org/mozilla-central/rev/f80f7cbfc7c3
https://hg.mozilla.org/mozilla-central/rev/91c26c5b1e33

Comment 8

[Florin Strugariu [:Bebe]]

== Change summary for alert #26332 (as of Thu, 25 Jun 2020 08:23:16 GMT) ==

Regressions:

2% raptor-tp6-yahoo-mail-firefox-cold confidence windows7-32-shippable opt 74.92 -> 73.25

Improvements:

18% raptor-tp6-slides-firefox-cold loadtime windows10-64-shippable opt 2,324.58 -> 1,916.08
17% raptor-tp6-slides-firefox-cold loadtime windows7-32-shippable opt 2,260.50 -> 1,884.17
14% raptor-assorted-dom-firefox linux64-shippable opt 28.50 -> 24.40
11% raptor-tp6-wikipedia-firefox-cold windows7-32-shippable opt 1,460.04 -> 1,297.86
11% raptor-tp6-wikipedia-firefox-cold loadtime windows7-32-shippable opt 1,629.92 -> 1,458.83
10% raptor-tp6-wikipedia-firefox-cold windows10-64-shippable opt 1,400.36 -> 1,259.17
10% raptor-tp6-wikipedia-firefox-cold loadtime windows10-64-shippable opt 1,577.42 -> 1,421.08
10% raptor-tp6-wikipedia-firefox-cold fcp windows10-64-shippable opt 1,343.50 -> 1,211.00
10% raptor-tp6-wikipedia-firefox-cold fcp windows7-32-shippable opt 1,384.33 -> 1,248.42
4% raptor-tp6-slides-firefox-cold windows10-64-shippable opt 813.71 -> 780.83

For up to date results, see: https://treeherder.mozilla.org/perf.html#/alerts?id=26332

Comment 9

[Florin Strugariu [:Bebe]]

== Change summary for alert #26349 (as of Fri, 26 Jun 2020 11:38:20 GMT) ==

Improvements:

182% bing-search-restaurants Similarity2D android-hw-p2-8-0-android-aarch64-shippable opt cold 0.34 -> 0.96
171% bing-search-restaurants Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.36 -> 0.98
166% bing-search-restaurants Similarity android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.37 -> 0.99
158% reddit Similarity android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.31 -> 0.80
125% booking Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.44 -> 1.00
94% bing-search-restaurants Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.52 -> 1.00
82% youtube-watch Similarity android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.41 -> 0.74
65% google-maps Similarity android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.61 -> 1.00
59% booking Similarity android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.62 -> 0.99
58% google Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.61 -> 0.97
52% reddit Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.66 -> 1.00
52% google-maps Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.66 -> 1.00
49% google Similarity2D android-hw-p2-8-0-android-aarch64-shippable opt cold 0.63 -> 0.94
47% google-maps Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.67 -> 0.99
47% google-maps Similarity2D android-hw-p2-8-0-android-aarch64-shippable opt cold 0.68 -> 0.99
44% google Similarity android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.69 -> 0.99
44% google Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.69 -> 1.00
37% facebook Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.73 -> 1.00
37% youtube-watch Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.73 -> 1.00
35% facebook Similarity android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.73 -> 0.99
32% facebook Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.73 -> 0.96
29% instagram Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.75 -> 0.96
28% instagram Similarity2D android-hw-p2-8-0-android-aarch64-shippable opt cold 0.76 -> 0.97
25% facebook Similarity2D android-hw-p2-8-0-android-aarch64-shippable opt cold 0.74 -> 0.93
24% booking Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.79 -> 0.99
22% youtube-watch Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.62 -> 0.76
19% booking Similarity2D android-hw-p2-8-0-android-aarch64-shippable opt cold 0.83 -> 0.99
13% wikipedia Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.86 -> 0.97
11% cnn-ampstories Similarity android-hw-p2-8-0-android-aarch64-shippable opt cold 0.89 -> 0.98
9% wikipedia Similarity android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.91 -> 0.99
8% wikipedia Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.92 -> 0.99
5% cnn-ampstories Similarity2D android-hw-p2-8-0-android-aarch64-shippable opt cold 0.95 -> 1.00
4% cnn-ampstories Similarity2D android-hw-g5-7-0-arm7-api-16-shippable opt cold 0.96 -> 1.00

For up to date results, see: https://treeherder.mozilla.org/perf.html#/alerts?id=26349

Comment 10

[Dave Hunt [:davehunt] [he/him] ⌚BST]

(In reply to Florin Strugariu [:Bebe] (needinfo me) from comment #8)

== Change summary for alert #26332 (as of Thu, 25 Jun 2020 08:23:16 GMT) ==

Regressions:

2% raptor-tp6-yahoo-mail-firefox-cold confidence windows7-32-shippable opt 74.92 -> 73.25

Improvements:

18% raptor-tp6-slides-firefox-cold loadtime windows10-64-shippable opt 2,324.58 -> 1,916.08
17% raptor-tp6-slides-firefox-cold loadtime windows7-32-shippable opt 2,260.50 -> 1,884.17
14% raptor-assorted-dom-firefox linux64-shippable opt 28.50 -> 24.40
11% raptor-tp6-wikipedia-firefox-cold windows7-32-shippable opt 1,460.04 -> 1,297.86
11% raptor-tp6-wikipedia-firefox-cold loadtime windows7-32-shippable opt 1,629.92 -> 1,458.83
10% raptor-tp6-wikipedia-firefox-cold windows10-64-shippable opt 1,400.36 -> 1,259.17
10% raptor-tp6-wikipedia-firefox-cold loadtime windows10-64-shippable opt 1,577.42 -> 1,421.08
10% raptor-tp6-wikipedia-firefox-cold fcp windows10-64-shippable opt 1,343.50 -> 1,211.00
10% raptor-tp6-wikipedia-firefox-cold fcp windows7-32-shippable opt 1,384.33 -> 1,248.42
4% raptor-tp6-slides-firefox-cold windows10-64-shippable opt 813.71 -> 780.83

For up to date results, see: https://treeherder.mozilla.org/perf.html#/alerts?id=26332

:sparky should we be alerting on similarity? Is improvement/regression appropriate for changes to this test? This could be misleading.

Comment 11

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Attachment: Bug 1647332 - Provide a minimum starting value for extraBlockSize in FindBestBalanceBSize.

Comment 12

[Phabricator Automation]

Comment on attachment 9170116 [details]
Bug 1647332 - Provide a minimum starting value for extraBlockSize in FindBestBalanceBSize.

Revision D87131 was moved to bug 1658198. Setting attachment 9170116 [details] to obsolete.

Comment 13

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

Re comment 10:

bug 1658198 comment 22 has a theory on why certain pages can be very slow, but in general the page matching the behavior described in comment 0 should become faster.

Comment 14

[Greg Mierzwinski [:sparky]]

(In reply to Dave Hunt [:davehunt] [he/him] ⌚BST from comment #10)

(In reply to Florin Strugariu [:Bebe] (needinfo me) from comment #8)

== Change summary for alert #26332 (as of Thu, 25 Jun 2020 08:23:16 GMT) ==

Regressions:

2% raptor-tp6-yahoo-mail-firefox-cold confidence windows7-32-shippable opt 74.92 -> 73.25

Improvements:

18% raptor-tp6-slides-firefox-cold loadtime windows10-64-shippable opt 2,324.58 -> 1,916.08
17% raptor-tp6-slides-firefox-cold loadtime windows7-32-shippable opt 2,260.50 -> 1,884.17
14% raptor-assorted-dom-firefox linux64-shippable opt 28.50 -> 24.40
11% raptor-tp6-wikipedia-firefox-cold windows7-32-shippable opt 1,460.04 -> 1,297.86
11% raptor-tp6-wikipedia-firefox-cold loadtime windows7-32-shippable opt 1,629.92 -> 1,458.83
10% raptor-tp6-wikipedia-firefox-cold windows10-64-shippable opt 1,400.36 -> 1,259.17
10% raptor-tp6-wikipedia-firefox-cold loadtime windows10-64-shippable opt 1,577.42 -> 1,421.08
10% raptor-tp6-wikipedia-firefox-cold fcp windows10-64-shippable opt 1,343.50 -> 1,211.00
10% raptor-tp6-wikipedia-firefox-cold fcp windows7-32-shippable opt 1,384.33 -> 1,248.42
4% raptor-tp6-slides-firefox-cold windows10-64-shippable opt 813.71 -> 780.83

For up to date results, see: https://treeherder.mozilla.org/perf.html#/alerts?id=26332

:sparky should we be alerting on similarity? Is improvement/regression appropriate for changes to this test? This could be misleading.

The similarity metric isn't mentioned here (since it's only available for browsertime), but the network request confidence is. We shouldn't be alerting on that and given that it's been 2 months since this alert was posted, it was before our recent changes which disabled alerting on confidence: https://searchfox.org/mozilla-central/source/testing/raptor/raptor/webextension/base.py#160

Comment 15

[Dave Hunt [:davehunt] [he/him] ⌚BST]

See comment 9 for the simularity alerts.

Comment 16

[Greg Mierzwinski [:sparky]]

Ah that's so cool! I missed that.

Yes we should definitely alert on changes in that metric. It's a catch-all that tells us something (but not what) changed between the last run and the current test run. That said, the alert, as seen in the graph, is very wrong and is pointing to the wrong commit (but the alert was attributed to the correct bug any way): https://treeherder.mozilla.org/perf.html#/graphs?highlightAlerts=1&selected=2474228,1176401295&series=autoland,2474228,1,13&timerange=7776000&zoom=1592817650698,1593042553403,0.576168903327493,1.1440993935235717

What the graph for this metric tells us is that a patch landed and it made our perf pageload tests very, and consistently, unstable (plus they are different from before the patch that caused the regression). Then the patch in this bug landed, and our pageload tests stabilized and provide more consistent results now.