Bug 103372 – checkAcceptChild() needs fewer virtual calls

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

[Hajime Morrita]

There are a few virtual method calls which can be eliminated.
It's worth eliminating since the function is hot in DOM mutations.

[Hajime Morrita]

Created attachment 176224 [details]
Patch

[Hajime Morrita]

Created attachment 176225 [details]
Updated to ToT

[Ojan Vafai]

Comment on attachment 176225 [details]
Updated to ToT

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

I like the overall direction of this patch, but it needs a bit more work.

> Source/WebCore/ChangeLog:24
> +        (WebCore::isChildTypeAllowed): Adopted isDocumentTypeNode(), which is faster than nodeType().

Why is this faster? isDocumentTypeNode just calls nodeType(), no?

> Source/WebCore/dom/ContainerNode.cpp:135
> +static inline bool isChildTypeAllowed(Node* newParent, Node* child)

Can we make these non-static, private methods? They all take "this" as the first argument in all the callers.

> Source/WebCore/dom/ContainerNode.cpp:147
> +static inline void checkAcceptChild(Node* newParent, Node* newChild, Node* oldChild, ExceptionCode& ec)

At this point, may as well rename this to checkAddChild.

> Source/WebCore/dom/ContainerNode.cpp:173
> +        if (oldChild && newParent->isDocumentNode() && !toDocument(newParent)->canReplaceChild(newChild, oldChild)) {
> +            ec = HIERARCHY_REQUEST_ERR;
> +            return;
> +        }

Can you just keep this in checkReplaceChild? You can do this call before calling checkAcceptChild. It seems unlikely to me that you gain much performance benefit by putting it here and it makes the code more confusing since now checkAcceptChild also doubles as checking whether the child can be replaced.

If you find that this does measurably improve performance, then maybe we should consider it (maybe even as a separate followup patch?), but for now, I don't think it's worth the confusion.

> Source/WebCore/dom/ContainerNode.cpp:178
> +        if (!isChildTypeAllowed(newParent, newChild)) {
> +            ec = HIERARCHY_REQUEST_ERR;
> +            return;
> +        }

It looks to me that moving this here from checkAddChild fixes a bug with replaceChild. Mind writing a test for this case? Also, you could commit that change first, which would simplify this patch since then you'd just be moving the function.

> Source/WebCore/dom/ContainerNode.cpp:182
> +    // HIERARCHY_REQUEST_ERR: Raised if this node is of a type that does not allow children of the type of the
> +    // newChild node, or if the node to append is one of this node's ancestors.

I know this is just copy-pasted, but I don't think this comment adds any value. It's obvious what the code below is doing.

> Source/WebCore/dom/ContainerNode.cpp:186
> +    if (newChild->contains(newParent)) {
> +        ec = HIERARCHY_REQUEST_ERR;
> +        return;

If you move this above the previous if-else statement, you could early return in the if and then not need the else statement. Would make this code a bit easier to read. I know that this is the slow part of this function, but I think it's fine if we're a little slower in error cases. Error cases should almost never be hit and are unlikely to be a performance bottleneck with these APIs I think.

> Source/WebCore/dom/ContainerNode.cpp:199
> +    if (ec)
> +        return;

Don't need this.

> Source/WebCore/dom/ContainerNode.cpp:203
> +// This method is used to do strict error-checking when adding children via
> +// the public DOM API (e.g., appendChild()).

I know this comment was in the previous version of the code, but I don't think it actually adds any value. All our methods that take ExceptionCodes are for servicing public DOM apis.

> Source/WebCore/dom/ContainerNode.cpp:208
> +    if (ec)
> +        return;

Don't need this.

[Ryosuke Niwa]

Comment on attachment 176225 [details]
Updated to ToT

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

>> Source/WebCore/ChangeLog:24
>> +        (WebCore::isChildTypeAllowed): Adopted isDocumentTypeNode(), which is faster than nodeType().
> 
> Why is this faster? isDocumentTypeNode just calls nodeType(), no?

I think he meant that it's more concise and one can type it faster but I don't think we need this description.

>> Source/WebCore/dom/ContainerNode.cpp:135
>> +static inline bool isChildTypeAllowed(Node* newParent, Node* child)
> 
> Can we make these non-static, private methods? They all take "this" as the first argument in all the callers.

I'm not sure if that's necessarily an improvement. These functions don't access private/protected member functions of Node.

> Source/WebCore/dom/ContainerNode.cpp:140
> +    for (Node *n = child->firstChild(); n; n = n->nextSibling()) {

Please spell out node.

> Source/WebCore/dom/ContainerNode.cpp:152
> +        ec = NOT_FOUND_ERR;
> +        return;

Since this isn't exposed via IDL, you might as well as return ExceptionCode. It'll make code read much better.

> Source/WebCore/dom/ContainerNode.cpp:192
> +    if (!oldChild) {

We should probably have ASSERT(oldChild) in checkAcceptChild.

[Hajime Morrita]

Created attachment 176375 [details]
Patch

[Hajime Morrita]

Comment on attachment 176225 [details]
Updated to ToT

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

>>> Source/WebCore/ChangeLog:24
>>> +        (WebCore::isChildTypeAllowed): Adopted isDocumentTypeNode(), which is faster than nodeType().
>> 
>> Why is this faster? isDocumentTypeNode just calls nodeType(), no?
> 
> I think he meant that it's more concise and one can type it faster but I don't think we need this description.

Oh, I meant to say isDocumentFragment(). I would remove this line anyway.

>>> Source/WebCore/dom/ContainerNode.cpp:135
>>> +static inline bool isChildTypeAllowed(Node* newParent, Node* child)
>> 
>> Can we make these non-static, private methods? They all take "this" as the first argument in all the callers.
> 
> I'm not sure if that's necessarily an improvement. These functions don't access private/protected member functions of Node.

It seems rather matter of taste in this case.
I'd keep this as is, just changing the type of the parameter to ContainerNode.

>> Source/WebCore/dom/ContainerNode.cpp:140
>> +    for (Node *n = child->firstChild(); n; n = n->nextSibling()) {
> 
> Please spell out node.

done.

>> Source/WebCore/dom/ContainerNode.cpp:147
>> +static inline void checkAcceptChild(Node* newParent, Node* newChild, Node* oldChild, ExceptionCode& ec)
> 
> At this point, may as well rename this to checkAddChild.

Right. Done, and removed oldChild parameter.

>> Source/WebCore/dom/ContainerNode.cpp:152
>> +        return;
> 
> Since this isn't exposed via IDL, you might as well as return ExceptionCode. It'll make code read much better.

Good point. Done.

>> Source/WebCore/dom/ContainerNode.cpp:173
>> +        }
> 
> Can you just keep this in checkReplaceChild? You can do this call before calling checkAcceptChild. It seems unlikely to me that you gain much performance benefit by putting it here and it makes the code more confusing since now checkAcceptChild also doubles as checking whether the child can be replaced.
> 
> If you find that this does measurably improve performance, then maybe we should consider it (maybe even as a separate followup patch?), but for now, I don't think it's worth the confusion.

Oh, right. I didn't do this for performance. It's just a consequence of try-and-error.

>> Source/WebCore/dom/ContainerNode.cpp:178
>> +        }
> 
> It looks to me that moving this here from checkAddChild fixes a bug with replaceChild. Mind writing a test for this case? Also, you could commit that change first, which would simplify this patch since then you'd just be moving the function.

I'm sorry but I don't follow. Which bug are you talking about?

>> Source/WebCore/dom/ContainerNode.cpp:182
>> +    // newChild node, or if the node to append is one of this node's ancestors.
> 
> I know this is just copy-pasted, but I don't think this comment adds any value. It's obvious what the code below is doing.

Done.

>> Source/WebCore/dom/ContainerNode.cpp:186
>> +        return;
> 
> If you move this above the previous if-else statement, you could early return in the if and then not need the else statement. Would make this code a bit easier to read. I know that this is the slow part of this function, but I think it's fine if we're a little slower in error cases. Error cases should almost never be hit and are unlikely to be a performance bottleneck with these APIs I think.

Good point. We hit this in most cases anyway.

>> Source/WebCore/dom/ContainerNode.cpp:192
>> +    if (!oldChild) {
> 
> We should probably have ASSERT(oldChild) in checkAcceptChild.

I got rid of the oldChild parameter there.

>> Source/WebCore/dom/ContainerNode.cpp:199
>> +        return;
> 
> Don't need this.

Done.

>> Source/WebCore/dom/ContainerNode.cpp:203
>> +// the public DOM API (e.g., appendChild()).
> 
> I know this comment was in the previous version of the code, but I don't think it actually adds any value. All our methods that take ExceptionCodes are for servicing public DOM apis.

Removed.

>> Source/WebCore/dom/ContainerNode.cpp:208
>> +        return;
> 
> Don't need this.

Done.

[Build Bot]

Comment on attachment 176375 [details]
Patch

Attachment 176375 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15023289

[Hajime Morrita]

Created attachment 176394 [details]
Patch

[Ojan Vafai]

Comment on attachment 176225 [details]
Updated to ToT

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

>>> Source/WebCore/dom/ContainerNode.cpp:178
>>> +        }
>> 
>> It looks to me that moving this here from checkAddChild fixes a bug with replaceChild. Mind writing a test for this case? Also, you could commit that change first, which would simplify this patch since then you'd just be moving the function.
> 
> I'm sorry but I don't follow. Which bug are you talking about?

Oh, I'm not sure. I think I was misreading the code. I thought there was a codepath where we weren't calling isChildTypeAllowed before and now we are, but I don't see it now that I look at the patch again. :)

[Ojan Vafai]

Comment on attachment 176394 [details]
Patch

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

This patch looks great to me. Too tired now to give it a confident r+. If another reviewer wants to, go ahead, otherwise, I'll take a look in the morning.

> Source/WebCore/dom/ContainerNode.cpp:176
> +    if (ExceptionCode ec = checkAddChild(parent, newChild))
> +        return ec;

This now calls isChildTypeAllowed for Document nodes where the old code didn't. I suppose there actually no change in exposed behavior and all we're doing is a little extra work that's almost certainly never going to be a performance problem. So it seems fine to me, but it seemed worth calling out.

[WebKit Review Bot]

Comment on attachment 176394 [details]
Patch

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

New failing tests:
dom/xhtml/level3/core/nodereplacechild22.xhtml
fast/body-propagation/background-color/003-xhtml.xhtml
dom/xhtml/level3/core/nodereplacechild13.xhtml
fast/body-propagation/overflow/003.html
fast/body-propagation/overflow/003-xhtml.xhtml
fast/body-propagation/background-image/003.html
fast/dom/Document/replace-child.html
dom/xhtml/level3/core/nodereplacechild23.xhtml
fast/body-propagation/background-image/003-xhtml.xhtml
dom/xhtml/level3/core/documentgetdoctype01.xhtml
dom/xhtml/level3/core/nodecomparedocumentposition02.xhtml
fast/body-propagation/background-color/003.html

[Ryosuke Niwa]

Comment on attachment 176394 [details]
Patch

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

> Source/WebCore/ChangeLog:10
> +        scope, This change moves Node::checkReplaceChild() and

moves > makes?

> Source/WebCore/dom/ContainerNode.cpp:140
> +    for (Node *node = child->firstChild(); node; node = node->nextSibling()) {

* should be on the left of the space.

> Source/WebCore/dom/ContainerNode.cpp:160
> +    if ((newChild->isElementNode() || newChild->isTextNode()) && newParent->isElementNode()) {
> +        ASSERT(!newParent->isReadOnlyNode());
> +        ASSERT(!newParent->isDocumentTypeNode());
> +        ASSERT(isChildTypeAllowed(newParent, newChild));
> +        return 0;
> +    }

Where did this come from? In general, I feel like this patch needs more elaborative description on how things are changed (e.g. checkAcceptChild being merged into checkAddChild).

[Hajime Morrita]

Created attachment 176415 [details]
Patch

[Hajime Morrita]

Comment on attachment 176415 [details]
Patch

Oh, the patch doesn't address Ryosuke's comment. Will revise.

[Hajime Morrita]

Created attachment 176444 [details]
Patch

[Hajime Morrita]

Created attachment 176445 [details]
Patch

[Hajime Morrita]

(In reply to comment #11)
> (From update of attachment 176394 [details])
> Attachment 176394 [details] did not pass chromium-ews (chromium-xvfb):
> Output: http://queues.webkit.org/results/15029240
> 
> New failing tests:
> dom/xhtml/level3/core/nodereplacechild22.xhtml
> dom/xhtml/level3/core/nodereplacechild13.xhtml
> dom/xhtml/level3/core/nodereplacechild23.xhtml
> dom/xhtml/level3/core/documentgetdoctype01.xhtml
> dom/xhtml/level3/core/nodecomparedocumentposition02.xhtml

Turned out that moving Node::contains() and other cleanup broke these tests.
I went back original flow with smaller clean up.

Updated one also addresses Ryosuke's point.

[Ojan Vafai]

Comment on attachment 176445 [details]
Patch

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

> Source/WebCore/ChangeLog:15
> +        - Added a fast path in checkAcceptChild(), where we canassume that the parent is element

typo: canassume

> Source/WebCore/ChangeLog:17
> +          and just needs a circle prevention through Node::contains(). This is faster than current generic version.

nit: s/circle/cycle. circle is correct, but it's just a less common term for this.

> Source/WebCore/dom/ContainerNode.cpp:153
> +    if ((newChild->isElementNode() || newChild->isTextNode()) && newParent->isElementNode()) {

Maybe add a comment above this line that this is just a fast-path for the common case?

> Source/WebCore/dom/ContainerNode.cpp:157
> +        ASSERT(!oldChild || !newParent->isDocumentNode() || static_cast<Document*>(newParent)->canReplaceChild(newChild, oldChild));

I think the last two clauses here are not especially useful since the if-statement clearly doesn't go down this codepath if newParent is a Document.

> Source/WebCore/dom/ContainerNode.cpp:174
> +    } else {
> +        if (!isChildTypeAllowed(newParent, newChild))

Nit: you could make this an "} else if {"

> Source/WebCore/dom/ContainerNode.cpp:371
> -    checkReplaceChild(newChild.get(), oldChild, ec);
> -    if (ec)
> +    if (!checkReplaceChild(this, newChild.get(), oldChild, ec))

This would be a separate patch, but I'm noting it while I see it. We only need to do these checks again if we dispatched any events. We should just tracked whether any events were dispatched and only do these checks if that was the case (kind of like ChildNodesLazySnapshot).

Also, maybe I'm reading the code wrong, but I think there's a bug in insertBefore/appendChild for the cases where we dispatch a sync event (e.g. blur) during the removal in collectChildrenAndRemoveFromOldParent. We don't do the checks again to see that we can still insert the node.

[Hajime Morrita]

Created attachment 176595 [details]
Patch for landing

[Hajime Morrita]

Comment on attachment 176445 [details]
Patch

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

>> Source/WebCore/ChangeLog:15
>> +        - Added a fast path in checkAcceptChild(), where we canassume that the parent is element
> 
> typo: canassume

Fixed.

>> Source/WebCore/ChangeLog:17
>> +          and just needs a circle prevention through Node::contains(). This is faster than current generic version.
> 
> nit: s/circle/cycle. circle is correct, but it's just a less common term for this.

Well, this is just wrong. Fixed.

>> Source/WebCore/dom/ContainerNode.cpp:153
>> +    if ((newChild->isElementNode() || newChild->isTextNode()) && newParent->isElementNode()) {
> 
> Maybe add a comment above this line that this is just a fast-path for the common case?

Makes sense. Added a comment.

>> Source/WebCore/dom/ContainerNode.cpp:157
>> +        ASSERT(!oldChild || !newParent->isDocumentNode() || static_cast<Document*>(newParent)->canReplaceChild(newChild, oldChild));
> 
> I think the last two clauses here are not especially useful since the if-statement clearly doesn't go down this codepath if newParent is a Document.

Hmm. This statement might be just confusing. I'd remove this.

>> Source/WebCore/dom/ContainerNode.cpp:174
>> +        if (!isChildTypeAllowed(newParent, newChild))
> 
> Nit: you could make this an "} else if {"

Fixed.

>> Source/WebCore/dom/ContainerNode.cpp:371
>> +    if (!checkReplaceChild(this, newChild.get(), oldChild, ec))
> 
> This would be a separate patch, but I'm noting it while I see it. We only need to do these checks again if we dispatched any events. We should just tracked whether any events were dispatched and only do these checks if that was the case (kind of like ChildNodesLazySnapshot).
> 
> Also, maybe I'm reading the code wrong, but I think there's a bug in insertBefore/appendChild for the cases where we dispatch a sync event (e.g. blur) during the removal in collectChildrenAndRemoveFromOldParent. We don't do the checks again to see that we can still insert the node.

File bug 103571 for the speedup idea. I'm wondering if there are any umbrella bug for tracking DOM speedup ideas.
For possibly-missing checkAddChild(), I'll try to repro the issue.

[WebKit Review Bot]

Comment on attachment 176595 [details]
Patch for landing

Clearing flags on attachment: 176595

Committed r136076: <http://trac.webkit.org/changeset/136076>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Darin Adler]

Good changes. I like these!

[Hajime Morrita]

(In reply to comment #23)
> Good changes. I like these!
Thanks!

(In reply to comment #20)
> > Also, maybe I'm reading the code wrong, but I think there's a bug in insertBefore/appendChild for the cases where we dispatch a sync event (e.g. blur) during the removal in collectChildrenAndRemoveFromOldParent. We don't do the checks again to see that we can still insert the node.

I tried this but couldn't figure out any attack. Here is my attempt: http://jsfiddle.net/U5KJX/2/
It's hard to explain why this is OK, but you could take a look at http://wkcheck.in/124156 to see why 
replaceChild() needs that extra check, and why appendChild() doesn't (IMO) need one.

[Ojan Vafai]

> I'm wondering if there are any umbrella bug for tracking DOM speedup ideas.

Not that I know of. We could add a bugzilla keyword.

> For possibly-missing checkAddChild(), I'll try to repro the issue.

It took some work, but I found a testcase. Filed bug 103601.