Bug 113433 - ContainerNode::removeChildren should first detach the children then remove them
Summary: ContainerNode::removeChildren should first detach the children then remove them
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Andrei Bucur
URL:
Keywords:
Depends on:
Blocks: 110352
  Show dependency treegraph
 
Reported: 2013-03-27 12:17 PDT by Andrei Bucur
Modified: 2013-04-19 10:24 PDT (History)
7 users (show)

See Also:


Attachments
Patch (4.59 KB, patch)
2013-04-01 04:13 PDT, Andrei Bucur
no flags Details | Formatted Diff | Diff
Patch (7.36 KB, patch)
2013-04-15 05:24 PDT, Andrei Bucur
no flags Details | Formatted Diff | Diff
Patch (6.61 KB, patch)
2013-04-15 06:48 PDT, Andrei Bucur
no flags Details | Formatted Diff | Diff
Simple version of the patch (3.15 KB, patch)
2013-04-18 05:33 PDT, Andrei Bucur
no flags Details | Formatted Diff | Diff
Perf results for the very simple patch (483.97 KB, application/x-webarchive)
2013-04-18 08:16 PDT, Andrei Bucur
no flags Details
Patch for landing (3.45 KB, patch)
2013-04-19 09:56 PDT, Andrei Bucur
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andrei Bucur 2013-03-27 12:17:19 PDT
The order of operations in ContainerNode::removeChildren is unintuitive and can lead to subtle bugs. The function ContainerNode::removeChild first detaches the child and then removes it from the DOM tree. ContainerNode::removeChildren does it the other way around. This leaves the render tree in an inconsistent state when calling detach on the removed nodes (the renderers point to nodes that are no longer in the DOM).
The main reason invoked for this behaviour is the performance gain. However, the removeChildren method makes two iterations thorough the children list that may be avoided:
- removedChildren.reserveInitialCapacity(childNodeCount()); // childNodeCount is O(n)
- children detachment is another O(n)
The patch should also try to remove these time consumers as well.
Comment 1 Andrei Bucur 2013-04-01 04:13:55 PDT
Created attachment 195951 [details]
Patch
Comment 2 Antti Koivisto 2013-04-01 04:50:18 PDT
Comment on attachment 195951 [details]
Patch

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

> Source/WebCore/dom/ContainerNode.cpp:459
> +static void willRemoveChildren(ContainerNode* container, NodeVector& children)

This function has unclear purpose (doing both pre-removal tasks and building up the child vector). I think it would be better to pass in an initialized child vector and possibly rename the function to something more descriptive (though I don't have great suggestions, fireEventsBeforeRemovingAllChildren or something).
Comment 3 Andrei Bucur 2013-04-08 08:31:16 PDT
This will be fixed in https://bugs.webkit.org/show_bug.cgi?id=113517 .

*** This bug has been marked as a duplicate of bug 113517 ***
Comment 4 Andrei Bucur 2013-04-15 00:55:26 PDT
https://bugs.webkit.org/show_bug.cgi?id=113517 is a lot harder than initially estimated. Just refactor the code a bit and first detach then remove the nodes.
Comment 5 Andrei Bucur 2013-04-15 05:24:39 PDT
Created attachment 198113 [details]
Patch
Comment 6 Andrei Bucur 2013-04-15 06:48:09 PDT
Created attachment 198121 [details]
Patch
Comment 7 Andrei Bucur 2013-04-16 04:14:43 PDT

*** This bug has been marked as a duplicate of bug 114677 ***
Comment 8 Andrei Bucur 2013-04-18 00:54:12 PDT
Use this bug to track the simple change of first detaching a child before it is removed.
Comment 9 Andrei Bucur 2013-04-18 05:33:48 PDT
Created attachment 198725 [details]
Simple version of the patch
Comment 10 Andrei Bucur 2013-04-18 08:16:49 PDT
Created attachment 198738 [details]
Perf results for the very simple patch

innserHTML-setter.html and html5-full-render.html
There doesn't seem to be any performance regression. This is aligned with the small performance boost found in the more complex patch.
Comment 11 Elliott Sprehn 2013-04-19 04:02:34 PDT
I think the Simple version is the way to go. Make tiny changes and watch the perf and security issues as you go. Calling shrink(0) on the vector is also really weird, I don't think that's what you want to do since it frees the vector buffer and you end up mallocing again.

btw I don't think html5-full-render.html is the right benchmark for this. It's doing document.write() which goes directly at the parser/tree builder. It doesn't go through innerHTML which would benchmark this code.
Comment 12 Andrei Bucur 2013-04-19 05:39:14 PDT
Great, thanks for the review!

(In reply to comment #11)
> I think the Simple version is the way to go. Make tiny changes and watch the perf and security issues as you go. Calling shrink(0) on the vector is also really weird, I don't think that's what you want to do since it frees the vector buffer and you end up mallocing again.

shrink() doesn't modify the capacity. It will just remove the nodes, keeping the buffer intact. This is why I said reserveInitialCapacity() is not required any more.
shrinkCapacity() does what you describe.
The advanced patch saves a free() and possibly a malloc(). The free() that happens when exiting willRemoveChildren() and the possible malloc() when calling reserveInitialCapacity, if the inline size of the vector is smaller than the number of nodes. I'm not counting the loop through the children required when calling reserveInitialCapacity.

> 
> btw I don't think html5-full-render.html is the right benchmark for this. It's doing document.write() which goes directly at the parser/tree builder. It doesn't go through innerHTML which would benchmark this code.
Comment 13 Ryosuke Niwa 2013-04-19 08:41:51 PDT
Comment on attachment 198725 [details]
Simple version of the patch

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

> Source/WebCore/dom/ContainerNode.cpp:633
> -            for (size_t i = 0; i < removedChildren.size(); ++i) {
> -                Node* removedChild = removedChildren[i].get();
> -                if (removedChild->attached())
> -                    removedChild->detach();
> +                removedChildren.append(n.release());

Why aren't we moving this loop before the other loop?
Is the comment you removed no longer applicable?
Comment 14 Andrei Bucur 2013-04-19 09:21:11 PDT
Comment on attachment 198725 [details]
Simple version of the patch

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

>> Source/WebCore/dom/ContainerNode.cpp:633
>> +                removedChildren.append(n.release());
> 
> Why aren't we moving this loop before the other loop?
> Is the comment you removed no longer applicable?

No, it's not applicable. The pointers are fixed after each node is removed and I didn't find any evidence of detachment being faster for removed nodes that a new iteration through them is worth the effort.
Comment 15 Ryosuke Niwa 2013-04-19 09:23:10 PDT
Comment on attachment 198725 [details]
Simple version of the patch

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

>>> Source/WebCore/dom/ContainerNode.cpp:633
>>> +                removedChildren.append(n.release());
>> 
>> Why aren't we moving this loop before the other loop?
>> Is the comment you removed no longer applicable?
> 
> No, it's not applicable. The pointers are fixed after each node is removed and I didn't find any evidence of detachment being faster for removed nodes that a new iteration through them is worth the effort.

Please clarify that in the change log.
Comment 16 Andrei Bucur 2013-04-19 09:56:49 PDT
Created attachment 198893 [details]
Patch for landing
Comment 17 WebKit Commit Bot 2013-04-19 10:24:42 PDT
Comment on attachment 198893 [details]
Patch for landing

Clearing flags on attachment: 198893

Committed r148754: <http://trac.webkit.org/changeset/148754>
Comment 18 WebKit Commit Bot 2013-04-19 10:24:46 PDT
All reviewed patches have been landed.  Closing bug.