Bug 55209 – Speed up node removal by removing the Node::willRemove() function

• Component: New Bugs
• Status: RESOLVED FIXED

[Eric Seidel (no email)]

Remove support for Node::willRemove()

It slows down performance of moving/removing nodes.   This shows up in peacekeeper's domDynamicCreationCreateElement (as well as other benchmarks I'm sure).

There was only 1 usage (HTMLFrameOwnerElement::willRemove()) until recently.  Now we have HTMLSourceElement::willRemove().  Both should easily be able to be removed.

On my local copy of peacekeeper's domDynamicCreationCreateElement:

Before:
avg 366.3333333333333
median 366
stdev 2.712112747574399
min 362
max 377

After removing willRemove():
avg 350.23333333333335
median 349
stdev 4.200661323596031
min 347
max 370

I got those by commenting out willRemove().  Now I'm going to investigate actually getting rid of it.

[Eric Seidel (no email)]

bug 46763 is when HTMLSourceElement::willRemove was added.

[Eric Seidel (no email)]

Created attachment 83789 [details]
does not work yet

[Eric Seidel (no email)]

My first attempt to remove HTMLFrameOwnerElement::willRemove is attached.  It fails because detach() expects that frames will already be stopped/disconnected before detach.

If no, this happens:

ASSERTION FAILED: !eventDispatchForbidden()
/Projects/WebKit/Source/WebCore/dom/Node.cpp(2648) : bool WebCore::Node::dispatchGenericEvent(WTF::PassRefPtr<WebCore::Event>)
1   WebCore::Node::dispatchGenericEvent(WTF::PassRefPtr<WebCore::Event>)
2   WebCore::Node::dispatchEvent(WTF::PassRefPtr<WebCore::Event>)
3   WebCore::Node::dispatchBlurEvent()
4   WebCore::Document::setFocusedNode(WTF::PassRefPtr<WebCore::Node>)
5   -[WebHTMLView clearFocus]
6   -[WebHTMLView resignFirstResponder]
7   -[NSWindow makeFirstResponder:]
8   WebCore::safeRemoveFromSuperview(NSView*)
9   WebCore::Widget::removeFromSuperview()
10  WebCore::ScrollView::platformRemoveChild(WebCore::Widget*)
11  WebCore::ScrollView::removeChild(WebCore::Widget*)
12  WebCore::RenderWidget::resumeWidgetHierarchyUpdates()
13  WebCore::Element::detach()
14  WebCore::ContainerNode::removeChildren()
15  WebCore::Document::implicitOpen()
16  WebCore::Document::open(WebCore::Document*)
17  WebCore::Document::write(WebCore::SegmentedString const&, WebCore::Document*)
18  WebCore::documentWrite(JSC::ExecState*, WebCore::HTMLDocument*, WebCore::NewlineRequirement)
19  WebCore::JSHTMLDocument::write(JSC::ExecState*)
20  WebCore::jsHTMLDocumentPrototypeFunctionWrite(JSC::ExecState*)
21  0x50e9f68001b8
22  JSC::JITCode::execute(JSC::RegisterFile*, JSC::ExecState*, JSC::JSGlobalData*)
23  JSC::Interpreter::executeCall(JSC::ExecState*, JSC::JSObject*, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&)
24  JSC::call(JSC::ExecState*, JSC::JSValue, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&)
25  WebCore::JSMainThreadExecState::call(JSC::ExecState*, JSC::JSValue, JSC::CallType, JSC::CallData const&, JSC::JSValue, JSC::ArgList const&)
26  WebCore::JSEventListener::handleEvent(WebCore::ScriptExecutionContext*, WebCore::Event*)
27  WebCore::EventTarget::fireEventListeners(WebCore::Event*, WebCore::EventTargetData*, WTF::Vector<WebCore::RegisteredEventListener, 1ul>&)
28  WebCore::EventTarget::fireEventListeners(WebCore::Event*)
29  WebCore::DOMWindow::dispatchEvent(WTF::PassRefPtr<WebCore::Event>, WTF::PassRefPtr<WebCore::EventTarget>)
30  WebCore::DOMWindow::dispatchTimedEvent(WTF::PassRefPtr<WebCore::Event>, WebCore::Document*, double*, double*)
31  WebCore::DOMWindow::dispatchLoadEvent()
Program received signal:  “EXC_BAD_ACCESS”.

Previously willRemove would have detached/disconnected the frame, so it wouldn't have a widget to talk to when the detach came.

[Eric Seidel (no email)]

This may not be a path worth pursuing at this time.

[Hajime Morrita]

Created attachment 140643 [details]
Patch

[Hajime Morrita]

This patch comes from a different angle (Bug 82701).

[Hajime Morrita]

Ryosuke, Eric, could you take a look?

[Hajime Morrita]

Created attachment 140645 [details]
Patch

[Eric Seidel (no email)]

Comment on attachment 140645 [details]
Patch

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

> Source/WebCore/dom/ContainerNodeAlgorithms.h:288
> +        RefPtr<Node> m_owner;
> +        RefPtr<Node> m_ownerParent;

This seems like it will cause a lot of ref churn, no?

> Source/WebCore/dom/ContainerNodeAlgorithms.h:316
> +    unsigned size = m_list.size();
> +    for (unsigned i = 0; i < size; ++i)
> +        m_list[0].notify();

It seems like we'd want to do the refs right here, right before the notify if we could?  Maybe that's a separate change, since this is aready a 5% speedup. :)

> Source/WebCore/dom/Node.h:218
> +    bool isFrameOwnerElement() const { return getFlag(IsFrameOwnerElementFlag); }

How much does giving up this bit save us?  Is this the big 5% win?

[Ryosuke Niwa]

Comment on attachment 140645 [details]
Patch

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

This patch looks very promising!

> Source/WebCore/ChangeLog:24
> +        notification _before_ its removal. To handle that, this change
> +        introduces ChildNodePreRemovalNotifier which collects
> +        corresponding decendant elements and notifies (now non-virtual)
> +        willRemove().

Instead of making this generic, can we call it something like DispatchUnloadInFrames to make the semantics clearer?
Presumably, we don't want more people to start using this notifier, do we?

> Source/WebCore/ChangeLog:27
> +        Even though this approach doesn't kill pre-removal tree traversal
> +        completely, it's a bit more efficient due to the de-virtualization.

I think this patch paves a way to eventually get rid of pre-removal tree traversal.
There are a lot of things we can do to avoid it in the future once this patch is in.
e.g. we can check the number of child frames, and avoid the traversal if there's none.

> Source/WebCore/ChangeLog:34
> +        (WebCore::ContainerNode::notifyChildrenWillRemove): Added. Used from FrameLoader to replace Document::willRemove() call.

Ditto. We should probably make this member function semantically tied to unload event and/or frame.

> Source/WebCore/dom/ContainerNodeAlgorithms.h:301
> +    for (Node* node = root; node; node = node->traverseNextNode(root)) {

We might be able to do a bit of optimizations like skipping children of object, embed, etc... when they don't use fallback contents.

[Hajime Morrita]

Hi thanks for quick feedback!

(In reply to comment #9)
> (From update of attachment 140645 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=140645&action=review
> 
> > Source/WebCore/dom/ContainerNodeAlgorithms.h:288
> > +        RefPtr<Node> m_owner;
> > +        RefPtr<Node> m_ownerParent;
> 
> This seems like it will cause a lot of ref churn, no?
Maybe. On the other hand, original willRemove() also has protecting vector.
So this shouldn't be worse.

> 
> > Source/WebCore/dom/ContainerNodeAlgorithms.h:316
> > +    unsigned size = m_list.size();
> > +    for (unsigned i = 0; i < size; ++i)
> > +        m_list[0].notify();
> 
> It seems like we'd want to do the refs right here, right before the notify if we could?  Maybe that's a separate change, since this is aready a 5% speedup. :)
That won't help since willRemove() on other frame can blow stuff.

> 
> > Source/WebCore/dom/Node.h:218
> > +    bool isFrameOwnerElement() const { return getFlag(IsFrameOwnerElementFlag); }
> 
> How much does giving up this bit save us?  Is this the big 5% win?
This is just a part of that.
I'm going to re-use this to devirtualize insertedInto() and removedFrom() to
utilize this single bit as much as possible :-)

[Hajime Morrita]

Created attachment 140656 [details]
Gave more specific names, reduced refcount churn.

[Hajime Morrita]

Created attachment 140657 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 140657 [details]
Patch

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

> Source/WebCore/ChangeLog:4
> +        https://bugs.webkit.org/show_bug.cgi?id=55209
> +        Remove support for Node::willRemove()

Please fix the bug title & url order.

> Source/WebCore/ChangeLog:5
> +

Please insert "reviewed by" line here.

> Source/WebCore/dom/ContainerNodeAlgorithms.h:275
> +    explicit ChildFrameDisconnector(Node* root);
> +    void disconnect();
> +
> +private:
> +    void collectDescendant(Node* root);
> +    void collectDescendant(ElementShadow*);

Given that disconnect() is always called immediately after ChildFrameDisconnector is instantiated, should we just make this a global function?
e.g. disconnectDescendentFrames(Node* root) {
  Vector<Target, 10> list;
  collectDescendant(list, root);
  unsigned size = list.size();
  ... // Disconnect them
}
That way, you can probably allocate stack buffer for the vector (e.g. say 10 entries) and avoid heap allocation for common cases.

> Source/WebCore/dom/Element.cpp:937
>      setSavedLayerScrollOffset(IntSize());

Now we call this function before calling setContainsFullScreenElementOnAncestorsCrossingFrameBoundaries.
Is it safe to make this change?

> Source/WebCore/html/HTMLFrameOwnerElement.cpp:55
>      // FIXME: It is unclear why this can't be moved to removedFromDocument()
>      // this is the only implementation of willRemove in WebCore!

Do you know the answer to this function? Also, didn't we get rid of removedFromDocument in one of your patches?
We should at least update the comment if that's the case.

> Source/WebCore/html/HTMLSourceElement.cpp:66
> +void HTMLSourceElement::removedFrom(Node* insertionPoint)

Shouldn't this argument called as removalPoint or removalRoot instead?

[Hajime Morrita]

Created attachment 140661 [details]
Patch

[Hajime Morrita]

Comment on attachment 140657 [details]
Patch

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

>> Source/WebCore/ChangeLog:4
>> +        Remove support for Node::willRemove()
> 
> Please fix the bug title & url order.

Done.

>> Source/WebCore/ChangeLog:5
>> +
> 
> Please insert "reviewed by" line here.

Done.

>> Source/WebCore/dom/ContainerNodeAlgorithms.h:275
>> +    void collectDescendant(ElementShadow*);
> 
> Given that disconnect() is always called immediately after ChildFrameDisconnector is instantiated, should we just make this a global function?
> e.g. disconnectDescendentFrames(Node* root) {
>   Vector<Target, 10> list;
>   collectDescendant(list, root);
>   unsigned size = list.size();
>   ... // Disconnect them
> }
> That way, you can probably allocate stack buffer for the vector (e.g. say 10 entries) and avoid heap allocation for common cases.

This "instantiate and invoke" is a pattern which follows other notification classes.
But yes. We can pre-allocate some elements in the stack. The updated patch does it.

>> Source/WebCore/dom/Element.cpp:937
>>      setSavedLayerScrollOffset(IntSize());
> 
> Now we call this function before calling setContainsFullScreenElementOnAncestorsCrossingFrameBoundaries.
> Is it safe to make this change?

Good catch! It even doesn't need to be inside the if clause.
Fixed.

>> Source/WebCore/html/HTMLFrameOwnerElement.cpp:55
>>      // this is the only implementation of willRemove in WebCore!
> 
> Do you know the answer to this function? Also, didn't we get rid of removedFromDocument in one of your patches?
> We should at least update the comment if that's the case.

We now know the answer! Updated.

>> Source/WebCore/html/HTMLSourceElement.cpp:66
>> +void HTMLSourceElement::removedFrom(Node* insertionPoint)
> 
> Shouldn't this argument called as removalPoint or removalRoot instead?

Done.

[Ryosuke Niwa]

Comment on attachment 140661 [details]
Patch

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

> Source/WebCore/ChangeLog:9
> +        o5% speedup on Dromaeo dom-modify.

o5%?

> Source/WebCore/dom/ContainerNode.h:97
> +    // Note that this cleanup is done by ContainerNode in most cases.
> +    // Only the Document class needs to take care of itself since ContainerNode doesn't care about its lifetime.

I don't really understand this comment. I think it's better not to add it.

> Source/WebCore/dom/ContainerNodeAlgorithms.cpp:124
> +    if (m_owner->parentNode() == m_ownerParent)
> +        toFrameOwnerElement(m_owner.get())->disconnectContentFrame();

I think this function should be inline to avoid incurring cost when m_owner->parentNode() != m_ownerParent.

> Source/WebCore/dom/ContainerNodeAlgorithms.h:299
> +inline void ChildFrameDisconnector::collectDescendant(Node* root)

I don't think this function needs to be inline since it's a recursive function anyway.
I'm almost certain you can safely move it to cpp file.
I suspect compilers would reject this function from being inlined.

[Hajime Morrita]

Created attachment 140663 [details]
Patch for landing

[Hajime Morrita]

Created attachment 140665 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 140665 [details]
Patch for landing

Rejecting attachment 140665 [details] from commit-queue.

New failing tests:
media/video-source-moved.html
Full output: http://queues.webkit.org/results/12647293

[WebKit Review Bot]

Created attachment 140683 [details]
Archive of layout-test-results from ec2-cq-01

The attached test failures were seen while running run-webkit-tests on the commit-queue.
Bot: ec2-cq-01  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.35-28-virtual-x86_64-with-Ubuntu-10.10-maverick

[Hajime Morrita]

Looks like a real regression. looking.

[Hajime Morrita]

Created attachment 140880 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 140880 [details]
Patch for landing

Rejecting attachment 140880 [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:
was not declared in this scope
Source/WebCore/dom/Node.h:823: error: request for member 'add' in 'urls', which is of non-class type 'int'
Source/WebCore/dom/Node.h: At global scope:
Source/WebCore/dom/Node.h:826: error: expected initializer before '*' token
Source/WebCore/dom/Node.h:831: error: expected initializer before '*' token
Source/WebCore/dom/Node.h:836: error: expected initializer before '*' token
make: *** [out/Debug/obj.target/webcore_dom/Source/WebCore/dom/ActiveDOMObject.o] Error 1

Full output: http://queues.webkit.org/results/12647556

[Hajime Morrita]

Created attachment 140892 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 140892 [details]
Patch for landing

Rejecting attachment 140892 [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:
ource/WebCore/dom/ActiveDOMObject.cpp:31:
Source/WebCore/dom/Node.h: In function 'void WebCore::addSubresourceURL(WTF::ListHashSet<WebCore::KURL, 256ul, WebCore::KURLHash>&, const WebCore::KURL&)':
Source/WebCore/dom/Node.h:822: error: 'class WTF::ListHashSet<WebCore::KURL, 256ul, WebCore::KURLHash>' has no member named 'isNull'
make: *** [out/Debug/obj.target/webcore_dom/Source/WebCore/dom/Attr.o] Error 1
make: *** [out/Debug/obj.target/webcore_dom/Source/WebCore/dom/ActiveDOMObject.o] Error 1

Full output: http://queues.webkit.org/results/12652630

[Hajime Morrita]

Created attachment 141070 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 141070 [details]
Patch for landing

Rejecting attachment 141070 [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:
webkit-commit-queue/Source/WebKit/chromium/webkit --revision 136044 --non-interactive --force --accept theirs-conflict --ignore-externals' in '/mnt/git/webkit-commit-queue/Source/WebKit/chromium'
49>At revision 136044.

________ running '/usr/bin/python tools/clang/scripts/update.py --mac-only' in '/mnt/git/webkit-commit-queue/Source/WebKit/chromium'

________ running '/usr/bin/python gyp_webkit' in '/mnt/git/webkit-commit-queue/Source/WebKit/chromium'
Updating webkit projects from gyp files...

Full output: http://queues.webkit.org/results/12653773

[Hajime Morrita]

Created attachment 141080 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 141080 [details]
Patch for landing

Clearing flags on attachment: 141080

Committed r116629: <http://trac.webkit.org/changeset/116629>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.