Bug 1647520 Part 4 - Stop binary search once the feasible and infeasible block-size is within one device pixel. r=heycam
authorTing-Yu Lin <tlin@mozilla.com>
Mon, 20 Jul 2020 22:28:45 +0000
changeset 541376 19047c90effa4666c26ea57cafe40b2df3a76aef
parent 541375 d6ce5fef610a01d6479b9193d19835baadac4149
child 541377 e369d25873ad9d13122b6a740a2ac5ef5a9d2804
push id122202
push useraethanyc@gmail.com
push dateMon, 20 Jul 2020 23:04:12 +0000
treeherderautoland@19047c90effa [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersheycam
bugs1647520
milestone80.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1647520 Part 4 - Stop binary search once the feasible and infeasible block-size is within one device pixel. r=heycam The gist of this patch is: once the feasible and infeasible block-size is within one device pixel, we choose nextGuess to be the greatest multiple of one device pixel below or equal to the feasible block-size. If this nextGuess is infeasible, we will reflow children one last time by using the last feasible block-size and done with the balancing. Differential Revision: https://phabricator.services.mozilla.com/D83732
layout/generic/nsColumnSetFrame.cpp
--- a/layout/generic/nsColumnSetFrame.cpp
+++ b/layout/generic/nsColumnSetFrame.cpp
@@ -991,28 +991,33 @@ void nsColumnSetFrame::FindBestBalanceBS
   // aConfig.knownFeasibleBSize - aConfig.knownInfeasibleBSize decreases in
   // every iteration.
   int32_t iterationCount = 1;
 
   // We set this flag when we detect that we may contain a frame
   // that can break anywhere (thus foiling the linear decrease-by-one
   // search)
   bool maybeContinuousBreakingDetected = false;
+  bool possibleOptimalBSizeDetected = false;
 
   // This is the extra block-size added to the optimal column block-size
   // estimation which is calculated in the while-loop by dividing
   // aColData.mSumBSize into N columns.
   //
   // The constant is arbitrary. We use a half of line-height first.
   nscoord extraBlockSize = aReflowInput.CalcLineHeight() / 2;
 
   // We use divide-by-N to estimate the optimal column block-size only if the
   // last column's available block-size is unbounded.
   bool foundFeasibleBSizeCloserToBest = !aUnboundedLastColumn;
 
+  // Stop the binary search when the difference of the feasible and infeasible
+  // block-size is within this gap. Here we use one device pixel.
+  const int32_t gapToStop = aPresContext->DevPixelsToAppUnits(1);
+
   while (!aPresContext->HasPendingInterrupt()) {
     nscoord lastKnownFeasibleBSize = aConfig.mKnownFeasibleBSize;
 
     // Record what we learned from the last reflow
     if (aColData.mFeasible) {
       // mMaxBSize is feasible. Also, mLastBalanceBSize is feasible.
       aConfig.mKnownFeasibleBSize =
           std::min(aConfig.mKnownFeasibleBSize, aColData.mMaxBSize);
@@ -1062,25 +1067,32 @@ void nsColumnSetFrame::FindBestBalanceBS
     }
 
     if (aConfig.mKnownInfeasibleBSize >= availableContentBSize) {
       // There's no feasible block-size to fit our contents. We may need to
       // reflow one more time after this loop.
       break;
     }
 
+    const nscoord gap =
+        aConfig.mKnownFeasibleBSize - aConfig.mKnownInfeasibleBSize;
+    if (gap <= gapToStop && possibleOptimalBSizeDetected) {
+      // We detected a possible optimal block-size in the last iteration. If it
+      // is infeasible, we may need to reflow one more time after this loop.
+      break;
+    }
+
     if (lastKnownFeasibleBSize - aConfig.mKnownFeasibleBSize == 1) {
       // We decreased the feasible block-size by one twip only. This could
       // indicate that there is a continuously breakable child frame
       // that we are crawling through.
       maybeContinuousBreakingDetected = true;
     }
 
-    nscoord nextGuess =
-        (aConfig.mKnownFeasibleBSize + aConfig.mKnownInfeasibleBSize) / 2;
+    nscoord nextGuess = aConfig.mKnownInfeasibleBSize + gap / 2;
     if (aConfig.mKnownFeasibleBSize - nextGuess < extraBlockSize &&
         !maybeContinuousBreakingDetected) {
       // We're close to our target, so just try shrinking just the
       // minimum amount that will cause one of our columns to break
       // differently.
       nextGuess = aConfig.mKnownFeasibleBSize - 1;
     } else if (!foundFeasibleBSizeCloserToBest) {
       // Make a guess by dividing mSumBSize into N columns and adding
@@ -1092,17 +1104,23 @@ void nsColumnSetFrame::FindBestBalanceBS
       // We keep doubling extraBlockSize in every iteration until we find a
       // feasible guess.
       extraBlockSize *= 2;
     } else if (aConfig.mKnownFeasibleBSize == NS_UNCONSTRAINEDSIZE) {
       // This can happen when we had a next-in-flow so we didn't
       // want to do an unbounded block-size measuring step. Let's just increase
       // from the infeasible block-size by some reasonable amount.
       nextGuess = aConfig.mKnownInfeasibleBSize * 2 + extraBlockSize;
+    } else if (gap <= gapToStop) {
+      // Floor nextGuess to the greatest multiple of gapToStop below or equal to
+      // mKnownFeasibleBSize.
+      nextGuess = aConfig.mKnownFeasibleBSize / gapToStop * gapToStop;
+      possibleOptimalBSizeDetected = true;
     }
+
     // Don't bother guessing more than our block-size constraint.
     nextGuess = std::min(availableContentBSize, nextGuess);
 
     COLUMN_SET_LOG("%s: Choosing next guess=%d, iteration=%d", __func__,
                    nextGuess, iterationCount);
     ++iterationCount;
 
     aConfig.mColMaxBSize = nextGuess;