Get rid of inefficient uses of childNodeCount()

Get rid of inefficient uses of childNodeCount()

Get rid of inefficient uses of childNodeCount() as this method can be costly.
Its implementation needs to traverse the node's direct children in the DOM tree
in order to count them. A lot of callers wrongly assume calling
childNodeCount() is cheap.

In a lot of cases, the callers simply want to know if the node has any children
or it is has exactly one child. hasChildNodes() / hasOneChild() methods provide
the same information much more efficiently.

In some cases, we already know the node is a ContainerNode but call the
Node::childNodeCount() method instead of ContainerNode::childNodeCount() which
bypasses the isContainerNode() check.

Finally, the caller sometimes wants to traverse all the direct children and
uses childNodeCount() / childNode(index) to do so. This causes the children to
be traversed twice (even more when childNodeCount() is used as loop condition
and not cached before the loop). In this case, it is best to use the traversal
API (NodeTraversal / ElementTraversal).

R=adamk, eseidel

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=167444

[Inactive, 2014-02-19 04:13:32]

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Containe...
File Source/core/dom/ContainerNode.cpp (left):

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Containe...
Source/core/dom/ContainerNode.cpp:540:
removedChildren.reserveInitialCapacity(childNodeCount());
I don't think this one is worth it as we end up traversing the children twice
instead of once for a likely small win on Vector::append().

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Range.cpp
File Source/core/dom/Range.cpp (right):

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Range.cp...
Source/core/dom/Range.cpp:661: return toContainerNode(node)->childNodeCount();
Those are all ContainerNodes so we can cast and bypass an isContainerNode()
check at run time.

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Range.cp...
Source/core/dom/Range.cpp:662: case Node::DOCUMENT_TYPE_NODE:
DocumentType is not a ContainerNode and thus cannot have any children.

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/Text...
File Source/core/editing/TextIterator.cpp (right):

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/Text...
Source/core/editing/TextIterator.cpp:1187: if (Node* childAtOffset =
startNode->childNode(startOffset)) {
ContainerNode::childNode(index) will return 0 if the offset is greater than the
number of children anyway.

https://codereview.chromium.org/171953002/diff/40001/Source/core/html/track/v...
File Source/core/html/track/vtt/VTTRegion.cpp (left):

https://codereview.chromium.org/171953002/diff/40001/Source/core/html/track/v...
Source/core/html/track/vtt/VTTRegion.cpp:378: for (size_t i = 0; i <
m_cueContainer->childNodeCount() && !m_scrollTimer.isActive(); ++i) {
This one was pretty inefficient :)

[eseidel, 2014-02-19 05:39:53]

lgtm

Please see the comments below.

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Containe...
File Source/core/dom/ContainerNode.cpp (left):

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Containe...
Source/core/dom/ContainerNode.cpp:540:
removedChildren.reserveInitialCapacity(childNodeCount());
On 2014/02/19 04:13:33, Chris Dumez wrote:
> I don't think this one is worth it as we end up traversing the children twice
> instead of once for a likely small win on Vector::append().

I expect walking the child list twice may be cheaper than a possible extra
malloc.  But I could be wrong.  I would expect this change to be visible on
microbenchmarks (one way or the other).  This function has historically ben
quite hot.

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/Text...
File Source/core/editing/TextIterator.cpp (right):

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/Text...
Source/core/editing/TextIterator.cpp:1187: if (Node* childAtOffset =
startNode->childNode(startOffset)) {
On 2014/02/19 04:13:33, Chris Dumez wrote:
> ContainerNode::childNode(index) will return 0 if the offset is greater than
the
> number of children anyway.

This seems like rather odd behavior to depend on.  I'm a bit surprised it
doesn't ASSERT.

If you're going to depend on this behavior I would leave a comment to explain
that.

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/mark...
File Source/core/editing/markup.cpp (right):

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/mark...
Source/core/editing/markup.cpp:797: bool elementHasTwoChildren =
(element->firstChild() && element->firstChild()->nextSibling() &&
!element->firstChild()->nextSibling()->nextSibling());
I wonder if a generic hasChildCount(unsigned) is useful.

https://codereview.chromium.org/171953002/diff/40001/Source/core/html/track/v...
File Source/core/html/track/vtt/VTTRegion.cpp (left):

https://codereview.chromium.org/171953002/diff/40001/Source/core/html/track/v...
Source/core/html/track/vtt/VTTRegion.cpp:378: for (size_t i = 0; i <
m_cueContainer->childNodeCount() && !m_scrollTimer.isActive(); ++i) {
On 2014/02/19 04:13:33, Chris Dumez wrote:
> This one was pretty inefficient :)

We should consider renaming this method "computeChildCount()" or
"countChilden()" to indicate that it does work.

[Inactive, 2014-02-19 14:28:15]

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Containe...
File Source/core/dom/ContainerNode.cpp (left):

https://codereview.chromium.org/171953002/diff/40001/Source/core/dom/Containe...
Source/core/dom/ContainerNode.cpp:540:
removedChildren.reserveInitialCapacity(childNodeCount());
On 2014/02/19 05:39:54, eseidel wrote:
> On 2014/02/19 04:13:33, Chris Dumez wrote:
> > I don't think this one is worth it as we end up traversing the children
twice
> > instead of once for a likely small win on Vector::append().
> 
> I expect walking the child list twice may be cheaper than a possible extra
> malloc.  But I could be wrong.  I would expect this change to be visible on
> microbenchmarks (one way or the other).  This function has historically ben
> quite hot.

Ok then. I prefer to keep this change out of the CL. We can try this one out
separately if we want to.

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/Text...
File Source/core/editing/TextIterator.cpp (right):

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/Text...
Source/core/editing/TextIterator.cpp:1187: if (Node* childAtOffset =
startNode->childNode(startOffset)) {
On 2014/02/19 05:39:54, eseidel wrote:
> On 2014/02/19 04:13:33, Chris Dumez wrote:
> > ContainerNode::childNode(index) will return 0 if the offset is greater than
> the
> > number of children anyway.
> 
> This seems like rather odd behavior to depend on.  I'm a bit surprised it
> doesn't ASSERT.
> 
> If you're going to depend on this behavior I would leave a comment to explain
> that.

Yes, I don't have a better proposal than this at the moment. I will add a
comment to explain.

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/mark...
File Source/core/editing/markup.cpp (right):

https://codereview.chromium.org/171953002/diff/40001/Source/core/editing/mark...
Source/core/editing/markup.cpp:797: bool elementHasTwoChildren =
(element->firstChild() && element->firstChild()->nextSibling() &&
!element->firstChild()->nextSibling()->nextSibling());
On 2014/02/19 05:39:54, eseidel wrote:
> I wonder if a generic hasChildCount(unsigned) is useful.

This is likely the only place where we would need it but why not. At least,
people would be less prone to using childNodeCount() for such use cases. I'll
look into this now.

https://codereview.chromium.org/171953002/diff/40001/Source/core/html/track/v...
File Source/core/html/track/vtt/VTTRegion.cpp (left):

https://codereview.chromium.org/171953002/diff/40001/Source/core/html/track/v...
Source/core/html/track/vtt/VTTRegion.cpp:378: for (size_t i = 0; i <
m_cueContainer->childNodeCount() && !m_scrollTimer.isActive(); ++i) {
On 2014/02/19 05:39:54, eseidel wrote:
> On 2014/02/19 04:13:33, Chris Dumez wrote:
> > This one was pretty inefficient :)
> 
> We should consider renaming this method "computeChildCount()" or
> "countChilden()" to indicate that it does work.

Good idea. Do you mind if I do this in a follow-up patch? There are still quite
a few uses of childNodeCount() so I think it is worth splitting the changes.

[Inactive, 2014-02-19 16:19:56]

I updated the patch as per review comments. Please take another look (especially
the new ContainerNode::hasChildCount() method).

[eseidel, 2014-02-19 18:26:50]

lgtm

https://codereview.chromium.org/171953002/diff/140001/Source/core/editing/mar...
File Source/core/editing/markup.cpp (right):

https://codereview.chromium.org/171953002/diff/140001/Source/core/editing/mar...
Source/core/editing/markup.cpp:797: return element->hasChildCount(2) &&
isTabSpanTextNode(element->firstChild()->firstChild()) &&
element->firstChild()->nextSibling()->isTextNode();
The last one can be element->lastChild() instead of
element->firstChild()->nextSibling() if you rather.

[Inactive, 2014-02-19 18:36:32]

https://codereview.chromium.org/171953002/diff/140001/Source/core/editing/mar...
File Source/core/editing/markup.cpp (right):

https://codereview.chromium.org/171953002/diff/140001/Source/core/editing/mar...
Source/core/editing/markup.cpp:797: return element->hasChildCount(2) &&
isTabSpanTextNode(element->firstChild()->firstChild()) &&
element->firstChild()->nextSibling()->isTextNode();
On 2014/02/19 18:26:50, eseidel wrote:
> The last one can be element->lastChild() instead of
> element->firstChild()->nextSibling() if you rather.

Better indeed thanks, Done.

[Inactive, 2014-02-19 18:36:37]

The CQ bit was checked by ch.dumez@samsung.com

[commit-bot: I haz the power, 2014-02-19 22:03:20]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ch.dumez@samsung.com/171953002/250001

[commit-bot: I haz the power, 2014-02-19 23:09:08]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ch.dumez@samsung.com/171953002/250001

[commit-bot: I haz the power, 2014-02-19 23:47:28]

Change committed as 167444