Bug 73969 - NodeChildList shouldn't be in NodeListNodeData
Summary: NodeChildList shouldn't be in NodeListNodeData
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Ryosuke Niwa
URL:
Keywords:
Depends on: 74028
Blocks: 73853
  Show dependency treegraph
 
Reported: 2011-12-06 17:38 PST by Ryosuke Niwa
Modified: 2011-12-14 15:18 PST (History)
6 users (show)

See Also:


Attachments
cleanup; might have improved perf. (18.72 KB, patch)
2011-12-09 01:02 PST, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Updated per Darin's comment; also fixed ChildNodeList::itemWithName (19.20 KB, patch)
2011-12-09 12:34 PST, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Fixed the bug (21.32 KB, patch)
2011-12-09 17:25 PST, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Fixed per Darin's comments (21.31 KB, patch)
2011-12-09 17:51 PST, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Fixed per Sam's comment (33.09 KB, patch)
2011-12-13 17:08 PST, Ryosuke Niwa
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ryosuke Niwa 2011-12-06 17:38:52 PST
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.
Comment 1 Ryosuke Niwa 2011-12-09 01:02:51 PST
Created attachment 118546 [details]
cleanup; might have improved perf.
Comment 2 Darin Adler 2011-12-09 10:12:35 PST
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.
Comment 3 Ryosuke Niwa 2011-12-09 10:24:27 PST
(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.
Comment 4 Darin Adler 2011-12-09 10:43:54 PST
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.
Comment 5 Ryosuke Niwa 2011-12-09 10:44:45 PST
(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.
Comment 6 Ryosuke Niwa 2011-12-09 12:27:34 PST
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.
Comment 7 Ryosuke Niwa 2011-12-09 12:34:34 PST
Created attachment 118613 [details]
Updated per Darin's comment; also fixed ChildNodeList::itemWithName
Comment 8 Darin Adler 2011-12-09 16:59:27 PST
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())?
Comment 9 Ryosuke Niwa 2011-12-09 17:25:42 PST
Created attachment 118669 [details]
Fixed the bug
Comment 10 Ryosuke Niwa 2011-12-09 17:39:58 PST
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.
Comment 11 Ryosuke Niwa 2011-12-09 17:51:13 PST
Created attachment 118674 [details]
Fixed per Darin's comments
Comment 12 Ryosuke Niwa 2011-12-12 13:15:08 PST
Ping reviewers.
Comment 13 Sam Weinig 2011-12-12 13:25:24 PST
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.
Comment 14 Ryosuke Niwa 2011-12-12 13:33:10 PST
(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.
Comment 15 Sam Weinig 2011-12-12 13:38:49 PST
(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.
Comment 16 Ryosuke Niwa 2011-12-12 13:44:30 PST
(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.
Comment 17 Ryosuke Niwa 2011-12-13 17:08:40 PST
Created attachment 119114 [details]
Fixed per Sam's comment
Comment 18 WebKit Review Bot 2011-12-13 17:11:02 PST
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.
Comment 19 Ryosuke Niwa 2011-12-13 17:18:30 PST
(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.
Comment 20 Ryosuke Niwa 2011-12-14 13:14:08 PST
Ping reviewers.
Comment 21 Ryosuke Niwa 2011-12-14 13:52:41 PST
Thanks for the review, Sam! I'm excited to land this patch.
Comment 22 Ryosuke Niwa 2011-12-14 15:18:30 PST
Comment on attachment 119114 [details]
Fixed per Sam's comment

Clearing flags on attachment: 119114

Committed r102834: <http://trac.webkit.org/changeset/102834>
Comment 23 Ryosuke Niwa 2011-12-14 15:18:36 PST
All reviewed patches have been landed.  Closing bug.