REGRESSION(r74593): removing nodes is 200+ times slower when selection is inside a shadow DOM

• Component: DOM
• Status: RESOLVED FIXED

[Igor Minar]

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.

[Alexey Proskuryakov]

Thank you for the report!

Do you know if there are any public sites affected by this?

[Igor Minar]

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.

[Igor Minar]

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.

[Igor Minar]

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.

[Igor Minar]

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.

[Emil A Eklund]

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.

[Emil A Eklund]

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.

[Ryosuke Niwa]

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.

[Ryosuke Niwa]

I think we need to throw WRONG_DOCUMENT_ERR in compareBoundaryPoints when two nodes have no common ancestors.

[Ryosuke Niwa]

Created attachment 89901 [details]
work in progress

Will finish this patch next week.

[Roland Steiner]

(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.

[Emil A Eklund]

Great, let me know if there is anything I can do to help!

[Ryosuke Niwa]

Created attachment 89953 [details]
reduction

Here's reduced test case

[Ryosuke Niwa]

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.

[Ryosuke Niwa]

Created attachment 90134 [details]
fixes the bug

[Early Warning System Bot]

Attachment 90134 [details] did not build on qt:
Build output: http://queues.webkit.org/results/8471166

[WebKit Review Bot]

Attachment 90134 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/8474124

[Ryosuke Niwa]

Created attachment 90141 [details]
fixed qt/chromium-linux build

[Dimitri Glazkov (Google)]

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?

[Ryosuke Niwa]

(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.

[Dimitri Glazkov (Google)]

(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.

[Igor Minar]

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.

[Ryosuke Niwa]

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.

[Ryosuke Niwa]

Committed r84265: <http://trac.webkit.org/changeset/84265>

[WebKit Review Bot]

http://trac.webkit.org/changeset/84265 might have broken Windows 7 Release (Tests)

[Igor Minar]

Just a quick note that I tested build r84295 and the issue is gone. Thanks!