Bug 85844 - Inline Node::traverseNextNode
Summary: Inline Node::traverseNextNode
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords: InRadar
Depends on: 85898 86159
Blocks:
  Show dependency treegraph
 
Reported: 2012-05-07 16:42 PDT by Antti Koivisto
Modified: 2012-05-12 09:54 PDT (History)
7 users (show)

See Also:


Attachments
patch (5.99 KB, patch)
2012-05-07 16:50 PDT, Antti Koivisto
no flags Details | Formatted Diff | Diff
patch2 (6.07 KB, patch)
2012-05-07 17:25 PDT, Antti Koivisto
rniwa: review+
webkit.review.bot: commit-queue-
Details | Formatted Diff | Diff
another version with non-inlined ancestor sibling search (5.45 KB, patch)
2012-05-10 04:02 PDT, Antti Koivisto
buildbot: commit-queue-
Details | Formatted Diff | Diff
fix exports (5.98 KB, patch)
2012-05-10 10:10 PDT, Antti Koivisto
rniwa: review+
buildbot: commit-queue-
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Antti Koivisto 2012-05-07 16:42:10 PDT
We spend quite of bit time here, including the function entry/exit. We should also generate different code for stayWithin and unscoped cases.
Comment 1 Antti Koivisto 2012-05-07 16:50:38 PDT
Created attachment 140621 [details]
patch
Comment 2 Ryosuke Niwa 2012-05-07 16:54:24 PDT
Comment on attachment 140621 [details]
patch

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

> Source/WebCore/dom/Node.h:861
> +    const Node* n = this;

Please spell out node.

> Source/WebCore/dom/Node.h:869
> +inline Node* Node::traverseNextNode(const Node* stayWithin) const

Should we use template to share the code?

> Source/WebCore/dom/Node.h:877
> +    const Node* n = this;

Ditto about one-letter variable name.

> Source/WebCore/dom/Node.h:878
> +    while (n && !n->nextSibling() && (!stayWithin || n->parentNodeAsNode() != stayWithin))

It appears to me that we should call traverseNextNode() when stayWithin is 0.

> Source/WebCore/dom/Node.h:889
> +    const Node* n = this;

Ditto about one-letter variable name.

> Source/WebCore/dom/Node.h:903
> +    const Node* n = this;

Ditto about one-letter variable name.

> Source/WebCore/dom/Node.h:904
> +    while (n && !n->nextSibling() && (!stayWithin || n->parentNodeAsNode() != stayWithin))

Ditto about calling traverseNextSibling() instead.
Comment 3 Ryosuke Niwa 2012-05-07 16:54:51 PDT
I'm sure Darin & Eric have something to say about this.
Comment 4 Eric Seidel (no email) 2012-05-07 16:57:12 PDT
Comment on attachment 140621 [details]
patch

Seems reasonable.  Curious what benchmark hit this?
Comment 5 Antti Koivisto 2012-05-07 17:03:50 PDT
(In reply to comment #2)

> > Source/WebCore/dom/Node.h:869
> > +inline Node* Node::traverseNextNode(const Node* stayWithin) const
> 
> Should we use template to share the code?

I wrote a template version and it was uglier and more confusing. As I mention in the changelog the function is simple.

> > Source/WebCore/dom/Node.h:878
> > +    while (n && !n->nextSibling() && (!stayWithin || n->parentNodeAsNode() != stayWithin))
> 
> It appears to me that we should call traverseNextNode() when stayWithin is 0.

Yeah but that is an interface change and better done separately. We don't know what relies on ability to pass null. We should ASSERT(stayWithin).
Comment 6 Ryosuke Niwa 2012-05-07 17:06:57 PDT
(In reply to comment #5)
> (In reply to comment #2)
> 
> > > Source/WebCore/dom/Node.h:869
> > > +inline Node* Node::traverseNextNode(const Node* stayWithin) const
> > 
> > Should we use template to share the code?
> 
> I wrote a template version and it was uglier and more confusing. As I mention in the changelog the function is simple.

Okay.

> > > Source/WebCore/dom/Node.h:878
> > > +    while (n && !n->nextSibling() && (!stayWithin || n->parentNodeAsNode() != stayWithin))
> > 
> > It appears to me that we should call traverseNextNode() when stayWithin is 0.
> 
> Yeah but that is an interface change and better done separately. We don't know what relies on ability to pass null. We should ASSERT(stayWithin).

What I meant is that you could just call traverseNextNode() in that case. Oh well, I guess compilers are smart enough to move the condition out of the loop?
Comment 7 Antti Koivisto 2012-05-07 17:10:59 PDT
(In reply to comment #6)
> > Yeah but that is an interface change and better done separately. We don't know what relies on ability to pass null. We should ASSERT(stayWithin).
> 
> What I meant is that you could just call traverseNextNode() in that case. Oh well, I guess compilers are smart enough to move the condition out of the loop?

That still adds an extra branch for no reason. It should really be the callers responsibility to use the right variant as usually they just need one or the other.
Comment 8 Ryosuke Niwa 2012-05-07 17:12:30 PDT
(In reply to comment #7)
> (In reply to comment #6)
> > What I meant is that you could just call traverseNextNode() in that case. Oh well, I guess compilers are smart enough to move the condition out of the loop?
> 
> That still adds an extra branch for no reason. It should really be the callers responsibility to use the right variant as usually they just need one or the other.

Fair enough. I bet editing code is the one that calls this function with null stayWithin.
Comment 9 Antti Koivisto 2012-05-07 17:16:03 PDT
(In reply to comment #4)
> (From update of attachment 140621 [details])
> Seems reasonable.  Curious what benchmark hit this?

Nothing really. If you sample regular page loading you can see this function showing up around ~1%.
Comment 10 Antti Koivisto 2012-05-07 17:16:27 PDT
<rdar://problem/10942765>
Comment 11 Antti Koivisto 2012-05-07 17:25:41 PDT
Created attachment 140632 [details]
patch2

n -> node
Comment 12 Ryosuke Niwa 2012-05-07 17:27:21 PDT
Comment on attachment 140632 [details]
patch2

Very reasonable patch.
Comment 13 WebKit Review Bot 2012-05-07 17:28:47 PDT
Attachment 140632 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1
Source/WebCore/dom/Node.h:894:  More than one command on the same line  [whitespace/newline] [4]
Total errors found: 1 in 2 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 14 Darin Adler 2012-05-07 17:29:14 PDT
Comment on attachment 140632 [details]
patch2

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

> Source/WebCore/dom/Node.h:853
> +inline Node* Node::parentNodeAsNode() const
> +{
> +    // Avoid circular dependency with ContainerNode.
> +    return reinterpret_cast<Node*>(parentNode());
> +}

Normally the way we handle stuff like this is to put the functions into ContainerNode.h, instead of a trick like this one.

The downside then, is that anyone calling these functions has to include ContainerNode.h, but they probably do anyway.
Comment 15 Antti Koivisto 2012-05-07 17:58:02 PDT
(In reply to comment #14)
> Normally the way we handle stuff like this is to put the functions into ContainerNode.h, instead of a trick like this one.
> 
> The downside then, is that anyone calling these functions has to include ContainerNode.h, but they probably do anyway.

Generally I would prefer keeping the functions in a predictable place but I see ContainerNode.h is already full of Node function. I'll move them there.
Comment 16 WebKit Review Bot 2012-05-07 19:28:38 PDT
Comment on attachment 140632 [details]
patch2

Attachment 140632 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/12652231
Comment 17 Antti Koivisto 2012-05-08 01:31:04 PDT
http://trac.webkit.org/changeset/116402
Comment 18 WebKit Review Bot 2012-05-08 11:01:02 PDT
Re-opened since this is blocked by 85898
Comment 19 Antti Koivisto 2012-05-08 11:56:51 PDT
Seems like the inlining here is overly aggressive. I'll try what bots think of a version that just inlines the initial firstChild/nextSibling checks.
Comment 20 Darin Adler 2012-05-08 12:47:58 PDT
Just for the record, all the time I saw in this function in profiles was in the implementation of HTMLCollection and the related DOM classes.
Comment 21 Ryosuke Niwa 2012-05-08 12:51:28 PDT
(In reply to comment #20)
> Just for the record, all the time I saw in this function in profiles was in the implementation of HTMLCollection and the related DOM classes.

HTMLCollection checks DOM tree version to invalidate cache so making any DOM mutation inside a loop to iterate over a HTMLCollection will introduce a O(n^2) iteration where n is the number of nodes in the subtree. We should probably move HTMLCollection to the model DynamicSubtreNodeList uses.
Comment 22 Darin Adler 2012-05-08 12:53:18 PDT
I still think the right amount of inlining is a good idea for this function. Inlining the whole thing is probably too much.

I also think we can override this in ContainerNode to do a version that’s even tighter for cases where we are starting with an Element* rather than a Node*. The firstChild function is smaller on an Element* than on a Node*.
Comment 23 Darin Adler 2012-05-08 13:23:21 PDT
I think I was remembering wrong. I think the hot cases were in one of the classes derived from DynamicSubtreeNodeList.
Comment 24 Ryosuke Niwa 2012-05-08 13:32:57 PDT
(In reply to comment #23)
> I think I was remembering wrong. I think the hot cases were in one of the classes derived from DynamicSubtreeNodeList.

I see. Do you happen to know tests / websites you used to obtain this result?
Comment 25 Darin Adler 2012-05-08 13:53:38 PDT
I was looking at a profile of loading the front page of nytimes.com.
Comment 26 Antti Koivisto 2012-05-10 04:02:19 PDT
Created attachment 141135 [details]
another version with non-inlined ancestor sibling search
Comment 27 Build Bot 2012-05-10 04:28:27 PDT
Comment on attachment 141135 [details]
another version with non-inlined ancestor sibling search

Attachment 141135 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/12654902
Comment 28 Antti Koivisto 2012-05-10 10:10:24 PDT
Created attachment 141191 [details]
fix exports
Comment 29 Ryosuke Niwa 2012-05-10 10:20:45 PDT
Comment on attachment 141191 [details]
fix exports

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

> Source/WebCore/dom/ContainerNode.h:236
> +    if (firstChild())
> +        return firstChild();
> +    if (nextSibling())
> +        return nextSibling();

Should we create a local variables for firstChid, nextSibling, etc...?
Or maybe compilers are smart enough to figure that out by themselves?
Comment 30 Antti Koivisto 2012-05-10 10:42:58 PDT
(In reply to comment #29)
> Should we create a local variables for firstChid, nextSibling, etc...?
> Or maybe compilers are smart enough to figure that out by themselves?

I think compiler knows best here.
Comment 31 Build Bot 2012-05-10 11:41:39 PDT
Comment on attachment 141191 [details]
fix exports

Attachment 141191 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/12672007
Comment 32 Build Bot 2012-05-10 11:43:50 PDT
Comment on attachment 141191 [details]
fix exports

Attachment 141191 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/12653924
Comment 33 Antti Koivisto 2012-05-10 12:57:03 PDT
Lets see what bots think about this one.

http://trac.webkit.org/changeset/116677
Comment 34 WebKit Review Bot 2012-05-10 16:49:02 PDT
Re-opened since this is blocked by 86159
Comment 35 Darin Adler 2012-05-10 17:35:33 PDT
The fix for the Chromium build error mentioned in bug 86159 is to add an include of ContainerNode.h to the Chromium source file that has RetainedDOMInfo::GetElementCount() in it.
Comment 36 Jian Li 2012-05-10 17:57:01 PDT
(In reply to comment #35)
> The fix for the Chromium build error mentioned in bug 86159 is to add an include of ContainerNode.h to the Chromium source file that has RetainedDOMInfo::GetElementCount() in it.

This seems to be the right fix for chromium. But it seems that we also have quite a few other places that call Node::traverseNextNode but might not include ContainerNode.h. This could be the reason mac-ews also showed the similar error.

Can the author add the comment to those methods in Node.h, saying that ContainerNode.h should be included to access these inline methods?
Comment 37 Darin Adler 2012-05-10 18:29:46 PDT
(In reply to comment #36)
> Can the author add the comment to those methods in Node.h, saying that ContainerNode.h should be included to access these inline methods?

I’m don’t think that kind of comment would be helpful. We have many other functions in Node with that requirement and this really isn’t an ongoing problem.

This kind of build breakage happens at the time we add the requirement, for existing code developed before it was required, and so the comment is not relevant.
Comment 38 Antti Koivisto 2012-05-11 02:06:19 PDT
I'm starting to feel the approach involving reinterpret_cast<Node*>(parentNode()) was superior.
Comment 39 Antti Koivisto 2012-05-11 02:28:50 PDT
Relanded with Chromium build fix.

http://trac.webkit.org/changeset/116742
Comment 40 Antti Koivisto 2012-05-11 08:48:25 PDT
(In reply to comment #22)
> I also think we can override this in ContainerNode to do a version that’s even tighter for cases where we are starting with an Element* rather than a Node*. The firstChild function is smaller on an Element* than on a Node*.

Most of the clients actually want to traverse Elements (or StyledElements) not Nodes. We might want to have traverseNextElement/traverseNextElementSibling. If we tracked whether elements have any Element children (with a bit) we could avoid looking into Text nodes at all.