Bug 103372 - checkAcceptChild() needs fewer virtual calls
Summary: checkAcceptChild() needs fewer virtual calls
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Hajime Morrita
URL:
Keywords:
Depends on:
Blocks: 103370
  Show dependency treegraph
 
Reported: 2012-11-27 00:18 PST by Hajime Morrita
Modified: 2012-11-28 21:36 PST (History)
8 users (show)

See Also:


Attachments
Patch (11.47 KB, patch)
2012-11-27 03:51 PST, Hajime Morrita
no flags Details | Formatted Diff | Diff
Updated to ToT (11.39 KB, patch)
2012-11-27 03:56 PST, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch (10.80 KB, patch)
2012-11-27 17:44 PST, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch (10.51 KB, patch)
2012-11-27 21:29 PST, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch (10.81 KB, patch)
2012-11-28 00:04 PST, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch (12.36 KB, patch)
2012-11-28 03:29 PST, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch (12.29 KB, patch)
2012-11-28 03:30 PST, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch for landing (12.07 KB, patch)
2012-11-28 16:14 PST, Hajime Morrita
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Hajime Morrita 2012-11-27 00:18:13 PST
There are a few virtual method calls which can be eliminated.
It's worth eliminating since the function is hot in DOM mutations.
Comment 1 Hajime Morrita 2012-11-27 03:51:06 PST
Created attachment 176224 [details]
Patch
Comment 2 Hajime Morrita 2012-11-27 03:56:25 PST
Created attachment 176225 [details]
Updated to ToT
Comment 3 Ojan Vafai 2012-11-27 10:01:37 PST
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.
Comment 4 Ryosuke Niwa 2012-11-27 10:36:48 PST
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.
Comment 5 Hajime Morrita 2012-11-27 17:44:02 PST
Created attachment 176375 [details]
Patch
Comment 6 Hajime Morrita 2012-11-27 17:44:27 PST
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.
Comment 7 Build Bot 2012-11-27 21:18:22 PST
Comment on attachment 176375 [details]
Patch

Attachment 176375 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15023289
Comment 8 Hajime Morrita 2012-11-27 21:29:59 PST
Created attachment 176394 [details]
Patch
Comment 9 Ojan Vafai 2012-11-27 22:49:52 PST
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. :)
Comment 10 Ojan Vafai 2012-11-27 22:57:03 PST
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.
Comment 11 WebKit Review Bot 2012-11-27 23:28:10 PST
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
Comment 12 Ryosuke Niwa 2012-11-27 23:32:59 PST
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).
Comment 13 Hajime Morrita 2012-11-28 00:04:04 PST
Created attachment 176415 [details]
Patch
Comment 14 Hajime Morrita 2012-11-28 00:06:01 PST
Comment on attachment 176415 [details]
Patch

Oh, the patch doesn't address Ryosuke's comment. Will revise.
Comment 15 Hajime Morrita 2012-11-28 03:29:40 PST
Created attachment 176444 [details]
Patch
Comment 16 Hajime Morrita 2012-11-28 03:30:31 PST
Created attachment 176445 [details]
Patch
Comment 17 Hajime Morrita 2012-11-28 03:32:52 PST
(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.
Comment 18 Ojan Vafai 2012-11-28 10:13:37 PST
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.
Comment 19 Hajime Morrita 2012-11-28 16:14:47 PST
Created attachment 176595 [details]
Patch for landing
Comment 20 Hajime Morrita 2012-11-28 16:18:34 PST
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.
Comment 21 WebKit Review Bot 2012-11-28 16:52:35 PST
Comment on attachment 176595 [details]
Patch for landing

Clearing flags on attachment: 176595

Committed r136076: <http://trac.webkit.org/changeset/136076>
Comment 22 WebKit Review Bot 2012-11-28 16:52:40 PST
All reviewed patches have been landed.  Closing bug.
Comment 23 Darin Adler 2012-11-28 17:20:29 PST
Good changes. I like these!
Comment 24 Hajime Morrita 2012-11-28 17:37:40 PST
(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.
Comment 25 Ojan Vafai 2012-11-28 21:36:18 PST
> 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.