Repository: GoogleChrome/lighthouse
Pull request #7130 (2019-02-01 02:07:17)

core: optimize tap-targets audit
Optimize the tap-targets audit for pages with a large number of tap targets. Many pages don't hit a problem, but searching for the [longest wikipedia pages](https://en.wikipedia.org/wiki/Special:LongPages) found https://en.wikipedia.org/wiki/List_of_2017_albums, which takes 18s to process in the current audit. That might seem kind of unreasonable as a test, but as we've discovered from some of our axe timeouts, people do indeed make and then test pages with giganto tables of links.

Some results:
**avclub**
before: 87.30 ms
after: 10.80 ms

[**https://github.com/GoogleChrome/lighthouse/pull/5846**](https://github.com/GoogleChrome/lighthouse/pull/5846)
before: 99.22 ms
after: 22.86 ms

**https://en.wikipedia.org/wiki/List_of_2017_albums**
before: 18,772.44 ms
after: 502.01 ms

(numbers updated from changes after feedback/bug fix)

Note that I was optimizing for a page with a ton of non-overlapping tap targets. There may still be some important asymptotic behavior of overlapping targets to optimize, but I couldn't find a good example page.

The primary optimization was to hoist `getTappableRectsFromClientRects` out of the inner loops so it only needs to run n times, not n^2.

The secondary optimization was to add a quick bounding box to each tap target of at least `FINGER_SIZE_PX` size (containing all of that target's client rects). If two bounding boxes don't overlap at all there is no point in testing further (though if they do overlap, there still may be no overlap of the constituent client rects).

Everything else was just some speeding up of hot functions without changing any behavior.

Functionality/flow/concepts should mostly be unchanged.

Remaining possibilities if we find it's a problem anywhere:
- the bounding box test is still O(n^2). Can do it n log n if we cared enough.
- we could halve the number of overlap failure tests if we handed the symmetrical situation simultaneously instead of intersecting and then filtering later
- `allRectsContainedWithinEachOther` is about 10% of the runtime of audit of the wikipedia page and doesn't appear to ever do anything. Conversation in https://github.com/GoogleChrome/lighthouse/pull/5846#discussion_r245247453 made it seem like it might only be needed when we add `position:absolute`? 
- all of the seemingly tight numeric functions (e.g. `rectContains`, `rectsTouchOrOverlap`) are actually a mess at runtime due to v8's int vs double optimizations (some rects have integer coordinates, others don't, and v8 can't always tell they're supposed to be the same object shape regardless). These functions are all super hot so we might benefit from optimizing for this, but it's going to be ugly so likely not worth it compared to the above.


----
initial numbers before feedback/bug fix
~~Some results:
avclub
before:66.51 ms
after: 21.48 ms~~

~~`https://github.com/GoogleChrome/lighthouse/pull/5846`
before: 101.30 ms
after: 39.43 ms~~

~~`https://en.wikipedia.org/wiki/List_of_2017_albums`
before: 18,432.65 ms
after: 1,192.31 ms~~


mattzeunert: Nice, that's a pretty significant speed-up 😍

> allRectsContainedWithinEachOther is about 10% of the runtime of audit of the wikipedia page and doesn't appear to ever do anything. Conversation in #5846 (comment) made it seem like it might only be needed when we add position:absolute?

Yeah, right now we just ignore `position: absolute` tap targets, and the gatherer already ignores elements that have an ancestor that's a tap target. We could only run that check if either tap target is actually `position: absolute`.

Patch:
diff --git a/lighthouse-core/audits/seo/tap-targets.js b/lighthouse-core/audits/seo/tap-targets.js
index 3a13b9369..b82e51fdb 100644
--- a/lighthouse-core/audits/seo/tap-targets.js
+++ b/lighthouse-core/audits/seo/tap-targets.js
@@ -12,10 +12,12 @@
 const Audit = require('../audit');
 const ViewportAudit = require('../viewport');
 const {
+  rectsTouchOrOverlap,
   getRectOverlapArea,
   getRectAtCenter,
   allRectsContainedWithinEachOther,
   getLargestRect,
+  getBoundingRectWithPadding,
 } = require('../../lib/rect-helpers');
 const {getTappableRectsFromClientRects} = require('../../lib/tappable-rects');
 const i18n = require('../../lib/i18n/i18n.js');
@@ -34,7 +36,7 @@ const UIStrings = {
   /** Label of a table column that identifies a tap target (like a link or button) that overlaps with another tap target. */
   overlappingTargetHeader: 'Overlapping Target',
   /** Explanatory message stating that there was a failure in an audit caused by the viewport meta tag not being optimized for mobile screens, which caused tap targets like buttons and links to be too small to tap on. */
-  /* eslint-disable max-len */
+  /* eslint-disable-next-line max-len */
   explanationViewportMetaNotOptimized: 'Tap targets are too small because there\'s no viewport meta tag optimized for mobile screens',
   /** Explanatory message stating that a certain percentage of the tap targets (like buttons and links) on the page are of an appropriately large size. */
   displayValue: '{decimalProportion, number, percent} appropriately sized tap targets',
@@ -47,6 +49,20 @@ const FINGER_SIZE_PX = 48;
 // to the finger area tapping on the intended element
 const MAX_ACCEPTABLE_OVERLAP_SCORE_RATIO = 0.25;
 
+/**
+ * Returns a tap target augmented with a bounding rect for quick overlapping
+ * rejections. Rect contains all the client rects, padded to half FINGER_SIZE_PX.
+ * @param {LH.Artifacts.TapTarget[]} targets
+ * @return {BoundedTapTarget[]}
+ */
+function getBoundedTapTargets(targets) {
+  return targets.map(tapTarget => {
+    return {
+      tapTarget,
+      paddedBoundsRect: getBoundingRectWithPadding(tapTarget.clientRects, FINGER_SIZE_PX),
+    };
+  });
+}
 
 /**
  * @param {LH.Artifacts.Rect} cr
@@ -57,130 +73,108 @@ function clientRectBelowMinimumSize(cr) {
 
 /**
  * A target is "too small" if none of its clientRects are at least the size of a finger.
- * @param {LH.Artifacts.TapTarget[]} targets
- * @returns {LH.Artifacts.TapTarget[]}
+ * @param {BoundedTapTarget[]} targets
+ * @returns {BoundedTapTarget[]}
  */
 function getTooSmallTargets(targets) {
   return targets.filter(target => {
-    return target.clientRects.every(clientRectBelowMinimumSize);
+    return target.tapTarget.clientRects.every(clientRectBelowMinimumSize);
   });
 }
 
 /**
- * @param {LH.Artifacts.TapTarget[]} tooSmallTargets
- * @param {LH.Artifacts.TapTarget[]} allTargets
+ * @param {BoundedTapTarget[]} tooSmallTargets
+ * @param {BoundedTapTarget[]} allTargets
  * @returns {TapTargetOverlapFailure[]}
  */
 function getAllOverlapFailures(tooSmallTargets, allTargets) {
   /** @type {TapTargetOverlapFailure[]} */
-  let failures = [];
+  const failures = [];
 
   tooSmallTargets.forEach(target => {
-    const overlappingTargets = getAllOverlapFailuresForTarget(
-      target,
-      allTargets
-    );
+    // Convert client rects to unique tappable areas from a user's perspective
+    const tappableRects = getTappableRectsFromClientRects(target.tapTarget.clientRects);
 
-    failures = failures.concat(overlappingTargets);
-  });
+    for (const maybeOverlappingTarget of allTargets) {
+      if (maybeOverlappingTarget === target) {
+        // Checking the same target with itself, skip.
+        continue;
+      }
 
-  return failures;
-}
+      if (!rectsTouchOrOverlap(target.paddedBoundsRect, maybeOverlappingTarget.paddedBoundsRect)) {
+        // Bounding boxes (padded with half FINGER_SIZE_PX) don't overlap, skip.
+        continue;
+      }
 
-/**
- *
- * @param {LH.Artifacts.TapTarget} tapTarget
- * @param {LH.Artifacts.TapTarget[]} allTapTargets
- * @returns {TapTargetOverlapFailure[]}
- */
-function getAllOverlapFailuresForTarget(tapTarget, allTapTargets) {
-  /** @type TapTargetOverlapFailure[] */
-  const failures = [];
+      if (target.tapTarget.href === maybeOverlappingTarget.tapTarget.href) {
+        const isHttpOrHttpsLink = /https?:\/\//.test(target.tapTarget.href);
+        if (isHttpOrHttpsLink) {
+          // No overlap because same target action, skip.
+          continue;
+        }
+      }
 
-  for (const maybeOverlappingTarget of allTapTargets) {
-    if (maybeOverlappingTarget === tapTarget) {
-      // checking the same target with itself, skip
-      continue;
-    }
+      const maybeOverlappingRects = maybeOverlappingTarget.tapTarget.clientRects;
+      if (allRectsContainedWithinEachOther(tappableRects, maybeOverlappingRects)) {
+        // If one tap target is fully contained within the other that's
+        // probably intentional (e.g. an item with a delete button inside).
+        // We'll miss some problems because of this, but that's better
+        // than falsely reporting a failure.
+        continue;
+      }
 
-    const failure = getOverlapFailureForTargetPair(tapTarget, maybeOverlappingTarget);
-    if (failure) {
-      failures.push(failure);
+      const rectFailure = getOverlapFailureForTargetPair(tappableRects, maybeOverlappingRects);
+      if (rectFailure) {
+        failures.push({
+          ...rectFailure,
+          tapTarget: target.tapTarget,
+          overlappingTarget: maybeOverlappingTarget.tapTarget,
+        });
+      }
     }
-  }
+  });
 
   return failures;
 }
 
 /**
- * @param {LH.Artifacts.TapTarget} tapTarget
- * @param {LH.Artifacts.TapTarget} maybeOverlappingTarget
- * @returns {TapTargetOverlapFailure | null}
+ * @param {LH.Artifacts.Rect[]} tappableRects
+ * @param {LH.Artifacts.Rect[]} maybeOverlappingRects
+ * @returns {ClientRectOverlapFailure | null}
  */
-function getOverlapFailureForTargetPair(tapTarget, maybeOverlappingTarget) {
-  const isHttpOrHttpsLink = /https?:\/\//.test(tapTarget.href);
-  if (isHttpOrHttpsLink && tapTarget.href === maybeOverlappingTarget.href) {
-    // no overlap because same target action
-    return null;
-  }
-
-  // Convert client rects to unique tappable areas from a user's perspective
-  const tappableRects = getTappableRectsFromClientRects(tapTarget.clientRects);
-  if (allRectsContainedWithinEachOther(tappableRects, maybeOverlappingTarget.clientRects)) {
-    // If one tap target is fully contained within the other that's
-    // probably intentional (e.g. an item with a delete button inside).
-    // We'll miss some problems because of this, but that's better
-    // than falsely reporting a failure.
-    return null;
-  }
-
-  /** @type TapTargetOverlapFailure | null */
+function getOverlapFailureForTargetPair(tappableRects, maybeOverlappingRects) {
+  /** @type ClientRectOverlapFailure | null */
   let greatestFailure = null;
+
   for (const targetCR of tappableRects) {
-    for (const maybeOverlappingCR of maybeOverlappingTarget.clientRects) {
-      const failure = getOverlapFailureForClientRectPair(targetCR, maybeOverlappingCR);
-      if (failure) {
-        // only update our state if this was the biggest failure we've seen for this pair
-        if (!greatestFailure ||
-          failure.overlapScoreRatio > greatestFailure.overlapScoreRatio) {
-          greatestFailure = {
-            ...failure,
-            tapTarget,
-            overlappingTarget: maybeOverlappingTarget,
-          };
-        }
+    const fingerRect = getRectAtCenter(targetCR, FINGER_SIZE_PX);
+    // Score indicates how much of the finger area overlaps each target when the user
+    // taps on the center of targetCR
+    const tapTargetScore = getRectOverlapArea(fingerRect, targetCR);
+
+    for (const maybeOverlappingCR of maybeOverlappingRects) {
+      const overlappingTargetScore = getRectOverlapArea(fingerRect, maybeOverlappingCR);
+
+      const overlapScoreRatio = overlappingTargetScore / tapTargetScore;
+      if (overlapScoreRatio < MAX_ACCEPTABLE_OVERLAP_SCORE_RATIO) {
+        // low score means it's clear that the user tried to tap on the targetCR,
+        // rather than the other tap target client rect
+        continue;
+      }
+
+      // only update our state if this was the biggest failure we've seen for this pair
+      if (!greatestFailure || overlapScoreRatio > greatestFailure.overlapScoreRatio) {
+        greatestFailure = {
+          overlapScoreRatio,
+          tapTargetScore,
+          overlappingTargetScore,
+        };
       }
     }
   }
   return greatestFailure;
 }
 
-/**
- * @param {LH.Artifacts.Rect} targetCR
- * @param {LH.Artifacts.Rect} maybeOverlappingCR
- * @returns {ClientRectOverlapFailure | null}
- */
-function getOverlapFailureForClientRectPair(targetCR, maybeOverlappingCR) {
-  const fingerRect = getRectAtCenter(targetCR, FINGER_SIZE_PX);
-  // Score indicates how much of the finger area overlaps each target when the user
-  // taps on the center of targetCR
-  const tapTargetScore = getRectOverlapArea(fingerRect, targetCR);
-  const maybeOverlappingScore = getRectOverlapArea(fingerRect, maybeOverlappingCR);
-
-  const overlapScoreRatio = maybeOverlappingScore / tapTargetScore;
-  if (overlapScoreRatio < MAX_ACCEPTABLE_OVERLAP_SCORE_RATIO) {
-    // low score means it's clear that the user tried to tap on the targetCR,
-    // rather than the other tap target client rect
-    return null;
-  }
-
-  return {
-    overlapScoreRatio,
-    tapTargetScore,
-    overlappingTargetScore: maybeOverlappingScore,
-  };
-}
-
 /**
  * Only report one failure if two targets overlap each other
  * @param {TapTargetOverlapFailure[]} overlapFailures
@@ -287,8 +281,11 @@ class TapTargets extends Audit {
       };
     }
 
-    const tooSmallTargets = getTooSmallTargets(artifacts.TapTargets);
-    const overlapFailures = getAllOverlapFailures(tooSmallTargets, artifacts.TapTargets);
+    // Augment the targets with padded bounding rects for quick intersection testing.
+    const boundedTapTargets = getBoundedTapTargets(artifacts.TapTargets);
+
+    const tooSmallTargets = getTooSmallTargets(boundedTapTargets);
+    const overlapFailures = getAllOverlapFailures(tooSmallTargets, boundedTapTargets);
     const overlapFailuresForDisplay = mergeSymmetricFailures(overlapFailures);
     const tableItems = getTableItems(overlapFailuresForDisplay);
 
@@ -336,6 +333,11 @@ module.exports.UIStrings = UIStrings;
   overlappingTarget: LH.Artifacts.TapTarget;
 }} TapTargetOverlapFailure */
 
+/** @typedef {{
+  paddedBoundsRect: LH.Artifacts.Rect;
+  tapTarget: LH.Artifacts.TapTarget;
+}} BoundedTapTarget */
+
 /** @typedef {{
   tapTarget: LH.Audit.DetailsRendererNodeDetailsJSON;
   overlappingTarget: LH.Audit.DetailsRendererNodeDetailsJSON;
diff --git a/lighthouse-core/lib/rect-helpers.js b/lighthouse-core/lib/rect-helpers.js
index 9deb75bbf..5bae4486e 100644
--- a/lighthouse-core/lib/rect-helpers.js
+++ b/lighthouse-core/lib/rect-helpers.js
@@ -9,48 +9,28 @@
  * @param {LH.Artifacts.Rect} rect
  * @param {{x:number, y:number}} point
  */
-// We sometimes run this as a part of a gatherer script injected into the page, so prevent
-// renaming the function for code coverage.
-/* istanbul ignore next */
 function rectContainsPoint(rect, {x, y}) {
   return rect.left <= x && rect.right >= x && rect.top <= y && rect.bottom >= y;
 }
 
 /**
+ * Returns whether rect2 is contained entirely within rect1;
  * @param {LH.Artifacts.Rect} rect1
  * @param {LH.Artifacts.Rect} rect2
+ * @return {boolean}
  */
 // We sometimes run this as a part of a gatherer script injected into the page, so prevent
 // renaming the function for code coverage.
 /* istanbul ignore next */
 function rectContains(rect1, rect2) {
-  return (
-    // top left corner
-    rectContainsPoint(rect1, {
-      x: rect2.left,
-      y: rect2.top,
-    }) &&
-    // top right corner
-    rectContainsPoint(rect1, {
-      x: rect2.right,
-      y: rect2.top,
-    }) &&
-    // bottom left corner
-    rectContainsPoint(rect1, {
-      x: rect2.left,
-      y: rect2.bottom,
-    }) &&
-    // bottom right corner
-    rectContainsPoint(rect1, {
-      x: rect2.right,
-      y: rect2.bottom,
-    })
-  );
+  return rect2.top >= rect1.top &&
+    rect2.right <= rect1.right &&
+    rect2.bottom <= rect1.bottom &&
+    rect2.left >= rect1.left;
 }
 
 
 const rectContainsString = `
-  ${rectContainsPoint.toString()}
   ${rectContains.toString()};
 `;
 
@@ -110,6 +90,46 @@ function rectsTouchOrOverlap(rectA, rectB) {
   );
 }
 
+/**
+ * Returns a bounding rect for all the passed in rects, with padded with half of
+ * `minimumSize` on all sides.
+ * @param {LH.Artifacts.Rect[]} rects
+ * @param {number} minimumSize
+ * @return {LH.Artifacts.Rect}
+ */
+function getBoundingRectWithPadding(rects, minimumSize) {
+  if (rects.length === 0) {
+    throw new Error('No rects to take bounds of');
+  }
+
+  let left = Number.MAX_VALUE;
+  let right = -Number.MAX_VALUE;
+  let top = Number.MAX_VALUE;
+  let bottom = -Number.MAX_VALUE;
+  for (const rect of rects) {
+    left = Math.min(left, rect.left);
+    right = Math.max(right, rect.right);
+    top = Math.min(top, rect.top);
+    bottom = Math.max(bottom, rect.bottom);
+  }
+
+  // Pad on all sides.
+  const halfMinSize = minimumSize / 2;
+  left -= halfMinSize;
+  right += halfMinSize;
+  top -= halfMinSize;
+  bottom += halfMinSize;
+
+  return {
+    left,
+    right,
+    top,
+    bottom,
+    width: right - left,
+    height: bottom - top,
+  };
+}
+
 /**
  * @param {LH.Artifacts.Rect} rectA
  * @param {LH.Artifacts.Rect} rectB
@@ -161,32 +181,15 @@ function addRectTopAndBottom({x, y, width, height}) {
  * @param {LH.Artifacts.Rect} rect1
  * @param {LH.Artifacts.Rect} rect2
  */
-function getRectXOverlap(rect1, rect2) {
+function getRectOverlapArea(rect1, rect2) {
   // https://stackoverflow.com/a/9325084/1290545
-  return Math.max(
-    0,
-    Math.min(rect1.right, rect2.right) - Math.max(rect1.left, rect2.left)
-  );
-}
+  const rectYOverlap = Math.min(rect1.bottom, rect2.bottom) - Math.max(rect1.top, rect2.top);
+  if (rectYOverlap <= 0) return 0;
 
-/**
- * @param {LH.Artifacts.Rect} rect1
- * @param {LH.Artifacts.Rect} rect2
- */
-function getRectYOverlap(rect1, rect2) {
-  // https://stackoverflow.com/a/9325084/1290545
-  return Math.max(
-    0,
-    Math.min(rect1.bottom, rect2.bottom) - Math.max(rect1.top, rect2.top)
-  );
-}
+  const rectXOverlap = Math.min(rect1.right, rect2.right) - Math.max(rect1.left, rect2.left);
+  if (rectXOverlap <= 0) return 0;
 
-/**
- * @param {LH.Artifacts.Rect} rect1
- * @param {LH.Artifacts.Rect} rect2
- */
-function getRectOverlapArea(rect1, rect2) {
-  return getRectXOverlap(rect1, rect2) * getRectYOverlap(rect1, rect2);
+  return rectXOverlap * rectYOverlap;
 }
 
 /**
@@ -244,13 +247,12 @@ module.exports = {
   rectContainsString,
   addRectWidthAndHeight,
   addRectTopAndBottom,
-  getRectXOverlap,
-  getRectYOverlap,
   getRectOverlapArea,
   getRectAtCenter,
   getLargestRect,
   getRectCenterPoint,
   getBoundingRect,
+  getBoundingRectWithPadding,
   rectsTouchOrOverlap,
   allRectsContainedWithinEachOther,
   filterOutRectsContainedByOthers,


Test patch:
diff --git a/lighthouse-core/test/lib/rect-helpers-test.js b/lighthouse-core/test/lib/rect-helpers-test.js
index 22c0a19be..82d001686 100644
--- a/lighthouse-core/test/lib/rect-helpers-test.js
+++ b/lighthouse-core/test/lib/rect-helpers-test.js
@@ -13,6 +13,7 @@ const {
   getLargestRect,
   getRectAtCenter,
   allRectsContainedWithinEachOther,
+  getBoundingRectWithPadding,
 } = require('../../lib/rect-helpers');
 
 describe('Rect Helpers', () => {
@@ -84,4 +85,35 @@ describe('Rect Helpers', () => {
       expect(allRectsContainedWithinEachOther([rect1], [rect2])).toBe(false);
     });
   });
+
+  describe('#getBoundingRectWithPadding', () => {
+    it('throws an error if no rects are passed in', () => {
+      expect(() => getBoundingRectWithPadding([])).toThrow('No rects');
+    });
+
+    it('pads rect with half minimum size on all sides', () => {
+      const rect = addRectTopAndBottom({x: 0, y: 0, width: 0, height: 0});
+      const minimumSize = 20;
+      const expectedPaddedBounds = addRectTopAndBottom({x: -10, y: -10, width: 20, height: 20});
+
+      expect(getBoundingRectWithPadding([rect], minimumSize)).toEqual(expectedPaddedBounds);
+    });
+
+    it('pads the bounding box of two rects with half of the minimum size', () => {
+      const rect1 = addRectTopAndBottom({x: 0, y: 0, width: 10, height: 10});
+      const rect2 = addRectTopAndBottom({x: 50, y: 50, width: 10, height: 10}); // in the middle somewhere
+      const rect3 = addRectTopAndBottom({x: 100, y: 100, width: 10, height: 10});
+
+      const minimumSize = 20;
+      const expectedPaddedBounds = addRectTopAndBottom({
+        x: -minimumSize / 2,
+        y: -minimumSize / 2,
+        width: 110 + minimumSize,
+        height: 110 + minimumSize,
+      });
+
+      const rects = [rect1, rect2, rect3];
+      expect(getBoundingRectWithPadding(rects, minimumSize)).toEqual(expectedPaddedBounds);
+    });
+  });
 });