Simplify logic in |Range::BoundaryNodeChildrenWillBeRemoved|. [chromium/src : main]
Sanket Joshi (Gerrit)
Sanket Joshi added 5 comments![]( "Open in Gerrit")
This seems like it would be a nice perf win once it lands. Do you have any before/after measurements to show how much of an improvement we can expect in node removal + live range scenarios?
Current logic can sometimes have perf issues when the to-be removed container has too many children. Thie patch is to simplify the logic and improve performance in certain scenarios. The change should have no behavior change.Could you be more specific what was causing the performance slow down and how you are fixing it?
for (Node* node_to_be_removed = container.firstChild(); node_to_be_removed;
node_to_be_removed = node_to_be_removed->nextSibling()) {
if (boundary.ChildBefore() == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
for (Node* n = &boundary.Container(); n; n = n->parentNode()) {
if (n == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
}Question for Mason/Kent when you all review: Any idea why this was originally written this way? Seems like excessive, unnecessary processing (unless we're missing something).
for (Node* node_to_be_removed = container.firstChild(); node_to_be_removed;
node_to_be_removed = node_to_be_removed->nextSibling()) {
for (Node* n = &boundary.Container(); n;
n = n->ParentOrShadowHostElement()) {
if (n == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
}
}Can this method be similarly optimized?
// remove children in body.
GetDocument().body()->setTextContent("");Do we have more exhaustive test coverage for node removal + live ranges? If not, we should add some to ensure we're not unexpectedly regressing something.
Related details
- Siye Liu
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Siye Liu (Gerrit)
Siye Liu added 3 comments![]( "Open in Gerrit")
Current logic can sometimes have perf issues when the to-be removed container has too many children. Thie patch is to simplify the logic and improve performance in certain scenarios. The change should have no behavior change.Could you be more specific what was causing the performance slow down and how you are fixing it?
Updated the description.
for (Node* node_to_be_removed = container.firstChild(); node_to_be_removed;
node_to_be_removed = node_to_be_removed->nextSibling()) {
for (Node* n = &boundary.Container(); n;
n = n->ParentOrShadowHostElement()) {
if (n == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
}
}Can this method be similarly optimized?
Yes we can. Will address the issue in shadow scenario in a separate CL.
// remove children in body.
GetDocument().body()->setTextContent("");Do we have more exhaustive test coverage for node removal + live ranges? If not, we should add some to ensure we're not unexpectedly regressing something.
Good idea. I checked WPT test coverage and found live ranges + node removal. https://source.chromium.org/chromium/chromium/src/+/main:third_party/blink/web_tests/external/wpt/dom/ranges/Range-mutations-removeChild.html
Related details
- Sanket Joshi
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Sanket Joshi (Gerrit)
Sanket Joshi added 3 comments![]( "Open in Gerrit")
This seems like it would be a nice perf win once it lands. Do you have any before/after measurements to show how much of an improvement we can expect in node removal + live range scenarios?
Doesn't look like this was addressed. Let me know if I missed anything.
for (Node* node_to_be_removed = container.firstChild(); node_to_be_removed;
node_to_be_removed = node_to_be_removed->nextSibling()) {
for (Node* n = &boundary.Container(); n;
n = n->ParentOrShadowHostElement()) {
if (n == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
}
}Siye LiuCan this method be similarly optimized?
Yes we can. Will address the issue in shadow scenario in a separate CL.
Can we file a crbug for this as well and link it in this CL's description?
// remove children in body.
GetDocument().body()->setTextContent("");Siye LiuDo we have more exhaustive test coverage for node removal + live ranges? If not, we should add some to ensure we're not unexpectedly regressing something.
Good idea. I checked WPT test coverage and found live ranges + node removal. https://source.chromium.org/chromium/chromium/src/+/main:third_party/blink/web_tests/external/wpt/dom/ranges/Range-mutations-removeChild.html
- Siye Liu
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Siye Liu (Gerrit)
Siye Liu added 3 comments![]( "Open in Gerrit")
Sanket JoshiThis seems like it would be a nice perf win once it lands. Do you have any before/after measurements to show how much of an improvement we can expect in node removal + live range scenarios?
Doesn't look like this was addressed. Let me know if I missed anything.
The issue was marked as resolved so it skipped my final check.
The perf improvement depends on the number of children in the to-be removed container node. In my test case, I have 50k children in the container. And the perf improvement is huge for each `BoundaryNodeChildrenWillBeRemoved` call: 3.7ms vs 0.003 ms (1000x faster).
for (Node* node_to_be_removed = container.firstChild(); node_to_be_removed;
node_to_be_removed = node_to_be_removed->nextSibling()) {
for (Node* n = &boundary.Container(); n;
n = n->ParentOrShadowHostElement()) {
if (n == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
}
}Siye LiuCan this method be similarly optimized?
Sanket JoshiYes we can. Will address the issue in shadow scenario in a separate CL.
Can we file a crbug for this as well and link it in this CL's description?
Acknowledged
// remove children in body.
GetDocument().body()->setTextContent("");Siye LiuDo we have more exhaustive test coverage for node removal + live ranges? If not, we should add some to ensure we're not unexpectedly regressing something.
Sanket JoshiGood idea. I checked WPT test coverage and found live ranges + node removal. https://source.chromium.org/chromium/chromium/src/+/main:third_party/blink/web_tests/external/wpt/dom/ranges/Range-mutations-removeChild.html
Thanks for confirming.
- Sanket Joshi
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Sanket Joshi (Gerrit)
Sanket Joshi voted and added 2 comments![]( "Open in Gerrit")
Votes added by Sanket Joshi
| Code-Review | +1 |
Sanket JoshiThis seems like it would be a nice perf win once it lands. Do you have any before/after measurements to show how much of an improvement we can expect in node removal + live range scenarios?
Siye LiuDoesn't look like this was addressed. Let me know if I missed anything.
The issue was marked as resolved so it skipped my final check.
The perf improvement depends on the number of children in the to-be removed container node. In my test case, I have 50k children in the container. And the perf improvement is huge for each `BoundaryNodeChildrenWillBeRemoved` call: 3.7ms vs 0.003 ms (1000x faster).
Thanks. Would be good to add some of the perf details to the PR description, given that is what this PR is meant to address.
LGTM % one comment about adding perf details in the PR description
Related details
- Siye Liu
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Siye Liu (Gerrit)
Siye Liu added 1 comment![]( "Open in Gerrit")
Sanket JoshiThis seems like it would be a nice perf win once it lands. Do you have any before/after measurements to show how much of an improvement we can expect in node removal + live range scenarios?
Siye LiuDoesn't look like this was addressed. Let me know if I missed anything.
Sanket JoshiThe issue was marked as resolved so it skipped my final check.
The perf improvement depends on the number of children in the to-be removed container node. In my test case, I have 50k children in the container. And the perf improvement is huge for each `BoundaryNodeChildrenWillBeRemoved` call: 3.7ms vs 0.003 ms (1000x faster).
Thanks. Would be good to add some of the perf details to the PR description, given that is what this PR is meant to address.
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Kent Tamura (Gerrit)
Kent Tamura voted and added 2 comments![]( "Open in Gerrit")
Votes added by Kent Tamura
| Code-Review | +1 |
2 comments
Current logic can sometimes have perf issues when the to-be removed container node has too many children because |Range::BoundaryNodeChildrenWillBeRemoved| iterates through all the children of the container node and check every cached range if the child of container node is an ancestor container of the range. This patch is to simplify the logic and improve performance by adjusting the boundary points of the range to the start of the container node if the container node contains the range. The change should have no behavior change.Please wrap paragraphs in 72 columns.
for (Node* node_to_be_removed = container.firstChild(); node_to_be_removed;
node_to_be_removed = node_to_be_removed->nextSibling()) {
if (boundary.ChildBefore() == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
for (Node* n = &boundary.Container(); n; n = n->parentNode()) {
if (n == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
}Question for Mason/Kent when you all review: Any idea why this was originally written this way? Seems like excessive, unnecessary processing (unless we're missing something).
I have no idea. This code was written by an Apple people 14 years ago.
Related details
- Koji Ishii
- Mason Freed
- Sanket Joshi
- Siye Liu
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Koji Ishii (Gerrit)
Koji Ishii voted and added 1 comment![]( "Open in Gerrit")
- Mason Freed
- Sanket Joshi
- Siye Liu
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Siye Liu (Gerrit)
Siye Liu added 2 comments![]( "Open in Gerrit")
Current logic can sometimes have perf issues when the to-be removed container node has too many children because |Range::BoundaryNodeChildrenWillBeRemoved| iterates through all the children of the container node and check every cached range if the child of container node is an ancestor container of the range. This patch is to simplify the logic and improve performance by adjusting the boundary points of the range to the start of the container node if the container node contains the range. The change should have no behavior change.Please wrap paragraphs in 72 columns.
Acknowledged
for (Node* node_to_be_removed = container.firstChild(); node_to_be_removed;
node_to_be_removed = node_to_be_removed->nextSibling()) {
if (boundary.ChildBefore() == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
for (Node* n = &boundary.Container(); n; n = n->parentNode()) {
if (n == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
}Kent TamuraQuestion for Mason/Kent when you all review: Any idea why this was originally written this way? Seems like excessive, unnecessary processing (unless we're missing something).
I have no idea. This code was written by an Apple people 14 years ago.
Done
Related details
- Mason Freed
- Sanket Joshi
Code-Coverage
Code-Review
No-Unresolved-Comments
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Siye Liu (Gerrit)
Siye Liu added 3 comments![]( "Open in Gerrit")
Siye LiuLooking through this CL, I don't think this is an issue with the highlight API, rather just a general issue with ranges are implemented in Chromium. If we positioned the ranges in the DOM but didn't add them to highlights, wouldn't we still encounter the same perf problem?
Sanket JoshiIf we still hold a reference to the range, then the range is cached in `Document` and it's boundaries will be adjusted.
In the repro page from the bug:
for (let i = 0; i < paragraphs.length; i++) {
let range = new Range();
range.setStart(paragraphs[i].childNodes[0], 0);
range.setEnd(paragraphs[i].childNodes[0], 2);
highlight.add(range);
}The range should be garbage collected after the for loop. It is the case if we don't add the range to custom highlight.
If we hold references to all the ranges, then we might encounter the same perf hit. So I opened a discussion in an earlier comment:
https://chromium-review.googlesource.com/c/chromium/src/+/5414145/comment/30847ee0_4f3d5348/.
Siye LiuIn the example that you shared above, I wouldn't expect the range to be garbage collected until the `highlight` object is garbage collected. I think that's not an unreasonable way to add ranges to highlights.
Done
if (range->ShouldDisposeIfContainerRemoved() &&Siye LiuThis CL only removes cached ranges created by Custom Highlight. Should we expand the scenario and remove all ranges if container is cleared?
Done
for (Range* range : ranges_to_be_removed) {
DetachRange(range);
}Sanket JoshiIt is by design that live ranges are updated to the parent when the attached node is removed from the DOM. Such an update would make live ranges in highlights spec incompliant.
Siye Liu
Siye LiuThis cl only removes the cached highlight range if and only if its containing parent removes all of its children. In this case, the range would have been adjusted to (parent, 0, parent, 0) which makes no sense for highlight. So I think it is fine to remove it from the cache.
Sanket JoshiAnother option is to adjust the range to (parent, 0, parent, 0) instead of removing it from |ranges_|.
Siye LiuHow are ranges adjusted in these cases in other browsers? I believe the highlight API is implemented in the nightly builds of Firefox and Safari.
Done
Related details
- Mason Freed
- Sanket Joshi
Code-Coverage
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mason Freed (Gerrit)
Mason Freed voted and added 2 comments![]( "Open in Gerrit")
Votes added by Mason Freed
| Code-Review | +1 |
2 comments
for (Node* node_to_be_removed = container.firstChild(); node_to_be_removed;
node_to_be_removed = node_to_be_removed->nextSibling()) {
if (boundary.ChildBefore() == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
for (Node* n = &boundary.Container(); n; n = n->parentNode()) {
if (n == node_to_be_removed) {
boundary.SetToStartOfNode(container);
return;
}
}Kent TamuraQuestion for Mason/Kent when you all review: Any idea why this was originally written this way? Seems like excessive, unnecessary processing (unless we're missing something).
Siye LiuI have no idea. This code was written by an Apple people 14 years ago.
Done
Yeah, I also don't know. The new code seems much easier to understand. Perhaps `contains()` didn't exist back then?
Related details
- Sanket Joshi
- Siye Liu
Code-Coverage
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Siye Liu (Gerrit)
Siye Liu voted Commit-Queue+2![]( "Open in Gerrit")
| Commit-Queue | +2 |
Related details
- Sanket Joshi
Code-Coverage
Code-Review
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Chromium LUCI CQ (Gerrit)
Chromium LUCI CQ submitted the change![]( "Open in Gerrit")
Change information
Simplify logic in |Range::BoundaryNodeChildrenWillBeRemoved|.
Current logic can sometimes have perf issues when the to-be removed
container node has too many children because
|Range::BoundaryNodeChildrenWillBeRemoved| iterates through all the
children of the container node and check every cached range if the
child of container node is an ancestor container of the range. This
patch is to simplify the logic and improve performance by adjusting
the boundary points of the range to the start of the container node if
the container node contains the range. The change should have no
behavior change.
The perf improvement is huge when there are lots of children (~50k) in
container node. For each BoundaryNodeChildrenWillBeRemoved call: 3.7ms
vs 0.003 ms (1000x faster).
|Range::BoundaryShadowNodeChildrenWillBeRemoved| can also be simplified.
Will submit a separate CL to address the
issue(https://issues.chromium.org/issues/336222283).
- M third_party/blink/renderer/core/dom/range.cc
- M third_party/blink/renderer/core/dom/range_test.cc
Code-Review: +1 by Kent Tamura, +1 by Koji Ishii, +1 by Mason Freed, +1 by Sanket Joshi
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |