Bug 73969 – NodeChildList shouldn't be in NodeListNodeData

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

[Ryosuke Niwa]

We don't need to invalidate child node lists for all ancestors when inserting or removing a child. Furthermore, it makes zero sense to remove child node list of an element when adding/removing an attribute to/from the element.

[Ryosuke Niwa]

Created attachment 118546 [details]
cleanup; might have improved perf.

[Darin Adler]

Comment on attachment 118546 [details]
cleanup; might have improved perf.

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

> Source/WebCore/ChangeLog:8
> +        Move the child node list's cache from NodeListNodeData to NodeRareData.

Why? I’d guess that this would cost more memory since all the other rare data is allocated every time.

Please make sure to say *why* in your comments and change logs. This does not say why.

[Ryosuke Niwa]

(In reply to comment #2)
> (From update of attachment 118546 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=118546&action=review
> 
> > Source/WebCore/ChangeLog:8
> > +        Move the child node list's cache from NodeListNodeData to NodeRareData.
> 
> Why? I’d guess that this would cost more memory since all the other rare data is allocated every time.
> 
> Please make sure to say *why* in your comments and change logs. This does not say why.

The goal here is to get rid of NodeListNodeData altogether and move that to TreeScope-level hash map of node to node lists in order to resolve the bug 73853.

According to the stat I posted on https://bugs.webkit.org/show_bug.cgi?id=73853#c10, we can clear all node lists caches on every DOM mutation without having to iterate through ancestors.

However, since child node lists are second most common node lists used (see https://bugs.webkit.org/show_bug.cgi?id=73853#c6; alive about 60% of the time), and there is no need for it be invalidated when non-child descendants mutate, it seems undesirable to make it hang off of a TreeScope.

[Darin Adler]

So then the comment I would have written in the change log would be something like this:

    Move NodeChildList out of NodeListNodeData to separate it from the other node lists.

    NodeChildList is simple to invalidate when children change. Other node lists need to
    be invalidated more often; NodeChildList should be separated from them to make that easy.

[Ryosuke Niwa]

(In reply to comment #4)
> So then the comment I would have written in the change log would be something like this:
> 
>     Move NodeChildList out of NodeListNodeData to separate it from the other node lists.
> 
>     NodeChildList is simple to invalidate when children change. Other node lists need to
>     be invalidated more often; NodeChildList should be separated from them to make that easy.

Sure. That sounds good to me. I'll add that.

[Ryosuke Niwa]

Comment on attachment 118546 [details]
cleanup; might have improved perf.

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

> Source/WebCore/ChangeLog:23
> +        (WebCore::ChildNodeList::itemWithName): Added; while DynamicNodeList's version uses TreeScope's
> +        getElementById, this is undesirable for ChildNodeList because this would create DynamicNodeList
> +        on on the TreeScope and we'll end up having to walk up the entire tree in childrenChanged.

It turned out this isn't accurate at all :( TreeScope has a DocumentOrderedMap so it's super fast.

[Ryosuke Niwa]

Created attachment 118613 [details]
Updated per Darin's comment; also fixed ChildNodeList::itemWithName

[Darin Adler]

Comment on attachment 118613 [details]
Updated per Darin's comment; also fixed ChildNodeList::itemWithName

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

review- because of the offset problem

> Source/WebCore/dom/ChildNodeList.cpp:114
> +    if (m_node->isDocumentNode() || m_node->inDocument()) {

Why do we need to check isDocumentNode()? Doesn't inDocument() return true for document nodes themselves?

> Source/WebCore/dom/ChildNodeList.cpp:118
> +        // In the case of multiple nodes with the same name, just fall through.

Shouldn’t this comment say “the same ID”?

> Source/WebCore/dom/ChildNodeList.cpp:121
> +    unsigned offset = 0;

I think you forgot the code that updates offset. It’s always zero!

Why didn’t any test case catch this? I think we may need to add test cases.

> Source/WebCore/dom/Node.cpp:1016
>      ASSERT(rareData());

Shouldn’t this assertion say ASSERT(hasRareData())?

[Ryosuke Niwa]

Created attachment 118669 [details]
Fixed the bug

[Ryosuke Niwa]

Will upload a new patch that addresses the rest of your comments in a minute.

(In reply to comment #8)
> (From update of attachment 118613 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=118613&action=review
> 
> review- because of the offset problem
> 
> > Source/WebCore/dom/ChildNodeList.cpp:114
> > +    if (m_node->isDocumentNode() || m_node->inDocument()) {
> 
> Why do we need to check isDocumentNode()? Doesn't inDocument() return true for document nodes themselves?

Good point. I just copied it from DynamicNodeList but document node can never have a child so this check is useless.

> > Source/WebCore/dom/ChildNodeList.cpp:118
> > +        // In the case of multiple nodes with the same name, just fall through.
> 
> Shouldn’t this comment say “the same ID”?

Fixed.

> > Source/WebCore/dom/ChildNodeList.cpp:121
> > +    unsigned offset = 0;
> 
> I think you forgot the code that updates offset. It’s always zero!
> 
> Why didn’t any test case catch this? I think we may need to add test cases.

Fixed and added a test.

> > Source/WebCore/dom/Node.cpp:1016
> >      ASSERT(rareData());
> 
> Shouldn’t this assertion say ASSERT(hasRareData())?

Sure. Fixed.

[Ryosuke Niwa]

Created attachment 118674 [details]
Fixed per Darin's comments

[Ryosuke Niwa]

Ping reviewers.

[Sam Weinig]

I am not thrilled with making ChildNodeList not inherit from DynamicNodeList.  I would be more comfortable moving things that are unique to non-ChildNodeList DynamicNodeList into a new shared class that derives from DynamicNodeList.

[Ryosuke Niwa]

(In reply to comment #13)
> I am not thrilled with making ChildNodeList not inherit from DynamicNodeList.  I would be more comfortable moving things that are unique to non-ChildNodeList DynamicNodeList into a new shared class that derives from DynamicNodeList.

But ChildNodeList and DynamicNodeList share so little! They even manage DynamicNodeList::Caches differently.

[Sam Weinig]

(In reply to comment #14)
> (In reply to comment #13)
> > I am not thrilled with making ChildNodeList not inherit from DynamicNodeList.  I would be more comfortable moving things that are unique to non-ChildNodeList DynamicNodeList into a new shared class that derives from DynamicNodeList.
> 
> But ChildNodeList and DynamicNodeList share so little! They even manage DynamicNodeList::Caches differently.

Well, they share the important point that they are both dynamic as opposed to static.

[Ryosuke Niwa]

(In reply to comment #15)
> (In reply to comment #14)
> > 
> > But ChildNodeList and DynamicNodeList share so little! They even manage DynamicNodeList::Caches differently.
> 
> Well, they share the important point that they are both dynamic as opposed to static.

Sure. But implementation-wise, they're almost completely disjoint.

We could rename the existing DynamicNodeList to something like SubtreeDynamicNodeList and create new DynamicNodeList that has item(unsigned) = 0 and itemName(~) if you'll prefer that.

[Ryosuke Niwa]

Created attachment 119114 [details]
Fixed per Sam's comment

[WebKit Review Bot]

Attachment 119114 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1

Source/WebCore/dom/TagNodeList.h:33:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Source/WebCore/dom/ClassNodeList.h:39:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Source/WebCore/dom/NameNodeList.h:34:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 3 in 21 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Ryosuke Niwa]

(In reply to comment #18)
> Attachment 119114 [details] did not pass style-queue:
> 
> Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1
> 
> Source/WebCore/dom/TagNodeList.h:33:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
> Source/WebCore/dom/ClassNodeList.h:39:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
> Source/WebCore/dom/NameNodeList.h:34:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
> Total errors found: 3 in 21 files
> 
> 
> If any of these errors are false positives, please file a bug against check-webkit-style.

While it'll be nice to fix these styles, I think it's out of scope for this patch since I'm just renaming the superclass.

[Ryosuke Niwa]

Ping reviewers.

[Ryosuke Niwa]

Thanks for the review, Sam! I'm excited to land this patch.

[Ryosuke Niwa]

Comment on attachment 119114 [details]
Fixed per Sam's comment

Clearing flags on attachment: 119114

Committed r102834: <http://trac.webkit.org/changeset/102834>

[Ryosuke Niwa]

All reviewed patches have been landed.  Closing bug.