Bug 113433

Summary: ContainerNode::removeChildren should first detach the children then remove them
Product: WebKit Reporter: Andrei Bucur <abucur>
Component: DOMAssignee: Andrei Bucur <abucur>
Status: RESOLVED FIXED    
Severity: Normal CC: commit-queue, esprehn+autocc, esprehn, ojan.autocc, rniwa, WebkitBugTracker, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 110352    
Attachments:
Description Flags
Patch
none
Patch
none
Patch
none
Simple version of the patch
none
Perf results for the very simple patch
none
Patch for landing none

Andrei Bucur
Reported 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.
Attachments
Patch (4.59 KB, patch)
2013-04-01 04:13 PDT, Andrei Bucur 		no flags
DetailsFormatted DiffDiff
Patch (7.36 KB, patch)
2013-04-15 05:24 PDT, Andrei Bucur 		no flags
DetailsFormatted DiffDiff
Patch (6.61 KB, patch)
2013-04-15 06:48 PDT, Andrei Bucur 		no flags
DetailsFormatted DiffDiff
Simple version of the patch (3.15 KB, patch)
2013-04-18 05:33 PDT, Andrei Bucur 		no flags
DetailsFormatted DiffDiff
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
DetailsFormatted DiffDiff
Show Obsolete (4) View All Add attachment proposed patch, testcase, etc.
Andrei Bucur
Comment 1 2013-04-01 04:13:55 PDT
Created attachment 195951 [details] Patch
Antti Koivisto
Comment 2 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).
Andrei Bucur
Comment 3 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 ***
Andrei Bucur
Comment 4 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.
Andrei Bucur
Comment 5 2013-04-15 05:24:39 PDT
Created attachment 198113 [details] Patch
Andrei Bucur
Comment 6 2013-04-15 06:48:09 PDT
Created attachment 198121 [details] Patch
Andrei Bucur
Comment 7 2013-04-16 04:14:43 PDT
*** This bug has been marked as a duplicate of bug 114677 ***
Andrei Bucur
Comment 8 2013-04-18 00:54:12 PDT
Use this bug to track the simple change of first detaching a child before it is removed.
Andrei Bucur
Comment 9 2013-04-18 05:33:48 PDT
Created attachment 198725 [details] Simple version of the patch
Andrei Bucur
Comment 10 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.
Elliott Sprehn
Comment 11 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.
Andrei Bucur
Comment 12 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.
Ryosuke Niwa
Comment 13 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?
Andrei Bucur
Comment 14 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.
Ryosuke Niwa
Comment 15 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.
Andrei Bucur
Comment 16 2013-04-19 09:56:49 PDT
Created attachment 198893 [details] Patch for landing
WebKit Commit Bot
Comment 17 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>
WebKit Commit Bot
Comment 18 2013-04-19 10:24:46 PDT
All reviewed patches have been landed. Closing bug.
Note You need to log in before you can comment on or make changes to this bug.