Bug 80706 – Improve ContainerNode's collectNodes() performance

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

[Stephen White]

This seems to be causing regressions in Chromium's dom_perf suite.

[Stephen White]

Created attachment 131056 [details]
Patch

[Adam Barth]

Comment on attachment 131056 [details]
Patch

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

> Source/WebCore/dom/ContainerNode.cpp:68
> +    size_t newSize = nodes.size();
> +    for (Node* child = node->firstChild(); child; child = child->nextSibling())
> +        newSize++;

There's already a function that does.  We might need to change the type of |node| to ContainerNode to see it.

[Ryosuke Niwa]

Comment on attachment 131056 [details]
Patch

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

>> Source/WebCore/dom/ContainerNode.cpp:68
>> +        newSize++;
> 
> There's already a function that does.  We might need to change the type of |node| to ContainerNode to see it.

childNodeCount

[Stephen White]

(In reply to comment #2)
> (From update of attachment 131056 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=131056&action=review
> 
> > Source/WebCore/dom/ContainerNode.cpp:68
> > +    size_t newSize = nodes.size();
> > +    for (Node* child = node->firstChild(); child; child = child->nextSibling())
> > +        newSize++;
> 
> There's already a function that does.  We might need to change the type of |node| to ContainerNode to see it.

Unfortunately, that requires changing collectTargetNodes(), and a number of call sites pass in a plain ol' Node to collectTargetNodes() (which can't be blindly downcast, I presume).

I could move childNodeCount() up to Node, but considering this is just a speculative fix for which I'd like to get some data off the perf bots, maybe we could try it as-is?

[Ryosuke Niwa]

Comment on attachment 131056 [details]
Patch

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

>>>> Source/WebCore/dom/ContainerNode.cpp:68
>>>> +        newSize++;
>>> 
>>> There's already a function that does.  We might need to change the type of |node| to ContainerNode to see it.
>> 
>> childNodeCount
> 
> Unfortunately, that requires changing collectTargetNodes(), and a number of call sites pass in a plain ol' Node to collectTargetNodes() (which can't be blindly downcast, I presume).
> 
> I could move childNodeCount() up to Node, but considering this is just a speculative fix for which I'd like to get some data off the perf bots, maybe we could try it as-is?

All nodes that have children are ContainerNodes so caller can either downcast the pointer or never call this function depending on the type of the node.

[Stephen White]

Created attachment 131065 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 131065 [details]
Patch

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

> Source/WebCore/dom/ContainerNode.cpp:78
> -    collectNodes(node, nodes);
> +    if (!node->isContainerNode())
> +        return;

node is a DocumentFragment (which inherits from ContainerNode) at this point so there's no need to call isContainerNode.

[Ryosuke Niwa]

As I've privately told you, bumping up the initial capacity will probably buy us more performance than allocating the entire buffer up front.

[Stephen White]

Created attachment 131081 [details]
Patch

[Eric Seidel (no email)]

Comment on attachment 131081 [details]
Patch

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

> Source/WebCore/ChangeLog:9
> +        Covered by existing tests.

You need to explain what tests this improves performance on.

> Source/WebCore/dom/ContainerNode.cpp:66
> +    nodes.reserveCapacity(nodes.size() + node->childNodeCount());

I believe childNodeCount() walks all the node pointers... but I could imagine avoiding multiple mallocs would be faster.

> Source/WebCore/dom/ContainerNode.cpp:77
> -    collectNodes(node, nodes);
> +    collectNodes(static_cast<ContainerNode*>(node), nodes);

This doesn't seem safe.

[Ryosuke Niwa]

Comment on attachment 131081 [details]
Patch

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

>> Source/WebCore/dom/ContainerNode.cpp:77
>> +    collectNodes(static_cast<ContainerNode*>(node), nodes);
> 
> This doesn't seem safe.

This is okay because node is a DocumentFragment at this point. See line 73 :)
But it might be better to cast it to DocumentFragment for clarity.

[Eric Seidel (no email)]

Comment on attachment 131081 [details]
Patch

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

>>> Source/WebCore/dom/ContainerNode.cpp:77
>>> +    collectNodes(static_cast<ContainerNode*>(node), nodes);
>> 
>> This doesn't seem safe.
> 
> This is okay because node is a DocumentFragment at this point. See line 73 :)
> But it might be better to cast it to DocumentFragment for clarity.

Ah yes, I had read the above as the DocumentFramgment-only special case, missed the !=.  You're right though, casing to DocumentFragment would probably be more clear.

[Adam Barth]

Comment on attachment 131081 [details]
Patch

Please update the ChangeLog before landing.

[Stephen White]

Created attachment 131118 [details]
Patch

[Stephen White]

Comment on attachment 131081 [details]
Patch

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

>> Source/WebCore/ChangeLog:9
>> +        Covered by existing tests.
> 
> You need to explain what tests this improves performance on.

Done.  Note that this is a speculative fix:  I'm going to land it and evalute it based on the listed tests.   If there's no improvement, I'll revert.

>>>> Source/WebCore/dom/ContainerNode.cpp:77
>>>> +    collectNodes(static_cast<ContainerNode*>(node), nodes);
>>> 
>>> This doesn't seem safe.
>> 
>> This is okay because node is a DocumentFragment at this point. See line 73 :)
>> But it might be better to cast it to DocumentFragment for clarity.
> 
> Ah yes, I had read the above as the DocumentFramgment-only special case, missed the !=.  You're right though, casing to DocumentFragment would probably be more clear.

OK, done.

[Ryosuke Niwa]

Comment on attachment 131118 [details]
Patch

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

> Source/WebCore/ChangeLog:9
> +        Covered by existing tests.  Performance will be evaluated based on

Nit: we use one space after period.

[Stephen White]

Committed r110358: <http://trac.webkit.org/changeset/110358>

[Stephen White]

Result:  the tests of interest showed no change (positive or negative) after this CL, so I'm going to revert it.

e.g., http://build.chromium.org/f/chromium/perf/linux-release-webkit-latest/bloat-http/report.html?history=150&rev=-1

(change corresponds to Chrome r125985 on that chart).

[Stephen White]

Rolled out in http://trac.webkit.org/changeset/110378.

[Ryosuke Niwa]

I've looked into how many nodes are typically inserted by the following diff:

ndex: Source/WebCore/dom/ContainerNode.cpp
===================================================================
--- Source/WebCore/dom/ContainerNode.cpp	(revision 110541)
+++ Source/WebCore/dom/ContainerNode.cpp	(working copy)
@@ -65,6 +65,7 @@
 {
     for (Node* child = node->firstChild(); child; child = child->nextSibling())
         nodes.append(child);
+    fprintf(stderr, "[%ld]\n", nodes.size());
 }

and browsed on popular websites like facebook, twitter, gmail, etc...

sample size: 188272

Statistics ignoring entries with 0s and 1s:
mean: 4.41114811377
std: 3.31585908742
min: 2
max: 151

nodes.size() > 5: 9908 5.26%
nodes.size() > 10: 2471 1.31%
nodes.size() > 11: 915 0.49%
nodes.size() > 12: 863 0.46%
nodes.size() > 13: 834 0.44%
nodes.size() > 15: 154 0.082%

11 is probably a good number to use.

[Ryosuke Niwa]

Created attachment 131762 [details]
Increases the stack allocated buffer size

[Stephen White]

Comment on attachment 131762 [details]
Increases the stack allocated buffer size

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

> Source/WebCore/dom/ContainerNode.cpp:58
> +typedef Vector<RefPtr<Node>, 11> NodeVector;

You should probably add a comment explaining how you arrived at this number.

[Ryosuke Niwa]

(In reply to comment #22)
> (From update of attachment 131762 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=131762&action=review
> 
> > Source/WebCore/dom/ContainerNode.cpp:58
> > +typedef Vector<RefPtr<Node>, 11> NodeVector;
> 
> You should probably add a comment explaining how you arrived at this number.

We don't normally add that kind of comment in the code. Instead, we tend to document those things in the change log.

[Stephen White]

(In reply to comment #23)
> (In reply to comment #22)
> > (From update of attachment 131762 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=131762&action=review
> > 
> > > Source/WebCore/dom/ContainerNode.cpp:58
> > > +typedef Vector<RefPtr<Node>, 11> NodeVector;
> > 
> > You should probably add a comment explaining how you arrived at this number.
> 
> We don't normally add that kind of comment in the code. Instead, we tend to document those things in the change log.

My understanding of WebKit's policy on comments is that code should be self-documenting, through the use of descriptive variable names and the like.  A magic value in the code is not self-documenting.  The next developer who discovers this value in the code would have to root around in the VCS to find out the change which added it, and then look up the ChangeLog to find the reasoning.

[Ryosuke Niwa]

(In reply to comment #24)
> My understanding of WebKit's policy on comments is that code should be self-documenting, through the use of descriptive variable names and the like.  A magic value in the code is not self-documenting.  The next developer who discovers this value in the code would have to root around in the VCS to find out the change which added it, and then look up the ChangeLog to find the reasoning.

e.g.
http://trac.webkit.org/browser/trunk/Source/WebCore/css/CSSStyleSelector.cpp#L1143

As much as I understand where you're coming from, WebKit has a very different policy and culture from Google/Chromium. Please respect that.

[Stephen White]

(In reply to comment #25)
> (In reply to comment #24)
> > My understanding of WebKit's policy on comments is that code should be self-documenting, through the use of descriptive variable names and the like.  A magic value in the code is not self-documenting.  The next developer who discovers this value in the code would have to root around in the VCS to find out the change which added it, and then look up the ChangeLog to find the reasoning.
> 
> e.g.
> http://trac.webkit.org/browser/trunk/Source/WebCore/css/CSSStyleSelector.cpp#L1143

static const unsigned cStyleSearchThreshold = 10;  ?

This seems to be an example of a descriptive variable name (or at least, an attempt).  If you'd do that in this patch, I think it would be an improvement, although I still think an explanation of how the value was derived wouldn't be out of place.

> As much as I understand where you're coming from, WebKit has a very different policy and culture from Google/Chromium. Please respect that.

That's exactly what I'm attempting to do (which is tricky, since this is not actually addressed in the coding guidelines).  Here's a quote from Darin Adler which I think is relevant to this case:

"In general my preference is to have comments that say things that the code does not. Many header comments I have seen repeat things already said by the names and signatures of functions. Comments that answer questions such as "why" and that are brief would make a good addition, even to a header file."

[Ryosuke Niwa]

(In reply to comment #26)
> (In reply to comment #25)
> > (In reply to comment #24)
> > > My understanding of WebKit's policy on comments is that code should be self-documenting, through the use of descriptive variable names and the like.  A magic value in the code is not self-documenting.  The next developer who discovers this value in the code would have to root around in the VCS to find out the change which added it, and then look up the ChangeLog to find the reasoning.
> > 
> > e.g.
> > http://trac.webkit.org/browser/trunk/Source/WebCore/css/CSSStyleSelector.cpp#L1143
> 
> static const unsigned cStyleSearchThreshold = 10;  ?
> 
> This seems to be an example of a descriptive variable name (or at least, an attempt).  If you'd do that in this patch, I think it would be an improvement, although I still think an explanation of how the value was derived wouldn't be out of place.

In this case, a descriptive variable name helps because the semantics isn't clear from just seeing the value 10. However, in my patch, the semantics of 11 is vacuously clear; it's the initial size of the stack allocated buffer. Anyone who can read the code that uses Vector understands this instantly.

[Antti Koivisto]

Comment on attachment 131762 [details]
Increases the stack allocated buffer size

r=me. You could just make it even bigger. Looks like this type is just a temporary and the stack allocated size is essentially free.

[Stephen White]

(In reply to comment #27)
> (In reply to comment #26)
> > (In reply to comment #25)
> > > (In reply to comment #24)
> > > > My understanding of WebKit's policy on comments is that code should be self-documenting, through the use of descriptive variable names and the like.  A magic value in the code is not self-documenting.  The next developer who discovers this value in the code would have to root around in the VCS to find out the change which added it, and then look up the ChangeLog to find the reasoning.
> > > 
> > > e.g.
> > > http://trac.webkit.org/browser/trunk/Source/WebCore/css/CSSStyleSelector.cpp#L1143
> > 
> > static const unsigned cStyleSearchThreshold = 10;  ?
> > 
> > This seems to be an example of a descriptive variable name (or at least, an attempt).  If you'd do that in this patch, I think it would be an improvement, although I still think an explanation of how the value was derived wouldn't be out of place.
> 
> In this case, a descriptive variable name helps because the semantics isn't clear from just seeing the value 10. However, in my patch, the semantics of 11 is vacuously clear; it's the initial size of the stack allocated buffer. Anyone who can read the code that uses Vector understands this instantly.

Again, you're missing the point.  They'll understand the "what" but not the "why".

If it's still unclear to you why code peppered with inexplicable literals is not maintainable, I'll just leave someone else to r+ this patch.

[Antti Koivisto]

Also the patch is sufficiently self document as-is.

[Andreas Kling]

(In reply to comment #30)
> Also the patch is sufficiently self document as-is.

Agreed. I'd probably go with inlineCapacity=16 myself to get a more "rounded" number. Shouldn't matter if these are never used as member variables.

LGTM regardless.

[Ryosuke Niwa]

Committed in http://trac.webkit.org/changeset/110797.

[Ryosuke Niwa]

Oops, wrong bug :(

[WebKit Review Bot]

Comment on attachment 131762 [details]
Increases the stack allocated buffer size

Rejecting attachment 131762 [details] from commit-queue.

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

Last 500 characters of output:
ti Koiv..." exit_code: 1 cwd: /mnt/git/webkit-commit-queue/

Parsed 2 diffs from patch file(s).
patching file Source/WebCore/ChangeLog
Hunk #1 succeeded at 1 with fuzz 3.
patching file Source/WebCore/dom/ContainerNode.cpp
Hunk #1 FAILED at 55.
1 out of 1 hunk FAILED -- saving rejects to file Source/WebCore/dom/ContainerNode.cpp.rej

Failed to run "[u'/mnt/git/webkit-commit-queue/Tools/Scripts/svn-apply', u'--force', u'--reviewer', u'Antti Koiv..." exit_code: 1 cwd: /mnt/git/webkit-commit-queue/

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

[Hajime Morrita]

Comment on attachment 131762 [details]
Increases the stack allocated buffer size

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

>>>> Source/WebCore/dom/ContainerNode.cpp:58
>>>> +typedef Vector<RefPtr<Node>, 11> NodeVector;
>>> 
>>> You should probably add a comment explaining how you arrived at this number.
>> 
>> We don't normally add that kind of comment in the code. Instead, we tend to document those things in the change log.
> 
> My understanding of WebKit's policy on comments is that code should be self-documenting, through the use of descriptive variable names and the like.  A magic value in the code is not self-documenting.  The next developer who discovers this value in the code would have to root around in the VCS to find out the change which added it, and then look up the ChangeLog to find the reasoning.

Yeah, I think static const int ChildCountMoslyCovered = 11 will be fine  for example.
The point which should be emphasized  here is that the number is nothing absolute and more empirical.

[Hajime Morrita]

> 
> Yeah, I think static const int ChildCountMoslyCovered = 11 will be fine  for example.
> The point which should be emphasized  here is that the number is nothing absolute and more empirical.
>
Oops the party looks over before I join.

[Ryosuke Niwa]

(In reply to comment #35)
> Yeah, I think static const int ChildCountMoslyCovered = 11 will be fine  for example.
> The point which should be emphasized  here is that the number is nothing absolute and more empirical.

We normally document these things in the change log, not in the actual code base.

[Ryosuke Niwa]

Apparently this patch was committed in http://trac.webkit.org/changeset/110797 but mangled with my patch for https://bugs.webkit.org/show_bug.cgi?id=80900.

Fixed the change log in http://trac.webkit.org/changeset/110797.

[Ryosuke Niwa]

I mean in http://trac.webkit.org/changeset/110817.

[Ryosuke Niwa]

http://crbug.com/117020