Bisect info: 492582 (good) - 492589 (bad)
https://chromium.googlesource.com/chromium/src/+log/5e5e8213..5e4413ea?pretty=fuller
Suspecting r492588 - 041c0b075176fb9bca94fd67fc1b6053a4df2e1c
"[Android] Relanding Smart GO NEXT feature in Android Chrome 2/2"
Landed in 62.0.3180.0

Confirmed by observing FocusController code added by r492588 in stacktrace during 100% CPU load of the tab:
 	chrome_child.dll!blink::Element::tabIndex(void)	Unknown
 	chrome_child.dll!blink::Element::IsKeyboardFocusable(void)	Unknown
 	chrome_child.dll!blink::FocusController::Trace(class blink::Visitor *)	Unknown
 	chrome_child.dll!blink::FocusController::Trace(class blink::Visitor *)	Unknown
 	chrome_child.dll!blink::Traversal<class blink::Element>::Previous(class blink::Node const &)	Unknown
 	chrome_child.dll!blink::FocusController::AdvanceFocusAcrossFrames(enum blink::WebFocusType,class blink::RemoteFrame *,class blink::LocalFrame *,class blink::InputDeviceCapabilities *)	Unknown
 	chrome_child.dll!blink::FocusController::NextFocusableElementInForm(class blink::Element *,enum blink::WebFocusType)	Unknown

Able to reproduce the issue on Windows 10, Ubuntu 14.04 and Mac 10.12.6 using chrome stable version #62.0.3202.75 and latest canary #64.0.3257.0.

Bisect Information:
=====================
Good build: 62.0.3179.0	 Revision(492477)
Bad Build : 62.0.3180.0	 Revision(492769)

Change Log URL: 
https://chromium.googlesource.com/chromium/src/+log/6fd2494b34878740b651208c9b05de5f9d1ef653..041c0b075176fb9bca94fd67fc1b6053a4df2e1c

From the above change log suspecting below change
Change-Id: Ib2c7343a6ec7dea18c7cfa5ac283ac4d29e3a4cb
Reviewed-on: https://chromium-review.googlesource.com/574514

ajith.v@ - Could you please check whether this is caused with respect to your change, if not please help us in assigning it to the right owner.
Note: Adding label ReleaseBlock-Stable as it seems to be a recent regression.

Thanks...!!

I think this can wait till M-63 reaches stable? Please feel free to update if someone feels otherwise.

M63 Stable promotion is coming soon and your bug is labelled as Stable ReleaseBlock, pls make sure to land the fix and request a merge to M63 ASAP. Thank you.

Ajith, could you take action on this immediately?
The test case posted with the description has 5000 focusable elements in a tree,
which sounds to me that it is somewhat excessive, but could be in real web sites.

I tried this on my Pixel, and it takes like ~30 seconds from a tap to focus.
It smells that there is some code O(N^2) in the logic.

Probably what we can do is ideally identify the bottleneck and fix it, but if no, try some
mitigation like implementing a logic to "give up" after some threshold (e.g. 100) so that
focus happens within reasonable time at the cost of not showing prev/next in a larger form.

If both doesn't work, maybe we have to consider disabling the whole logic for M63 release.

kochi@ - I will look into this issue today. From https://bugs.chromium.org/p/chromium/issues/attachmentText?aid=310359 it appears FindFocusableElement has to traverse entire <div class="cell" > elements before concluding next/previous even though <div> is not child of active form. Hence this delay is occurring.
This is because we can have elements which is outside form element and can still pointing to the form as child using "form" attribute, so we have to continue search until we couldn't find a focusable element.

Let me think bit more how we can optimise it.

Ajith, thanks for taking on it.

As 63 is on beta and we don't have much time for release, while thinking of optimization,
could you try some stop-gap solution?  We need some time to bake in the fix on trunk,
then need to merge to M63.
Pessimistically thinking, an optimization could incur risks such as further regression or
corner cases.

I think a safer option would be implement a stop-gap solution and think/experiment
further optimization later.

kochi@ - I need to experiment whether elements outside the form element, which is pointing to form using "form" attribute maintains any child-parent relationship with form. If it exists, then I can completely isolate current issue by modifying code block of identifying next/previous element by traversing only current form children.

If not, then I need to find a stop-gap solution for masking current issue (May be as you suggested, by restricting element traversal by a threshold 100)

I am facing some issue while uploading new patchset to https://chromium-review.googlesource.com/c/chromium/src/+/758481. Once I resolve that, I will land that patch to close this issue.

Ajith, thanks for the update.  If I can help resolving the issue, please
let me know.

@kochi- I am getting following error, while uploading related to "private key"

Title for patchset [[Android] Restricting Smart Go Next only in Android]: Changing const to static const to adhere code base standard
remote: The push has been rejected because we detect that it contains a private        
remote: key. Please check the following commands and confirm that it's        
remote: intentional:        
remote: 
remote:     git show d44837c9dfdc126d9a054cc7d023c78aa0d8ce51        
remote:     git show 9fae938ae6a91f396b3e621c909e1af11c9dbbdc        
remote:     git show b9696fddc53d73acfffc875a116da4abe8b21d01        
remote:     git show 747d4456e7a9593ca6039d108a00159012273a9c        
remote:     git show 7ae4caf9f0f376f5d9a04e8be311df615b301fdf        
remote:     git show b1300babd9b5b3f6527bd69ca19d9a6bb2f65926        
remote: 
remote: You can use `git rev-list --objects --all` to find the files.        
remote: 
remote: To push these files, please run `git push -o nokeycheck`.        
remote: 
To https://chromium.googlesource.com/chromium/src.git
 ! [remote rejected]           c732d0207d705374e928007ce0cb14392b018737 -> refs/for/refs/heads/master%notify=NONE,m=Changing_const_to_static_const_to_adhere_code_base_standard (found a private key)
error: failed to push some refs to 'https://chromium.googlesource.com/chromium/src.git'

Error after CL description prompt -- saving description to /home/ajithk/.git_cl_description_backup

Failed to create a change. Please examine output above for the reason of the failure.
Hint: run command below to diagnose common Git/Gerrit credential problems:
  git cl creds-check

If you have any idea about the problem, please let me know

Hmm, I have no idea why the server complain that your CL contain
a private key... Could you try rebase, then try 'git cl upload' again?

Ok thanks kochi. I am trying to apply the patch on a new local branch by pointing to same gerrit URL and hopefully it gets succeeded.

M63 Stable promotion is coming VERY soon. Your bug is labelled as Stable ReleaseBlock, pls make sure to land the fix and request a merge  into the release branch ASAP. Thank you.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9e7b5573604b73de075c1c7a86ae9b26b871a96b

commit 9e7b5573604b73de075c1c7a86ae9b26b871a96b
Author: AJITH KUMAR V <ajith.v@samsung.com>
Date: Tue Nov 14 00:54:21 2017

[Android] Restricting Smart Go Next only in Android

Current implementation of Smart Go Next will execute for
all platforms because of calculation logic touches blink.
Now restricting this logic only in Android platform. Due to
a regression in blink wrt element focus time, currently applying
a threshold of focus calculation.

Bug:  781026 
Change-Id: I96c60e15186bddae087345f2d5b25a359dd4ac48
Reviewed-on: https://chromium-review.googlesource.com/758481
Commit-Queue: Takayoshi Kochi <kochi@chromium.org>
Reviewed-by: Daniel Cheng <dcheng@chromium.org>
Reviewed-by: Changwan Ryu <changwan@chromium.org>
Reviewed-by: Nasko Oskov <nasko@chromium.org>
Reviewed-by: Takayoshi Kochi <kochi@chromium.org>
Cr-Commit-Position: refs/heads/master@{#516124}
[modify] https://crrev.com/9e7b5573604b73de075c1c7a86ae9b26b871a96b/content/renderer/render_widget.cc
[modify] https://crrev.com/9e7b5573604b73de075c1c7a86ae9b26b871a96b/third_party/WebKit/Source/core/page/FocusController.cpp

[Auto-generated comment by a script] We noticed that this issue is targeted for M-63; it appears the fix may have landed after branch point, meaning a merge might be required. Please confirm if a merge is required here - if so add Merge-Request-63 label, otherwise remove Merge-TBD label. Thanks.

Let's wait for a few days in canary.

Verified the fix on Win-10 and Ubuntu 14.04 using Chrome version #64.0.3268.0 as per the comment #0.
Note: Unable to verify the fix on mac due to build failure having issue id: 784251.
Attaching screen cast for reference.
Observed that no focus delay was experienced when the first input field was to gain focus.
Hence, the fix is working as expected. 
Adding the verified labels.

Thanks...!!

Deleted: 781026.webm 1.5 MB

	781026.webm 1.5 MB View Download

Pls update the bug once change is well baked in Canary. Also pls provide merge justification as this is regressed in M62 (not M63 regression) and we're getting closer to M63 Stable promotion.

This bug requires manual review: M63 has already been promoted to the beta branch, so this requires manual review
Please contact the milestone owner if you have questions.
Owners: cmasso@(Android), cmasso@(iOS), gkihumba@(ChromeOS), govind@(Desktop)

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot

Justification for merge: the performance of focus navigation on very large DOM
regressed in M62, where the new "smart go next" (let Android on-screen keyboard
show the "next" button where appropriate) feature was implemented. Even though it
was happening only on very large DOM, but the impact is so significant that it makes
users wait for few seconds ~ a minute to go to next focus, while it keeps CPU 100%.

The fix that was to introduce a cut-off value (currently 50) to stop searching for the
next field. The change is simple and small, and should have no impact on most form
pages, but also is able to avoid the problem on large forms.

Approving merge to M63 branch 3239 based on comments #21 and #24. Please merge ASAP. Thank you.

Ajith, I'll take care of merging.

Thank you kochi

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/d0122d5f78250cb66a93f59f915d7a70320bfa23

commit d0122d5f78250cb66a93f59f915d7a70320bfa23
Author: Takayoshi Kochi <kochi@chromium.org>
Date: Wed Nov 15 06:25:05 2017

[Android] Restricting Smart Go Next only in Android

Current implementation of Smart Go Next will execute for
all platforms because of calculation logic touches blink.
Now restricting this logic only in Android platform. Due to
a regression in blink wrt element focus time, currently applying
a threshold of focus calculation.

TBR=ajith.v@samsung.com

(cherry picked from commit 9e7b5573604b73de075c1c7a86ae9b26b871a96b)

Bug:  781026 
Change-Id: I96c60e15186bddae087345f2d5b25a359dd4ac48
Reviewed-on: https://chromium-review.googlesource.com/758481
Commit-Queue: Takayoshi Kochi <kochi@chromium.org>
Reviewed-by: Daniel Cheng <dcheng@chromium.org>
Reviewed-by: Changwan Ryu <changwan@chromium.org>
Reviewed-by: Nasko Oskov <nasko@chromium.org>
Reviewed-by: Takayoshi Kochi <kochi@chromium.org>
Cr-Original-Commit-Position: refs/heads/master@{#516124}
Reviewed-on: https://chromium-review.googlesource.com/770914
Cr-Commit-Position: refs/branch-heads/3239@{#502}
Cr-Branched-From: adb61db19020ed8ecee5e91b1a0ea4c924ae2988-refs/heads/master@{#508578}
[modify] https://crrev.com/d0122d5f78250cb66a93f59f915d7a70320bfa23/content/renderer/render_widget.cc
[modify] https://crrev.com/d0122d5f78250cb66a93f59f915d7a70320bfa23/third_party/WebKit/Source/core/page/FocusController.cpp

Thanks Ajith for the fix, krajshree for testing/verification, govind for
release management!  Fingers crossed :)

Verified this issue on Windows-7, Ubuntu 14.04 and Mac OS 10.12.6 using chrome latest beta M63-63.0.3239.59 by following the steps mentioned in the original comment, observed no delay in focus while typing in the first text box as expected. Hence adding TE-Verified label for M63.

Thanks!

 Issue 787033  has been merged into this issue.