New issue
Advanced search Search tips
Note: Color blocks (like or ) mean that a user may not be available. Tooltip shows the reason.

Issue 763794 link

Starred by 1 user

Issue metadata

Status: Fixed
Owner:
Last visit > 30 days ago
Closed: Oct 2017
Cc:
Components:
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 2
Type: Bug



Sign in to add a comment

Fix O(N^2) / O(N*depth) behavior for tab focus navigation

Project Member Reported by kochi@chromium.org, Sep 11 2017

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.

 

Comment 1 by kochi@chromium.org, Sep 11 2017

Cc: hayato@chromium.org kochi@chromium.org
Components: Blink>Focus
Labels: -Pri-3 Pri-2
Owner: elkurin@google.com
Status: Assigned (was: Untriaged)
Eriko-san, could you take a look?
Components: Blink>HTML>Focus
Components: -Blink>Focus

Comment 4 by elkurin@google.com, Oct 6 2017

Status: Fixed (was: Assigned)

Comment 5 by kochi@chromium.org, 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}
Cc: sarakato@chromium.org
Cc: -sarakato@chromium.org

Sign in to add a comment