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]
<rdar://problem/90059576>
Created attachment 454296 [details] Patch
(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.
Created attachment 454901 [details] Patch
> + 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!
Created attachment 455139 [details] Patch
Created attachment 455140 [details] Patch
(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 { }
Can we make the caching in a way that would work for ITM as well?
> --- 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).
Created attachment 455251 [details] Patch
Applied your other suggestions.
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].