Bug 55209 - Speed up node removal by removing the Node::willRemove() function
Summary: Speed up node removal by removing the Node::willRemove() function
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: PC OS X 10.5
: P2 Normal
Assignee: Hajime Morrita
URL:
Keywords:
Depends on: 55624
Blocks:
  Show dependency treegraph
 
Reported: 2011-02-25 01:04 PST by Eric Seidel (no email)
Modified: 2012-05-10 04:36 PDT (History)
16 users (show)

See Also:


Attachments
does not work yet (5.47 KB, patch)
2011-02-25 03:07 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
Patch (25.06 KB, patch)
2012-05-07 18:36 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch (25.02 KB, patch)
2012-05-07 18:41 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Gave more specific names, reduced refcount churn. (25.42 KB, patch)
2012-05-07 20:15 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch (25.34 KB, patch)
2012-05-07 20:23 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch (25.41 KB, patch)
2012-05-07 21:00 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch for landing (25.42 KB, patch)
2012-05-07 21:24 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch for landing (25.42 KB, patch)
2012-05-07 21:26 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from ec2-cq-01 (6.45 MB, application/zip)
2012-05-07 23:53 PDT, WebKit Review Bot
no flags Details
Patch for landing (27.47 KB, patch)
2012-05-09 01:05 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch for landing (27.85 KB, patch)
2012-05-09 02:33 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch for landing (27.59 KB, patch)
2012-05-09 18:40 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff
Patch for landing (28.11 KB, patch)
2012-05-09 21:24 PDT, Hajime Morrita
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Eric Seidel (no email) 2011-02-25 01:04:08 PST
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.
Comment 1 Eric Seidel (no email) 2011-02-25 01:33:33 PST
bug 46763 is when HTMLSourceElement::willRemove was added.
Comment 2 Eric Seidel (no email) 2011-02-25 03:07:54 PST
Created attachment 83789 [details]
does not work yet
Comment 3 Eric Seidel (no email) 2011-02-25 03:09:38 PST
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.
Comment 4 Eric Seidel (no email) 2011-02-25 03:12:28 PST
This may not be a path worth pursuing at this time.
Comment 5 Hajime Morrita 2012-05-07 18:36:41 PDT
Created attachment 140643 [details]
Patch
Comment 6 Hajime Morrita 2012-05-07 18:38:12 PDT
This patch comes from a different angle (Bug 82701).
Comment 7 Hajime Morrita 2012-05-07 18:39:15 PDT
Ryosuke, Eric, could you take a look?
Comment 8 Hajime Morrita 2012-05-07 18:41:59 PDT
Created attachment 140645 [details]
Patch
Comment 9 Eric Seidel (no email) 2012-05-07 18:58:34 PDT
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?
Comment 10 Ryosuke Niwa 2012-05-07 19:04:13 PDT
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.
Comment 11 Hajime Morrita 2012-05-07 19:27:43 PDT
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 :-)
Comment 12 Hajime Morrita 2012-05-07 20:15:11 PDT
Created attachment 140656 [details]
Gave more specific names, reduced refcount churn.
Comment 13 Hajime Morrita 2012-05-07 20:23:28 PDT
Created attachment 140657 [details]
Patch
Comment 14 Ryosuke Niwa 2012-05-07 20:38:59 PDT
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?
Comment 15 Hajime Morrita 2012-05-07 21:00:42 PDT
Created attachment 140661 [details]
Patch
Comment 16 Hajime Morrita 2012-05-07 21:03:31 PDT
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.
Comment 17 Ryosuke Niwa 2012-05-07 21:12:54 PDT
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.
Comment 18 Hajime Morrita 2012-05-07 21:24:59 PDT
Created attachment 140663 [details]
Patch for landing
Comment 19 Hajime Morrita 2012-05-07 21:26:58 PDT
Created attachment 140665 [details]
Patch for landing
Comment 20 WebKit Review Bot 2012-05-07 23:52:35 PDT
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
Comment 21 WebKit Review Bot 2012-05-07 23:53:05 PDT
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
Comment 22 Hajime Morrita 2012-05-08 02:37:21 PDT
Looks like a real regression. looking.
Comment 23 Hajime Morrita 2012-05-09 01:05:26 PDT
Created attachment 140880 [details]
Patch for landing
Comment 24 WebKit Review Bot 2012-05-09 01:57:58 PDT
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
Comment 25 Hajime Morrita 2012-05-09 02:33:32 PDT
Created attachment 140892 [details]
Patch for landing
Comment 26 WebKit Review Bot 2012-05-09 03:16:13 PDT
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
Comment 27 Hajime Morrita 2012-05-09 18:40:12 PDT
Created attachment 141070 [details]
Patch for landing
Comment 28 WebKit Review Bot 2012-05-09 19:45:42 PDT
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
Comment 29 Hajime Morrita 2012-05-09 21:24:38 PDT
Created attachment 141080 [details]
Patch for landing
Comment 30 WebKit Review Bot 2012-05-10 04:36:27 PDT
Comment on attachment 141080 [details]
Patch for landing

Clearing flags on attachment: 141080

Committed r116629: <http://trac.webkit.org/changeset/116629>
Comment 31 WebKit Review Bot 2012-05-10 04:36:47 PDT
All reviewed patches have been landed.  Closing bug.