Bug 104332 – NodeRenderingContext is slow due to ComposedShadowTreeWalker

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Hajime Morrita]

This is variant of Bug 103208.
Since I don't want to obsolete the original patch there, I'd file a separate bug.
My attempt is to kill the slowdown even if SHADOW_DOM is on.

[Hajime Morrita]

Created attachment 178190 [details]
Patch

[Hajime Morrita]

Need to measure this on Apple Mac. dom-modify is too noisy on Chromium to see difference.

[Hajime Morrita]

(In reply to comment #2)
> Need to measure this on Apple Mac. dom-modify is too noisy on Chromium to see difference.
Will do next week....

[Hajime Morrita]

Created attachment 178462 [details]
dom-modify innerHTML result

I confirmed similar progression similar to what Antti did at Bug 103208.
Note that this is not whole dom-modify. It runs only innerHTML sub test.

[Hajime Morrita]

First three trial came from patched, last three from original.

[Hajime Morrita]

Created attachment 178476 [details]
Patch

[Dimitri Glazkov (Google)]

Comment on attachment 178476 [details]
Patch

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

This looks nice. I am not sure whether the ShadowTreeJoint is the right term, since it needs explanation. Not sure if I have better ideas, but it seems like the shadow tree joint node is a node that impacts shadow tree algorithms... ImpactsShadowDOMAlgorithms is way too verbose though :)

> Source/WebCore/ChangeLog:29
> +        This chagne has 3-4% speedup on Dromaeo/dom-modify/innerHTML.

chagne -> change

> Source/WebCore/dom/ContainerNodeAlgorithms.h:261
> +    bool inDocument = node->inDocument();
> +    bool isShadowTreeJoint = node->isShadowTreeJoint();
> +    bool isContainerNode = node->isContainerNode();

Not sure why all these guys need to be pre-declared upfront.

[Elliott Sprehn]

Comment on attachment 178476 [details]
Patch

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

It seems like we could do this without the flag and having to maintain it everywhere. It also seems like we can make CSTW::nextSibling and previousSibling inline and have them check a bitfield based on the m_node that the ComposedShadowTreeWalker was created with for "started on a joint node". If that bitfield is false then the walker should fast path itself. Callers should not need to use special static methods.

> Source/WebCore/ChangeLog:23
> +        - The node is a child of shadow host.

Can we do this without the flag? Why not just parentOrHostNode() for being either an InsertionPointNode or having an elementShadow ?

> Source/WebCore/ChangeLog:49
> +        (WebCore::Element::childrenChanged): Maingains shadow tree joint flag.

Misspelled maintains? You have this all over the description. :)

> Source/WebCore/dom/NodeRenderingContext.cpp:95
> +    for (Node* sibling = ComposedShadowTreeWalker::traverseNextSibling(m_node); sibling; sibling = ComposedShadowTreeWalker::traverseNextSibling(sibling)) {

This doesn't seem right because if you started a non-joint node you'll never run into a joint node by walking siblings per your definition in the ChangeLog so you shouldn't need this complexity where you subvert the walker and use static methods. If that's the case when Walker::nextSibling() can just be smart enough to handle this all for you.

[Elliott Sprehn]

(In reply to comment #8)
> (From update of attachment 178476 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=178476&action=review
> ...
> 
> Can we do this without the flag? Why not just parentOrHostNode() for being either an InsertionPointNode or having an elementShadow ?

Specifically, this check seems equivalent:

// These are bitfield checks, they should be super fast.
bool isShadowPivot() { return !parentOrHostNode()->isInsertionPoint() && (!parentOrHostNode()->isElementNode() || toElement(parentOrHostNode())->shadow(); }

and you could do:

inline void ComposedShadowTreeWalker::nextSibling()
{
  m_node = m_node->isShadowPivot() ? slowTraverse() : m_node->nextSibling();
}

[Hajime Morrita]

I consume a flag here since even checking parent node and rare data is a 
const considering what we can do without shadow is just fetching
a word for m_firstChild.

I hope this change be comparable to Bug 103208, where these whole paths are
compiled out by SHADOW_DOM flag.

[Elliott Sprehn]

(In reply to comment #10)
> I consume a flag here since even checking parent node and rare data is a 
> const considering what we can do without shadow is just fetching
> a word for m_firstChild.
> 
> I hope this change be comparable to Bug 103208, where these whole paths are
> compiled out by SHADOW_DOM flag.

Can you try the bool on CSTW construction and inline path instead? We also can't compile this check out as we need to support traversing the composed children for the new DOM based generated content to work properly with <input>... unless we plan to drop support for all generated content on shadows again.

[Elliott Sprehn]

(In reply to comment #11)
> (In reply to comment #10)
> > I consume a flag here since even checking parent node and rare data is a 
> > const considering what we can do without shadow is just fetching
> > a word for m_firstChild.
> > 
> > I hope this change be comparable to Bug 103208, where these whole paths are
> > compiled out by SHADOW_DOM flag.
> 
> Can you try the bool on CSTW construction and inline path instead? We also can't compile this check out as we need to support traversing the composed children for the new DOM based generated content to work properly with <input>... unless we plan to drop support for all generated content on shadows again.

Also note that Antti himself has said there's no reason to avoid bitfield checks with fancy acrobatics: https://bugs.webkit.org/show_bug.cgi?id=101448

So checking parentOrHostNode()->isShadowRoot() || parentOrHostNode()->isInsertionPoint() on CSTW should be fine.

[Hajime Morrita]

(In reply to comment #12)
> (In reply to comment #11)
> > (In reply to comment #10)
> > > I consume a flag here since even checking parent node and rare data is a 
> > > const considering what we can do without shadow is just fetching
> > > a word for m_firstChild.
> > > 
> > > I hope this change be comparable to Bug 103208, where these whole paths are
> > > compiled out by SHADOW_DOM flag.
> > 
> > Can you try the bool on CSTW construction and inline path instead? We also can't compile this check out as we need to support traversing the composed children for the new DOM based generated content to work properly with <input>... unless we plan to drop support for all generated content on shadows again.
> 
> Also note that Antti himself has said there's no reason to avoid bitfield checks with fancy acrobatics: https://bugs.webkit.org/show_bug.cgi?id=101448
This doesn't conflict introducing shadow-tree-joint flag ...
Anyway, I'm now aware that we need to take care of generated content here.
But I don't think it is good idea to mix shadow tree walking and generated content. 
I'm introducing NodeRenderingTraversal module as a sister of NodeTraversal ns,
which is going to be added by Bug 104507. We could manage generated content things there.
Let me try... before you land Bug 178634 :-)

[Hajime Morrita]

Created attachment 178690 [details]
Benchmark result with non-bitflag version

I tried non bitflag version but the benchmark doesn't say it's good. 
The last three columns came from non-flag version.

[Elliott Sprehn]

(In reply to comment #14)
> Created an attachment (id=178690) [details]
> Benchmark result with non-bitflag version
> 
> I tried non bitflag version but the benchmark doesn't say it's good. 
> The last three columns came from non-flag version.

Hmm, that's really suspicious since isShadowRoot() and isInsertionPoint() are both bitfields and checking two bitfields vs 1 (isShadowPivot) shouldn't have any noticeable difference... Okay lets go with this and perhaps we can try to get rid of this new bitfield in the future.

[Dimitri Glazkov (Google)]

Comment on attachment 178476 [details]
Patch

Please take care of the remaining comments and let's file two bugs: one to track better naming of ShadowTreeJoint and one to combine flags.

[Hajime Morrita]

(In reply to comment #16)
> (From update of attachment 178476 [details])
> Please take care of the remaining comments and let's file two bugs: one to track better naming of ShadowTreeJoint and one to combine flags.

I can't land this since it conflicts Elliot's pseudo element patch.
I'll adopt the change and ask for review again.

[Hajime Morrita]

Created attachment 178998 [details]
Patch

[Elliott Sprehn]

Comment on attachment 178998 [details]
Patch

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

This patch is going to make generated content much slower, and also makes appending children to a ShadowRoot n^2 which is bad. Please don't do this :(

> Source/WebCore/dom/Element.cpp:2160
> +        child->resetShadowTreeJoint();

This doesn't seem like the right place for this. Why does adding a pseudo element reset the join bits? I don't like this because it means adding :before and :after to a page dynamically now causes an extra walk across all children of the node you defined it on.

ex. You made <div> ... thousands of nodes ... </div> and then adding div:before {} much slower by introducing a new DOM walk.

> Source/WebCore/dom/Element.h:373
> +    bool isChildShadowTreeJoint() const { return isInsertionPoint() || shadow() || hasPseudoElements(); }

This is way too agressive. You're making everything with :before or :after into a joint node which is not correct.

> Source/WebCore/dom/ShadowRoot.cpp:330
> +        child->setShadowTreeJoint();

Again this is bad, you make appendChild() to ShadowRoot into an O(n^2) operation. This needs to be handled inside appendChild() itself where you check if the parent isShadowRoot() and update.

[Elliott Sprehn]

(In reply to comment #19)
> (From update of attachment 178998 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=178998&action=review
> ...
> Again this is bad, you make appendChild() to ShadowRoot into an O(n^2) operation. This needs to be handled inside appendChild() itself where you check if the parent isShadowRoot() and update.

More correctly Node::insertedInto, but adding a ShadowRoot to an existing element needs to update every child as well so that won't work... instead what if inside Node::attach() and Node::detach() you look at your parent node and update the bits? That removes the n^2 traversals.

Also can we call the bit "needsShadowRootAwareAttach" ? :before and :after are not "Shadow Joints", especially when the page has no shadows. :)

[Hajime Morrita]

Created attachment 179014 [details]
WIP

[Hajime Morrita]

Comment on attachment 178998 [details]
Patch

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

Elliot, I noticed your comment now. I'll do some routine work like adding files to exp file before addressing your comment.

>> Source/WebCore/dom/Element.cpp:2160
>> +        child->resetShadowTreeJoint();
> 
> This doesn't seem like the right place for this. Why does adding a pseudo element reset the join bits? I don't like this because it means adding :before and :after to a page dynamically now causes an extra walk across all children of the node you defined it on.
> 
> ex. You made <div> ... thousands of nodes ... </div> and then adding div:before {} much slower by introducing a new DOM walk.

Right. we need some compromise here.

>> Source/WebCore/dom/ShadowRoot.cpp:330
>> +        child->setShadowTreeJoint();
> 
> Again this is bad, you make appendChild() to ShadowRoot into an O(n^2) operation. This needs to be handled inside appendChild() itself where you check if the parent isShadowRoot() and update.

Oh I overlooked the comment. I should take care of this in coming patch.

[Hajime Morrita]

Created attachment 179018 [details]
WIP

[Hajime Morrita]

Created attachment 179025 [details]
WIP

[WebKit Review Bot]

Comment on attachment 179025 [details]
WIP

Attachment 179025 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/15259959

New failing tests:
fast/dom/shadow/pseudoclass-update-disabled-fieldset.html
fast/dom/shadow/dynamically-created-shadow-root.html
fast/dom/shadow/pseudoclass-update-link-anchor.html
fast/dom/shadow/focus-navigation.html
fast/dom/shadow/pseudoclass-update-target.html
fast/dom/shadow/distribution-className-modified.html
fast/dom/shadow/pseudoclass-update-enabled-fieldset.html
fast/dom/shadow/content-element-select-dynamic.html
editing/shadow/select-contenteditable-shadowhost.html
fast/dom/shadow/pseudoclass-update-indeterminate-progress.html
fast/dom/shadow/content-element-move.html
fast/dom/shadow/pseudoclass-update-checked-input.html
fast/dom/shadow/pseudoclass-update-disabled-select.html
fast/dom/shadow/pseudoclass-update-visited-area.html
fast/dom/shadow/pseudoclass-update-disabled-textarea.html
fast/dom/shadow/pseudoclass-update-enabled-select.html
fast/dom/shadow/distribution-id-modified.html
fast/dom/shadow/no-renderers-for-light-children.html
fast/dom/shadow/pseudoclass-update-indeterminate-input.html
editing/shadow/shadow-selection-not-exported.html
editing/shadow/contenteditable-propagation-at-shadow-boundary.html
fast/dom/shadow/pseudoclass-update-link-area.html
fast/dom/shadow/pseudoclass-update-visited-anchor.html
fast/dom/shadow/multiple-shadowroot-rendering.html
fast/dom/shadow/pseudoclass-update-enabled-button.html
fast/dom/shadow/pseudoclass-update-disabled-input.html
fast/dom/shadow/pseudoclass-update-enabled-input.html
fast/dom/shadow/distribution-attribute-modified.html
fast/dom/shadow/pseudoclass-update-enabled-textarea.html
fast/dom/shadow/pseudoclass-update-disabled-button.html

[WebKit Review Bot]

Comment on attachment 179025 [details]
WIP

Attachment 179025 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/15296118

New failing tests:
fast/dom/shadow/pseudoclass-update-disabled-fieldset.html
fast/dom/shadow/dynamically-created-shadow-root.html
fast/dom/shadow/pseudoclass-update-link-anchor.html
fast/dom/shadow/focus-navigation.html
fast/dom/shadow/pseudoclass-update-target.html
fast/dom/shadow/distribution-className-modified.html
fast/dom/shadow/pseudoclass-update-enabled-fieldset.html
fast/dom/shadow/content-element-select-dynamic.html
editing/shadow/select-contenteditable-shadowhost.html
fast/dom/shadow/pseudoclass-update-indeterminate-progress.html
fast/dom/shadow/content-element-move.html
fast/dom/shadow/pseudoclass-update-checked-input.html
fast/dom/shadow/pseudoclass-update-disabled-select.html
fast/dom/shadow/pseudoclass-update-visited-area.html
fast/dom/shadow/pseudoclass-update-disabled-textarea.html
fast/dom/shadow/pseudoclass-update-enabled-select.html
fast/dom/shadow/distribution-id-modified.html
fast/dom/shadow/no-renderers-for-light-children.html
fast/dom/shadow/pseudoclass-update-indeterminate-input.html
editing/shadow/shadow-selection-not-exported.html
editing/shadow/contenteditable-propagation-at-shadow-boundary.html
fast/dom/shadow/pseudoclass-update-link-area.html
fast/dom/shadow/pseudoclass-update-visited-anchor.html
fast/dom/shadow/multiple-shadowroot-rendering.html
fast/dom/shadow/pseudoclass-update-enabled-button.html
fast/dom/shadow/pseudoclass-update-disabled-input.html
fast/dom/shadow/pseudoclass-update-enabled-input.html
fast/dom/shadow/distribution-attribute-modified.html
fast/dom/shadow/pseudoclass-update-enabled-textarea.html
fast/dom/shadow/pseudoclass-update-disabled-button.html

[Elliott Sprehn]

I had an idea for an even better way to do this, lets just pass the need for a shadow tree walker down through ::attach() into createRendererIfNeeded and finally sets a boolean on the constructor for NodeRenderingContext.

and then you just need to update ContainerNode::attachChildren to do:

// outside the loop.
bool needsWalker = isShadowRoot() || isInsertionPoint() || hasPseudoElements();

// inside the loop...
child->attach(needsWalker);

and inside Element::attach(bool walkerIsNeeded) you do

createRendererIfNeeded(walkerIsNeeded)

and NodeRenderingContext(this, walkerIsNeeded).createRendererForElementIfNeeded();

This saves us from all these n^2 traversals and having to maintain the bit and should be very fast.

[Hajime Morrita]

(In reply to comment #27)
> I had an idea for an even better way to do this, lets just pass the need for a shadow tree walker down through ::attach() into createRendererIfNeeded and finally sets a boolean on the constructor for NodeRenderingContext.

My thought was a variation of this - We can pass NodeRenderingContext as a parameter to attach().
We can tell NRC which node is the parent/caller of attach().

Changing the signature of attach() is certainly a big change and that's why I'm hesitating to do that.
But we could probably do that in a follow up patch instead of this one.

[Hajime Morrita]

(In reply to comment #27)
> 
> and NodeRenderingContext(this, walkerIsNeeded).createRendererForElementIfNeeded();
Noticed that this approach might not work since the parent can change during
nextSibling/previosuSibling traversal: The next sibling of fast-traversable-node can be 
not-fast-traversable. It can be an insertion point for example.

[Hajime Morrita]

Created attachment 179198 [details]
Patch

[Hajime Morrita]

Created attachment 179200 [details]
Fixed ChangeLog

[Hajime Morrita]

Created attachment 179214 [details]
Patch

[Hajime Morrita]

Created attachment 179215 [details]
benchmark result showing 2-3% win for document-modify-innerhtml

This one is no longer as strong as before.  The improvement is now 2-3%. 
I'd like to land this and attack further in separate change.
The patch will be bigger otherwise.

[Dimitri Glazkov (Google)]

Comment on attachment 179214 [details]
Patch

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

> Source/WebCore/ChangeLog:17
> +        chagne, NRC directly used CSTW. This NRT module hides and narrows

chagne -> change

> Source/WebCore/ChangeLog:21
> +          doesn't need to use CSTW and just goes neighboring nodes in a plain DOM way.

doesn't -> don't, "just goes _to_ neighboring nodes"

> Source/WebCore/ChangeLog:25
> +        - CSTW::ParentTraversalDetails is moved and renamed to

This could've been a nice separate patch :-\

> Source/WebCore/ChangeLog:37
> +        node flag. Each DOM node is now markd as NeedsShadowTreeWalker if
> +        it requires non-trivial traversal in NRT which uses CSTW. This

This is great.

> Source/WebCore/ChangeLog:44
> +        - The node is a pseudo element or

or...? :)

> Source/WebCore/ChangeLog:46
> +        This criteria criteria is defined in Node::needsShadowTreeWalkerSlow(). The node actually needs

zap one "criteria" from the sentence. You have two.

> Source/WebCore/dom/ContainerNode.h:268
> +inline bool Node::needsShadowTreeWalker() const

Looks like this is the hottest function in the whole patch.

> Source/WebCore/dom/NodeRenderingTraversal.h:36
> +namespace NodeRenderingTraversal {

The name is a touch obtuse, but I don't have better ideas.

> Source/WebCore/html/HTMLOptGroupElement.cpp:29
> +#include "ElementShadow.h"

Why do we need this?

> Source/WebCore/html/HTMLOptionElement.cpp:32
> +#include "ElementShadow.h"

And this?

[Hajime Morrita]

Thanks for the review! I can land this.

(In reply to comment #34)
> > Source/WebCore/dom/ContainerNode.h:268
> > +inline bool Node::needsShadowTreeWalker() const
> 
> Looks like this is the hottest function in the whole patch.
> 

Yeah, it's sad to see the parent here. I should figure out how we can get rid of it.

> 
> > Source/WebCore/html/HTMLOptGroupElement.cpp:29
> > +#include "ElementShadow.h"
> 
> Why do we need this?
> 
> > Source/WebCore/html/HTMLOptionElement.cpp:32
> > +#include "ElementShadow.h"
> 
> And this?

We originally included ComposedShadowTreeWalker.h through NodeRenderingContext.h
but we no longer do. That change revealed these implicit dependency. I'll explain it in ChangeLog.

[Hajime Morrita]

Created attachment 179411 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 179411 [details]
Patch for landing

Rejecting attachment 179411 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 1

/mnt/git/webkit-commit-queue/Source/WebCore/ChangeLog neither lists a valid reviewer nor contains the string "Unreviewed" or "Rubber stamp" (case insensitive).

Full output: http://queues.webkit.org/results/15319529

[Hajime Morrita]

Created attachment 179413 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 179413 [details]
Patch for landing

Clearing flags on attachment: 179413

Committed r137715: <http://trac.webkit.org/changeset/137715>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.