Bug 57061 - REGRESSION(r74593): removing nodes is 200+ times slower when selection is inside a shadow DOM
Summary: REGRESSION(r74593): removing nodes is 200+ times slower when selection is ins...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Macintosh Intel OS X 10.5
: P1 Major
Assignee: Ryosuke Niwa
URL:
Keywords: HasReduction
Depends on:
Blocks:
 
Reported: 2011-03-24 15:42 PDT by Igor Minar
Modified: 2011-05-19 11:14 PDT (History)
12 users (show)

See Also:


Attachments
reduced test case (2.30 KB, text/html)
2011-03-24 15:42 PDT, Igor Minar
no flags Details
timeline without focus (28.90 KB, image/png)
2011-03-28 16:54 PDT, Igor Minar
no flags Details
timeline with focus (375.36 KB, image/png)
2011-03-28 16:55 PDT, Igor Minar
no flags Details
work in progress (9.62 KB, patch)
2011-04-15 18:43 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
reduction (553 bytes, text/html)
2011-04-17 11:34 PDT, Ryosuke Niwa
no flags Details
fixes the bug (12.70 KB, patch)
2011-04-18 19:22 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
fixed qt/chromium-linux build (12.70 KB, patch)
2011-04-18 21:36 PDT, Ryosuke Niwa
dglazkov: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Igor Minar 2011-03-24 15:42:34 PDT
Created attachment 86849 [details]
reduced test case

This issue is related to issue 57059 and makes the DOM node removal super slow.

If all of these are true:
- there is nth-child pseudo class is applied to li elements in a list
- there is an input field with focus in the document (issue 57059)
- some of the elements are removed from the list (direction: top/middle to bottom)

the removal operation takes up to 200x longer than without the selector (tested with r81868).

Attached is a test case that demonstrates this issue.
- type "x" into the input field to remove 1000 li nodes
- time it took to do that is displayed on the page
- empty the input field to cause new 1000 nodes to be added
- click on the "toggle css" button to apply the nth-child selector to li elements
- type "x" into the input field to again remove 1000 li's
- note the time. it should be considerably higher
- if you remove the css from li's by clicking on the toggle button again and repeat the addition/removal of nodes, you'll notice that while the removal is faster than the slowest case, it's still ~100x slower than when you refresh the page and start from scratch.

For some reason applying the css and triggering issue 57059 makes the dom removal really slow and the effect lasts even after the css was removed.

The issue was introduced in r75294 and is still present in r81868.
Comment 1 Alexey Proskuryakov 2011-03-24 17:52:16 PDT
Thank you for the report!

Do you know if there are any public sites affected by this?
Comment 2 Igor Minar 2011-03-24 20:31:29 PDT
At google we have a for now internal-only app that is affected. The testcase I attached is minuscule reduction of the affected part of our code base.

The functionality that is affected is a client side search. User types something into a input box and we update the DOM by removing all table rows that represent the records that were not matched by the user query.

I would say that removing table rows or list elements that were styled with nth-child(odd) (or nth-child(even)) because of user input is quite common scenario and affects more than us.
Comment 3 Igor Minar 2011-03-28 16:54:30 PDT
Created attachment 87238 [details]
timeline without focus

Chrome Timeline graph showing how quick removal of 289 table row nodes (styled with nth-child(even)) is when our input field doesn't have the focus.
Comment 4 Igor Minar 2011-03-28 16:55:14 PDT
Created attachment 87239 [details]
timeline with focus

Chrome Timeline graph showing how slow removal of 289 table row nodes (styled with nth-child(even)) is when our input field does have the focus.
Comment 5 Igor Minar 2011-03-28 17:00:18 PDT
We are still struggling with this one.

I attached screenshots showing that removing nodes styled with nth-child pseudo selector while an input field on the page has focus, results in "Recalculate Style" operation after removal of each of our 289 nodes.

This doesn't happen when I execute the very same code path, without previously calling focus() on the input field.

I also noticed that while my reduction exhibits the issue only when nodes are removed top-to-bottom, in our production app, the order of removal doesn't matter. The removal is slow in both directions. That makes me think that there is one more element in this puzzle that I haven't discovered yet.

Any hints would be very welcome.
Comment 6 Emil A Eklund 2011-04-15 14:09:08 PDT
Looks like the regression was caused by r74593. 

In SelectionController::respondToNodeModification

        if (!ec && (compareResult == Range::NODE_BEFORE_AND_AFTER || compareResult == Range::NODE_INSIDE)) {

is true when the input field has focus and thus a reflow is triggered for each call to removeChild in the test.
Comment 7 Emil A Eklund 2011-04-15 14:21:10 PDT
Ryosuke, would you mind taking a look at this? I don't quite understand what you fixed in r74593 and how this is supposed to work.
Comment 8 Ryosuke Niwa 2011-04-15 18:02:55 PDT
The bug is coming from Range::compareNode.  It returns NODE_INSIDE when a range is inside a shadow DOM and a node is outside of the shadow DOM.  We need to fix this.
Comment 9 Ryosuke Niwa 2011-04-15 18:11:00 PDT
I think we need to throw WRONG_DOCUMENT_ERR in compareBoundaryPoints when two nodes have no common ancestors.
Comment 10 Ryosuke Niwa 2011-04-15 18:43:30 PDT
Created attachment 89901 [details]
work in progress

Will finish this patch next week.
Comment 11 Roland Steiner 2011-04-15 19:14:28 PDT
(In reply to comment #9)
> I think we need to throw WRONG_DOCUMENT_ERR in compareBoundaryPoints when two nodes have no common ancestors.

Yes, ShadowRoot being comparable to DocumentFragment makes throwing WRONG_DOCUMENT_ERR probably a good choice w.r.t. the DOMRange spec.
Comment 12 Emil A Eklund 2011-04-15 19:34:49 PDT
Great, let me know if there is anything I can do to help!
Comment 13 Ryosuke Niwa 2011-04-17 11:34:58 PDT
Created attachment 89953 [details]
reduction

Here's reduced test case
Comment 14 Ryosuke Niwa 2011-04-17 11:37:58 PDT
nth-child is nothing to do with this regression.  It's just that nth-child slows rendering down and makes it more obvious.  Slow re-layout of nth-child should be addressed by another bug if necessary.
Comment 15 Ryosuke Niwa 2011-04-18 19:22:27 PDT
Created attachment 90134 [details]
fixes the bug
Comment 16 Early Warning System Bot 2011-04-18 19:29:23 PDT
Attachment 90134 [details] did not build on qt:
Build output: http://queues.webkit.org/results/8471166
Comment 17 WebKit Review Bot 2011-04-18 19:54:11 PDT
Attachment 90134 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/8474124
Comment 18 Ryosuke Niwa 2011-04-18 21:36:49 PDT
Created attachment 90141 [details]
fixed qt/chromium-linux build
Comment 19 Dimitri Glazkov (Google) 2011-04-18 21:51:45 PDT
Comment on attachment 90141 [details]
fixed qt/chromium-linux build

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

> Source/WebCore/ChangeLog:18
> +        No new tests because this is a performance improvement and the fix in Range cannot be tested since shadow DOM
> +        isn't exposed to JavaScript.

I am not sure I follow -- the original reduction showed there was a performance issue. Perhaps a perf test would be at least useful here?
Comment 20 Ryosuke Niwa 2011-04-18 22:05:35 PDT
(In reply to comment #19)
> (From update of attachment 90141 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=90141&action=review
> 
> > Source/WebCore/ChangeLog:18
> > +        No new tests because this is a performance improvement and the fix in Range cannot be tested since shadow DOM
> > +        isn't exposed to JavaScript.
> 
> I am not sure I follow -- the original reduction showed there was a performance issue. Perhaps a perf test would be at least useful here?

No, perf test only checks asymptotic behavior and this performance regression doesn't change the asymptotic behavior so I don't think it works.  I can check in a reduced test case with a really large number of nodes but that'll be very unreliable and I'm afraid that it's going to fail too.  I also considered verifying the fix I added to Range's method but that's not possible now because shadow DOM isn't accessible from JavaScript.
Comment 21 Dimitri Glazkov (Google) 2011-04-19 07:59:50 PDT
(In reply to comment #20)
> (In reply to comment #19)
> > (From update of attachment 90141 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=90141&action=review
> > 
> > > Source/WebCore/ChangeLog:18
> > > +        No new tests because this is a performance improvement and the fix in Range cannot be tested since shadow DOM
> > > +        isn't exposed to JavaScript.
> > 
> > I am not sure I follow -- the original reduction showed there was a performance issue. Perhaps a perf test would be at least useful here?
> 
> No, perf test only checks asymptotic behavior and this performance regression doesn't change the asymptotic behavior so I don't think it works.  I can check in a reduced test case with a really large number of nodes but that'll be very unreliable and I'm afraid that it's going to fail too.  I also considered verifying the fix I added to Range's method but that's not possible now because shadow DOM isn't accessible from JavaScript.

Ah I see. Well, hopefully when Kent-san converts text inputs (https://bugs.webkit.org/show_bug.cgi?id=54179) to the new shadow DOM, we'll be able to write a test, since we do expose layoutTestController.shadowRoot(node) for it.
Comment 22 Igor Minar 2011-04-19 08:28:19 PDT
Thanks guys for looking into this issue.

Does the original test case work fast in all cases? I'll be happy to test the fix when it lands in nightly builds.
Comment 23 Ryosuke Niwa 2011-04-19 10:30:17 PDT
Comment on attachment 90141 [details]
fixed qt/chromium-linux build

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

>>>> Source/WebCore/ChangeLog:18
>>>> +        isn't exposed to JavaScript.
>>> 
>>> I am not sure I follow -- the original reduction showed there was a performance issue. Perhaps a perf test would be at least useful here?
>> 
>> No, perf test only checks asymptotic behavior and this performance regression doesn't change the asymptotic behavior so I don't think it works.  I can check in a reduced test case with a really large number of nodes but that'll be very unreliable and I'm afraid that it's going to fail too.  I also considered verifying the fix I added to Range's method but that's not possible now because shadow DOM isn't accessible from JavaScript.
> 
> Ah I see. Well, hopefully when Kent-san converts text inputs (https://bugs.webkit.org/show_bug.cgi?id=54179) to the new shadow DOM, we'll be able to write a test, since we do expose layoutTestController.shadowRoot(node) for it.

Yeah, it's unfortunate that the bug 54179 hasn't been fixed yet.
Comment 24 Ryosuke Niwa 2011-04-19 11:05:58 PDT
Committed r84265: <http://trac.webkit.org/changeset/84265>
Comment 25 WebKit Review Bot 2011-04-19 12:03:16 PDT
http://trac.webkit.org/changeset/84265 might have broken Windows 7 Release (Tests)
Comment 26 Igor Minar 2011-04-19 23:42:04 PDT
Just a quick note that I tested build r84295 and the issue is gone. Thanks!