Fix O(N^2) / O(N*depth) behavior for tab focus navigation |
||||||
Issue description
core/page/FocusController.cpp and core/page/SlotScopedNavigation.cpp
use naive algorithm to search next/previous focusable element,
especially when the search is scoped in <slot> scope.
At this point I'm not sure if it was O(N^2), but at least from
what I see now, many O(depth) operations are done in O(N) loop
where N is the number of elements under the slot scope,
thus it can be O(N * depth) at least.
Here's rough analysis (not exhaustive and very accurate, I may miss
something that is "N"):
- ScopedFocusNavigation::NextFocusableElement()
calls ScopedFocusNavigation::MoveToNext() O(N) times
- ScopedFocusNavigation::MoveToNext()
calls non-trivial functions:
- ScopedFocusNavigation::IsSlotFallbackScopedForThisSlot()
- ScopedFocusNavigation::IsSlotFallbackScoped()
- SlotScopedTraversal::Next()
ScopedFocusNavigation::IsSlotFallbackScoped(element)
- O(depth of element)
ScopedFocusNavigation::IsSlotFallbackScopedForThisSlot(slot, current)
- Loops O(depth of current)
- calls SlotScopedTraversal::IsSlotScoped() which can take
O(depth of current)
SlotScopedTraversal::Next()
- calls NearestInclusiveAncestorAssignedToSlot() which can take
O(depth)
- calls NextSkippingChildrenOfShadowHost() O(depth) at worst?
- loops thorough assigned nodes of a slot, esp. Find() against
it takes O(number of assigned nodes), then next sibling could
be found in almost constant time?
Some ideas about more cleanup on the way:
- split ScopedFocusNavigation class out of FocusController.cpp
- define MoveToNext/MovToPrevious/MoveToFirst/MoveToLast as an
virtual interface and implement in inherited classes, rather than
using many if-else's in these methods in ScopedFocusNavigation class.
,
Sep 29 2017
,
Sep 29 2017
,
Oct 6 2017
,
Oct 6 2017
The change merged was: https://chromium.googlesource.com/chromium/src/+/78a168924315e3f9c988ba992a7ea6c57376a415 Improve FocusNavigation from O(N*depth*depth) to O(N) Here is a pathological example of moving focus in 1000 nested slots: http://jsbin.com/romexozero/1/edit?html,output hitting tab on the focused field takes ~3 seconds on my development Linux box with M61 release. For more detail, please read this design doc. https://docs.google.com/a/google.com/document/d/198_aBPlHZDzRXCHfNcyyGd39tIYuZlvlPyPsxuwWimg/edit?usp=sharing Change-Id: I1e5f4fd5ff9bb5c4f32ae1996766e781883ddf90 Reviewed-on: https://chromium-review.googlesource.com/678137 Commit-Queue: Eriko Kurimoto <elkurin@google.com> Reviewed-by: Takayoshi Kochi <kochi@chromium.org> Reviewed-by: Hayato Ito <hayato@chromium.org> Cr-Commit-Position: refs/heads/master@{#507022}
,
Aug 24
,
Aug 24
|
||||||
►
Sign in to add a comment |
||||||
Comment 1 by kochi@chromium.org
, Sep 11 2017Components: Blink>Focus
Labels: -Pri-3 Pri-2
Owner: elkurin@google.com
Status: Assigned (was: Untriaged)