Bug 122313 – FocusController::advanceFocus spends a lot of time in HTMLMapElement::imageElement

• Component: DOM
• Status: RESOLVED FIXED

[Ryosuke Niwa]

On a web page with lots of map/area elements, we end up spending a lot of time inside HTMLMapElement::imageElement because the HTMLCollection used to traverse through image elements isn't cached, resulting in O(n^2) time complexity.

Running Time	Self		Symbol Name
7711.0ms  100.0%	0.0	 	                      WebKit::handleKeyEvent(WebKit::WebKeyboardEvent const&, WebCore::Page*)
7711.0ms  100.0%	0.0	 	                       WebCore::EventHandler::keyEvent(WebCore::PlatformKeyboardEvent const&)
7711.0ms  100.0%	0.0	 	                        WebCore::EventTarget::dispatchEvent(WTF::PassRefPtr<WebCore::Event>, int&)
7711.0ms  100.0%	0.0	 	                         WebCore::Node::dispatchEvent(WTF::PassRefPtr<WebCore::Event>)
7711.0ms  100.0%	0.0	 	                          WebCore::EventDispatcher::dispatchEvent(WebCore::Node*, WTF::PassRefPtr<WebCore::EventDispatchMediator>)
7711.0ms  100.0%	0.0	 	                           WebCore::EventDispatchMediator::dispatchEvent(WebCore::EventDispatcher*) const
7711.0ms  100.0%	0.0	 	                            WebCore::EventDispatcher::dispatch()
7711.0ms  100.0%	0.0	 	                             WebCore::EventDispatcher::dispatchEventPostProcess(void*)
7711.0ms  100.0%	0.0	 	                              WebCore::HTMLInputElement::defaultEventHandler(WebCore::Event*)
7711.0ms  100.0%	0.0	 	                               WebCore::Node::defaultEventHandler(WebCore::Event*)
7711.0ms  100.0%	0.0	 	                                WebCore::EventHandler::defaultKeyboardEventHandler(WebCore::KeyboardEvent*)
7711.0ms  100.0%	0.0	 	                                 WebCore::FocusController::advanceFocus(WebCore::FocusDirection, WebCore::KeyboardEvent*, bool)
7711.0ms  100.0%	0.0	 	                                  WebCore::FocusController::advanceFocusInDocumentOrder(WebCore::FocusDirection, WebCore::KeyboardEvent*, bool)
7711.0ms  100.0%	0.0	 	                                   WebCore::FocusController::findFocusableElementAcrossFocusScope(WebCore::FocusDirection, WebCore::FocusNavigationScope, WebCore::Node*, WebCore::KeyboardEvent*)
7711.0ms  100.0%	0.0	 	                                    WebCore::FocusController::findFocusableElementRecursively(WebCore::FocusDirection, WebCore::FocusNavigationScope, WebCore::Node*, WebCore::KeyboardEvent*)
7711.0ms  100.0%	0.0	 	                                     WebCore::FocusController::nextFocusableElement(WebCore::FocusNavigationScope, WebCore::Node*, WebCore::KeyboardEvent*)
7711.0ms  100.0%	0.0	 	                                      WebCore::FocusController::findElementWithExactTabIndex(WebCore::Node*, int, WebCore::KeyboardEvent*, WebCore::FocusDirection)
7711.0ms  100.0%	0.0	 	                                       WebCore::HTMLAreaElement::isKeyboardFocusable(WebCore::KeyboardEvent*) const
7711.0ms  100.0%	1.0	 	                                        WebCore::HTMLAreaElement::isFocusable() const
7710.0ms   99.9%	0.0	 	                                         WebCore::HTMLMapElement::imageElement()
7683.0ms   99.6%	0.0	 	                                          WebCore::LiveNodeListBase::item(unsigned int) const

<rdar://problem/14920728>

[Ryosuke Niwa]

Created attachment 213329 [details]
Work in progress

[Ryosuke Niwa]

Created attachment 213335 [details]
Fixes the bug

[Andreas Kling]

Comment on attachment 213335 [details]
Fixes the bug

View in context: https://bugs.webkit.org/attachment.cgi?id=213335&action=review

r=me with some improvements.

> Source/WebCore/dom/Document.h:262
> +    void addImageElementByLowercasedUsemap(const AtomicString&, HTMLImageElement*);
> +    void removeImageElementByLowercasedUsemap(const AtomicString&, HTMLImageElement*);

HTMLImageElement* -> HTMLImageElement& since these don't accept null.

> Source/WebCore/html/HTMLImageElement.cpp:139
> +        const AtomicString& usemap = fastGetAttribute(HTMLNames::usemapAttr);

You already have the usemap attribute in the "value" argument variable here, no need to search for it.

> Source/WebCore/html/HTMLImageElement.cpp:141
> +            m_lowercasedUsemap = usemap.string().substring(1).lower().impl();

Is the .impl() really needed?

> Source/WebCore/html/HTMLImageElement.cpp:324
> +    ASSERT(const_cast<AtomicStringImpl*>(&name)->lower() == &name);

This would look ~1% nicer as:
ASSERT(const_cast<AtomicStringImpl&>(name).lower() == &name);

> Source/WebCore/html/HTMLMapElement.cpp:82
> +    return document().imageElementByUsemap(m_name.lower());

You could make this even faster by caching a lowercase version of the map's name in a member variable.
I don't know what your test case is, so I don't know if it'd be worth much.

[Ryosuke Niwa]

Committed r156925: <http://trac.webkit.org/changeset/156925>

[Ryosuke Niwa]

Fixed intermittent assertion failures reported by ap in http://trac.webkit.org/changeset/156950.

e.g.
http://build.webkit.org/results/Apple%20Lion%20Debug%20WK2%20(Tests)/r156929%20(11902)/fast/images/imagemap-focus-ring-outline-color-explicitly-inherited-from-map-crash-log.txt

CRASHING TEST: fast/images/imagemap-dynamic-area-updates.html

Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0   com.apple.JavaScriptCore      	0x00000001077f9a6a WTFCrash + 42 (Assertions.cpp:342)
1   com.apple.WebCore             	0x0000000108b7d2ba WebCore::Element* WebCore::DocumentOrderedMap::get<&(WebCore::keyMatchesLowercasedUsemap(WTF::AtomicStringImpl const*, WebCore::Element*))>(WTF::AtomicStringImpl const*, WebCore::TreeScope const*) const + 554 (DocumentOrderedMap.cpp:155)
2   com.apple.WebCore             	0x0000000108b7c105 WebCore::DocumentOrderedMap::getElementByLowercasedUsemap(WTF::AtomicStringImpl const*, WebCore::TreeScope const*) const + 37 (DocumentOrderedMap.cpp:181)
3   com.apple.WebCore             	0x0000000108b195e1 WebCore::Document::imageElementByLowercasedUsemap(WTF::AtomicString const&) const + 81 (Document.cpp:722)
4   com.apple.WebCore             	0x0000000108f85ff7 WebCore::HTMLMapElement::imageElement() + 71 (HTMLMapElement.cpp:82)
5   com.apple.WebCore             	0x0000000108f029b6 WebCore::HTMLAreaElement::imageElement() const + 86 (HTMLAreaElement.cpp:190)
6   com.apple.WebCore             	0x0000000108f02a19 WebCore::HTMLAreaElement::isFocusable() const + 25 (HTMLAreaElement.cpp:205)
7   com.apple.WebCore             	0x0000000108b17393 WebCore::Document::resetHiddenFocusElementTimer(WebCore::Timer<WebCore::Document>*) + 147 (Document.cpp:4731)
8   com.apple.WebCore             	0x0000000108b54cb3 WebCore::Timer<WebCore::Document>::fired() + 115 (Timer.h:114)
9   com.apple.WebCore             	0x0000000109f6f4e3 WebCore::ThreadTimers::sharedTimerFiredInternal() + 307 (ThreadTimers.cpp:132)
10  com.apple.WebCore             	0x0000000109f6f1f9 WebCore::ThreadTimers::sharedTimerFired() + 25 (ThreadTimers.cpp:106)
11  com.apple.WebCore             	0x0000000109d0da73 _ZN7WebCoreL10timerFiredEP16__CFRunLoopTimerPv + 67 (SharedTimerMac.mm:134)
12  com.apple.CoreFoundation      	0x00007fff8dc0c934 __CFRUNLOOP_IS_CALLING_OUT_TO_A_TIMER_CALLBACK_FUNCTION__ + 20
13  com.apple.CoreFoundation      	0x00007fff8dc0c486 __CFRunLoopDoTimer + 534
14  com.apple.CoreFoundation      	0x00007fff8dbece11 __CFRunLoopRun + 1617
15  com.apple.CoreFoundation      	0x00007fff8dbec486 CFRunLoopRunSpecific + 230
16  com.apple.HIToolbox           	0x00007fff988f82bf RunCurrentEventLoopInMode + 277
17  com.apple.HIToolbox           	0x00007fff988ff56d ReceiveNextEventCommon + 355
18  com.apple.HIToolbox           	0x00007fff988ff3fa BlockUntilNextEventMatchingListInMode + 62
19  com.apple.AppKit              	0x00007fff8c450779 _DPSNextEvent + 659
20  com.apple.AppKit              	0x00007fff8c45007d -[NSApplication nextEventMatchingMask:untilDate:inMode:dequeue:] + 135
21  com.apple.AppKit              	0x00007fff8c44c9b9 -[NSApplication run] + 470
22  com.apple.WebCore             	0x0000000109c5a9b2 WebCore::RunLoop::run() + 114 (RunLoopMac.mm:44)
23  com.apple.WebKit2             	0x0000000105cc12bc int WebKit::ChildProcessMain<WebKit::WebProcess, WebKit::WebContentProcessMainDelegate>(int, char**) + 604 (ChildProcessEntryPoint.h:92)
24  com.apple.WebKit2             	0x0000000105cc104b WebContentProcessMain + 27 (WebContentProcessMain.mm:179)
25  com.apple.WebProcess          	0x0000000105980acd _ZN6WebKitL13BootstrapMainEiPPc + 381
26  com.apple.WebProcess          	0x0000000105980942 main + 34
27  com.apple.WebProcess          	0x0000000105980914 start + 52

[Alexey Proskuryakov]

Looks like the follow-up fix broke a test on perfbot. It's quite surprising, but it already failed three times in a row after this commit.

Running Bindings/typed-array-construct-from-same-type.html (20 of 115)
error: Bindings/typed-array-construct-from-same-type.html
2013-10-05 05:24:44.800 DumpRenderTree[15052:707] CoreText CopyPropertiesForFontsMatchingRequest received mig IPC error (FFFFFFFFFFFFFECC) from font server
FAILED
Finished: 9.988322 s

[Ryosuke Niwa]

(In reply to comment #6)
> Looks like the follow-up fix broke a test on perfbot. It's quite surprising, but it already failed three times in a row after this commit.
> 
> Running Bindings/typed-array-construct-from-same-type.html (20 of 115)
> error: Bindings/typed-array-construct-from-same-type.html
> 2013-10-05 05:24:44.800 DumpRenderTree[15052:707] CoreText CopyPropertiesForFontsMatchingRequest received mig IPC error (FFFFFFFFFFFFFECC) from font server
> FAILED
> Finished: 9.988322 s

On which bot are you seeing this failure?

http://build.webkit.org/waterfall?show=Apple%20Lion%20Release%20%28Perf%29&show=Apple%20MountainLion%20Release%20%28Perf%29

looks green.

[Alexey Proskuryakov]

I must have been confused. I no longer see that happening repeatedly.