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

• 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.

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

Depends on D80569

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

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.

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

== 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

== 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

(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.

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.

(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

See comment 9 for the simularity alerts.

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.