Optimize ChildNode{Insertion,Removal}Notifier::notify() by lazily taking a snapshot of child nodes

[Kentaro Hara]

notifyDescendantRemovedFromDocument() cannot iterate child nodes in this way:

  void notifyDescendantRemovedFromDocument(Node* node) {
    for (Node* child = node->firstChild(); child; child = child->nextSibling()) {
      ...;
      notifyNodeRemovedFromDocument(child);
    }
  }

This is because notifyNodeRemovedFromDocument(child) might dispatch events and the events might change child trees. To avoid security issues, the current code takes a snapshot of child nodes before starting the iteration, like this.

  void notifyDescendantRemovedFromDocument(Node* node) {
     NodeVector children;
     getChildNodes(node, children); // Take a snapshot.
     for (int i = 0; i < children.size(); i++) {
       ...;
       notifyNodeRemovedFromDocument(children[i]);
     }
   }

Based on the observation that in almost all cases events won't be dispatched from inside notifyNodeRemovedFromDocument(), we can implement a "lazy" snapshot. The snapshot is taken at the point where EventDispatcher::dispatchEvent() is invoked. The snapshot is not taken unless any event is dispatched.

[Kentaro Hara]

Created attachment 156020 [details]
Patch

[Kentaro Hara]

Created attachment 156022 [details]
Patch

[Kentaro Hara]

Created attachment 156040 [details]
Patch

[Adam Barth]

Comment on attachment 156040 [details]
Patch

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

Nice idea.  Some detailed comments below.

> Source/WebCore/dom/ContainerNode.h:304
> +static ChildNodesSnapshot* latestSnapshot = 0;

Please don't add static global variables to header files.  That will add storage for this variable to every complication unit that includes this header!

> Source/WebCore/dom/ContainerNode.h:324
> +        if (m_childNodes)
> +            delete m_childNodes;

Can we use an OwnPtr to have this delete happen automatically?

> Source/WebCore/dom/ContainerNode.h:338
> +        Node* ret = (*m_childNodes)[m_currentIndex++].get();

ret -> node (prefer complete words in variable names)

> Source/WebCore/dom/ContainerNode.h:344
> +        if (!hasSnapshot()) {

Prefer early return.

> Source/WebCore/dom/ContainerNodeAlgorithms.cpp:69
> +    ChildNodesSnapshot snapshot(node);

I'd put the word "Lazy" into the name of this class to make it clear that the snapshot is happening lazily.

[Kentaro Hara]

Created attachment 156248 [details]
Patch

[Kentaro Hara]

(In reply to comment #3)
> > Source/WebCore/dom/ContainerNode.h:304
> > +static ChildNodesSnapshot* latestSnapshot = 0;
> 
> Please don't add static global variables to header files.  That will add storage for this variable to every complication unit that includes this header!
> 
> > Source/WebCore/dom/ContainerNode.h:324
> > +        if (m_childNodes)
> > +            delete m_childNodes;
> 
> Can we use an OwnPtr to have this delete happen automatically?
> 
> > Source/WebCore/dom/ContainerNode.h:338
> > +        Node* ret = (*m_childNodes)[m_currentIndex++].get();
> 
> ret -> node (prefer complete words in variable names)
> 
> > Source/WebCore/dom/ContainerNode.h:344
> > +        if (!hasSnapshot()) {
> 
> Prefer early return.
> 
> > Source/WebCore/dom/ContainerNodeAlgorithms.cpp:69
> > +    ChildNodesSnapshot snapshot(node);
> 
> I'd put the word "Lazy" into the name of this class to make it clear that the snapshot is happening lazily.

All done. Thanks.

[Adam Barth]

Comment on attachment 156248 [details]
Patch

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

> Source/WebCore/dom/ContainerNode.h:308
> +    ChildNodesLazySnapshot(Node* parentNode)

explicit

> Source/WebCore/dom/ContainerNode.h:325
> +        if (LIKELY(!m_childNodes.get())) {

Can we call hasSnapshot() here?  That would be slightly more readable.

[Kentaro Hara]

Created attachment 157065 [details]
patch for landing

[Kentaro Hara]

Created attachment 157066 [details]
patch for landing

[WebKit Review Bot]

Comment on attachment 157066 [details]
patch for landing

Clearing flags on attachment: 157066

Committed r124990: <http://trac.webkit.org/changeset/124990>

[Ojan Vafai]

Could we do this same trick for the methods in ContainerNode that call collectChildrenAndRemoveFromOldParent and/or collectTargetNodes? It might have a performance benefit for large innerHTML calls for example.

[Kentaro Hara]

(In reply to comment #11)
> Could we do this same trick for the methods in ContainerNode that call collectChildrenAndRemoveFromOldParent and/or collectTargetNodes? It might have a performance benefit for large innerHTML calls for example.

Yes, I'll do after investigating performance and security stuff.

[Ryosuke Niwa]

Nice! 9% improvement indeed.

http://webkit-perf.appspot.com/graph.html#tests=[[40018,2001,32196]]&sel=1344366304381.4546,1344436602563.2727,2520.1612903225805,4758.064516129032&displayrange=7&datatype=running