Bug 80706 - Improve ContainerNode's collectNodes() performance
Summary: Improve ContainerNode's collectNodes() performance
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Stephen White
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2012-03-09 09:48 PST by Stephen White
Modified: 2012-03-18 22:44 PDT (History)
8 users (show)

See Also:


Attachments
Patch (1.29 KB, patch)
2012-03-09 10:22 PST, Stephen White
no flags Details | Formatted Diff | Diff
Patch (1.64 KB, patch)
2012-03-09 11:46 PST, Stephen White
no flags Details | Formatted Diff | Diff
Patch (1.58 KB, patch)
2012-03-09 12:54 PST, Stephen White
no flags Details | Formatted Diff | Diff
Patch (1.96 KB, patch)
2012-03-09 14:54 PST, Stephen White
no flags Details | Formatted Diff | Diff
Increases the stack allocated buffer size (1.29 KB, patch)
2012-03-13 17:36 PDT, Ryosuke Niwa
koivisto: review+
webkit.review.bot: commit-queue-
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Stephen White 2012-03-09 09:48:53 PST
This seems to be causing regressions in Chromium's dom_perf suite.
Comment 1 Stephen White 2012-03-09 10:22:14 PST
Created attachment 131056 [details]
Patch
Comment 2 Adam Barth 2012-03-09 10:23:31 PST
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.
Comment 3 Ryosuke Niwa 2012-03-09 10:43:19 PST
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
Comment 4 Stephen White 2012-03-09 10:58:31 PST
(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?
Comment 5 Ryosuke Niwa 2012-03-09 11:04:31 PST
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.
Comment 6 Stephen White 2012-03-09 11:46:01 PST
Created attachment 131065 [details]
Patch
Comment 7 Ryosuke Niwa 2012-03-09 11:56:16 PST
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.
Comment 8 Ryosuke Niwa 2012-03-09 12:18:21 PST
As I've privately told you, bumping up the initial capacity will probably buy us more performance than allocating the entire buffer up front.
Comment 9 Stephen White 2012-03-09 12:54:32 PST
Created attachment 131081 [details]
Patch
Comment 10 Eric Seidel (no email) 2012-03-09 13:05:44 PST
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.
Comment 11 Ryosuke Niwa 2012-03-09 13:18:38 PST
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.
Comment 12 Eric Seidel (no email) 2012-03-09 13:22:37 PST
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.
Comment 13 Adam Barth 2012-03-09 14:50:10 PST
Comment on attachment 131081 [details]
Patch

Please update the ChangeLog before landing.
Comment 14 Stephen White 2012-03-09 14:54:51 PST
Created attachment 131118 [details]
Patch
Comment 15 Stephen White 2012-03-09 14:55:47 PST
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.
Comment 16 Ryosuke Niwa 2012-03-09 14:55:54 PST
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.
Comment 17 Stephen White 2012-03-09 18:23:30 PST
Committed r110358: <http://trac.webkit.org/changeset/110358>
Comment 18 Stephen White 2012-03-10 08:14:11 PST
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).
Comment 19 Stephen White 2012-03-10 09:19:04 PST
Rolled out in http://trac.webkit.org/changeset/110378.
Comment 20 Ryosuke Niwa 2012-03-13 17:28:18 PDT
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.
Comment 21 Ryosuke Niwa 2012-03-13 17:36:26 PDT
Created attachment 131762 [details]
Increases the stack allocated buffer size
Comment 22 Stephen White 2012-03-13 18:05:52 PDT
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.
Comment 23 Ryosuke Niwa 2012-03-13 18:16:03 PDT
(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.
Comment 24 Stephen White 2012-03-14 03:35:39 PDT
(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.
Comment 25 Ryosuke Niwa 2012-03-14 09:29:54 PDT
(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.
Comment 26 Stephen White 2012-03-14 10:48:32 PDT
(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."
Comment 27 Ryosuke Niwa 2012-03-14 11:45:04 PDT
(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.
Comment 28 Antti Koivisto 2012-03-14 11:51:28 PDT
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.
Comment 29 Stephen White 2012-03-14 11:56:49 PDT
(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.
Comment 30 Antti Koivisto 2012-03-14 11:57:51 PDT
Also the patch is sufficiently self document as-is.
Comment 31 Andreas Kling 2012-03-14 13:18:55 PDT
(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.
Comment 32 Ryosuke Niwa 2012-03-14 17:11:20 PDT
Committed in http://trac.webkit.org/changeset/110797.
Comment 33 Ryosuke Niwa 2012-03-14 17:11:40 PDT
Oops, wrong bug :(
Comment 34 WebKit Review Bot 2012-03-14 17:18:50 PDT
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
Comment 35 Hajime Morrita 2012-03-14 20:34:00 PDT
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.
Comment 36 Hajime Morrita 2012-03-14 20:35:03 PDT
> 
> 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.
Comment 37 Ryosuke Niwa 2012-03-14 20:35:27 PDT
(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.
Comment 38 Ryosuke Niwa 2012-03-14 20:50:50 PDT
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.
Comment 39 Ryosuke Niwa 2012-03-14 20:51:37 PDT
I mean in http://trac.webkit.org/changeset/110817.
Comment 40 Ryosuke Niwa 2012-03-14 21:00:38 PDT
http://crbug.com/117020