Bug 237678 – AX: AccessibilityObject::visibleCharacterRange is extremely slow when called on objects with lots of text

• Status: RESOLVED
• Resolution: FIXED
• Component: Accessibility

[Tyler Wilcock]

In this example `sample` with 100 total samplings, visibleCharacterRange accounted for 95% of the runtime:

95   WebCore::AccessibilityObject::visibleCharacterRange() const + 1740 (WebCore + 17852704) [0x10d83a920]
  62   WebCore::AccessibilityRenderObject::boundsForRange(WebCore::SimpleRange const&) const + 904 (WebCore + 18023804) [0x10d86457c]
  36   WebCore::boundsForRects(WebCore::LayoutRect const&, WebCore::LayoutRect const&, WebCore::SimpleRange const&) + 292 (WebCore + 18022192) [0x10d863f30]
  26   WebCore::RenderObject::absoluteTextRects(WebCore::SimpleRange const&, WTF::OptionSet<WebCore::RenderObject::BoundingRectBehavior>) + 360 (WebCore + 33800176) [0x10e76fff0]
  25   WebCore::absoluteRectsForRangeInText(WebCore::SimpleRange const&, WebCore::Text&, WTF::OptionSet<WebCore::RenderObject::BoundingRectBehavior>) + 100 (WebCore + 33801512) [0x10e770528]
  18   WebCore::RenderText::absoluteQuadsForRange(unsigned int, unsigned int, bool, bool, bool*) const + 1588 (WebCore + 33927852) [0x10e78f2ac]
  18   WebCore::RenderObject::localToContainerQuad(WebCore::FloatQuad const&, WebCore::RenderLayerModelObject const*, WTF::OptionSet<WebCore::MapCoordinatesMode>, bool*) const + 292 (WebCore + 33784096) [0x10e76c120]

[Radar WebKit Bug Importer]

<rdar://problem/90059576>

[Tyler Wilcock]

Created attachment 454296 [details]
Patch

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #2)
> Created attachment 454296 [details]
> Patch

--- a/Source/WebCore/accessibility/AccessibilityObject.cpp
+++ a/Source/WebCore/accessibility/AccessibilityObject.cpp

+Vector<BoundaryPoint> AccessibilityObject::previousLineStartBoundaryPoints(const VisiblePosition& startingPosition, const SimpleRange& targetRange, unsigned positionsToRetrieve) const
 {
...
+    VisiblePosition lastPosition = startingPosition;
+    for (unsigned i = 0; i < positionsToRetrieve; i++) {
+        auto newPosition = previousLineStartPositionInternal(lastPosition);

Can't we just have one local std::optional<VisiblePosition> instead of lastPosition and newPosition?

+        auto boundaryPoint = makeBoundaryPoint(*newPosition);
+        if (!boundaryPoint || !contains(targetRange, *boundaryPoint))
+            break;

I'd think that if !contains(...) you want to continue instead of breaking out of the loop, because another unvisited position may be inside the range.

+std::optional<BoundaryPoint> AccessibilityObject::lastBoundaryPointContainedInRect(const Vector<BoundaryPoint>& boundaryPoints, const BoundaryPoint& startBoundary, FloatRect rect, int leftIndex, int rightIndex) const

Pass the rect by ref, const FloatRect&.

+    auto indexIsValid = [&] (int index) {
+        return index >= 0 && index < static_cast<int>(boundaryPoints.size());
+    };

Doesn't casting a large size_t to int turn into a negative number? I'm pretty sure there is a safer way of doing this conversion, if you actually need to use int.

+    auto boundaryPointContainedByRect = [&, this] (const BoundaryPoint& testEndBoundary) {

Doesn't [&] capture this as well?

testEndBoundary -> boundary, testEnd doesn't mean anything here.

+    if (leftIndex > rightIndex || boundaryPoints.isEmpty())
         return std::nullopt;

This param check, early return should be done at the beginning of the function.

+    int midIndex = leftIndex + ((rightIndex - leftIndex) / 2);

You can get rid of one ( ).

+bool AccessibilityObject::boundaryPointsContainedByRect(const BoundaryPoint& startBoundary, const BoundaryPoint& endBoundary, FloatRect rect) const

const FloatRect&

--- a/Source/WebCore/accessibility/AccessibilityObject.h
+++ a/Source/WebCore/accessibility/AccessibilityObject.h

+    bool boundaryPointsContainedByRect(const BoundaryPoint&, const BoundaryPoint&, FloatRect) const;
+    std::optional<BoundaryPoint> lastBoundaryPointContainedInRect(const Vector<BoundaryPoint>&, const BoundaryPoint&, FloatRect, int, int) const;
+    std::optional<BoundaryPoint> lastBoundaryPointContainedInRect(const Vector<BoundaryPoint>& boundaryPoints, const BoundaryPoint& pairBoundaryPoint, FloatRect targetRect) const

We have names "ContainedByRect" and "ContainedInRect". Is there a distinction? Not sure what is more correct grammatically, but we should choose one if possible.

The header inlines shouldn't be in the class declaration, but instead put them below the class as inline AccessibilityObject::xxx.

[Tyler Wilcock]

Created attachment 454901 [details]
Patch

[Tyler Wilcock]

> +        auto boundaryPoint = makeBoundaryPoint(*newPosition);
> +        if (!boundaryPoint || !contains(targetRange, *boundaryPoint))
> +            break;
> 
> I'd think that if !contains(...) you want to continue instead of breaking
> out of the loop, because another unvisited position may be inside the range.
I don't believe this is true, as any later elements will be further and further outside the range, which allows us to break here.

Addressed all of your other comments. Thanks for the review!

[Tyler Wilcock]

Created attachment 455139 [details]
Patch

[Tyler Wilcock]

Created attachment 455140 [details]
Patch

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #7)
> Created attachment 455140 [details]
> Patch

--- a/Source/WebCore/accessibility/AccessibilityObject.cpp
+++ a/Source/WebCore/accessibility/AccessibilityObject.cpp

+std::optional<BoundaryPoint> AccessibilityObject::lastBoundaryPointContainedInRect(const Vector<BoundaryPoint>& boundaryPoints, const BoundaryPoint& startBoundary, const FloatRect& rect, int leftIndex, int rightIndex) const
+{
...
+    int midIndex = leftIndex + (rightIndex - leftIndex) / 2;

int midIndex = (leftIndex + rightIndex) / 2;

--- a/Source/WebCore/accessibility/AccessibilityObject.h
+++ a/Source/WebCore/accessibility/AccessibilityObject.h

+#if ENABLE(ACCESSIBILITY)
...
+#endif
+
 #if !ENABLE(ACCESSIBILITY)
...

Change to #if ENABLE(ACCESSIBILITY) ... #else ...

+inline VisiblePosition AccessibilityObject::previousLineStartPosition(const VisiblePosition& position) const { return VisiblePosition(); }

return { }

[Andres Gonzalez]

Can we make the caching in a way that would work for ITM as well?

[Tyler Wilcock]

> --- a/Source/WebCore/accessibility/AccessibilityObject.cpp
> +++ a/Source/WebCore/accessibility/AccessibilityObject.cpp
> 
> +std::optional<BoundaryPoint>
> AccessibilityObject::lastBoundaryPointContainedInRect(const
> Vector<BoundaryPoint>& boundaryPoints, const BoundaryPoint& startBoundary,
> const FloatRect& rect, int leftIndex, int rightIndex) const
> +{
> ...
> +    int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
> 
> int midIndex = (leftIndex + rightIndex) / 2;
I agree that your suggestion is the more intuitive, but that approach is vulnerable to overflow if leftIndex + rightIndex is greater than the max int value, while the algorithm in the patch is not vulnerable to this overflow.

> Can we make the caching in a way that would work for ITM as well?
ITM does benefit from the caching in the patch as-is:

  1. ITM requests visibleCharacterRange, goes to main-thread live object to get it
  2. The live object does the work and caches the value
  3. On subsequent requests, if inputs haven't changed, ITM still pays the cost to go to the mainthread but gets the already cached value

In order to save a trip to the mainthread to get the cached value, we would need to make the visibleCharacterRange inputs available off the mainthread:

  1. AccessibilityObject::elementRange()
  2. AccessibilityObject::unobscuredContentRect()
  3. AccessibilityObject::elementRect()

Not sure there's an easy way to do that, since these functions rely on a lot of data only available on the mainthread (at least right now).

[Tyler Wilcock]

Created attachment 455251 [details]
Patch

[Tyler Wilcock]

Applied your other suggestions.

[EWS]

Committed r291600 (248693@main): <https://commits.webkit.org/248693@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 455251 [details].