|
|
Created:
4 years, 12 months ago by rhogan Modified:
4 years, 4 months ago CC:
blink-reviews, blink-reviews-layout_chromium.org, chromium-reviews, eae+blinkwatch, jchaffraix+rendering, leviw+renderwatch, pdr+renderingwatchlist_chromium.org, szager+layoutwatch_chromium.org, zoltan1 Base URL:
https://chromium.googlesource.com/chromium/src.git@master Target Ref:
refs/pending/heads/master Project:
chromium Visibility:
Public. |
DescriptionSkip dirtying lines when attaching children prior to attaching oneself
If a parent is about to be (re)attached then there is no point in keeping its
dirty lines up to date as we attach children. The parent will get a full layout
anyway and we end up having to dirty the lineboxes for every inlines we add - which
can get expensive if there are a lot of inlines.
BUG=345972
Committed: https://crrev.com/dcb4562e8f888588dfe686b1b9d864e39b3dc5cb
Cr-Commit-Position: refs/heads/master@{#408601}
Patch Set 1 #Patch Set 2 : Updated #Patch Set 3 : Updated #Patch Set 4 : Updted #
Total comments: 1
Patch Set 5 : Updated #Patch Set 6 : Skip dirtying lines when attaching children prior to attaching oneself #
Total comments: 4
Patch Set 7 : Skip dirtying lines when attaching children prior to attaching oneself #Patch Set 8 : Skip dirtying lines when attaching children prior to attaching oneself #
Depends on Patchset: Messages
Total messages: 35 (12 generated)
Description was changed from ========== bug 345972 BUG=345972 ========== to ========== Skip dirtying lines when attaching children prior to attaching oneself If a parent is about to be (re)attached then there is no point in keeping its dirty lines up to date as we attach children. The parent will get a full layout anyway and we end up having to dirty the lineboxes for every inlines we add - which can get expensive if there are a lot of inlines. BUG=345972 ==========
robhogan@gmail.com changed reviewers: + esprehn@chromium.org
I don't think this fixes the bug, the parent will be already attached since we're incrementally rendering. You need to null check node there btw, I need to think more about this optimization, I don't think this case happens very often. When detaching we destroy the layout tree from the bottom up so I don't know why the parent would have needsAttach() but still have a LayoutObject. -- You received this message because you are subscribed to the Google Groups "Blink Reviews" group. To unsubscribe from this group and stop receiving emails from it, send an email to blink-reviews+unsubscribe@chromium.org.
I don't think this fixes the bug, the parent will be already attached since we're incrementally rendering. You need to null check node there btw, I need to think more about this optimization, I don't think this case happens very often. When detaching we destroy the layout tree from the bottom up so I don't know why the parent would have needsAttach() but still have a LayoutObject. -- You received this message because you are subscribed to the Google Groups "Chromium-reviews" group. To unsubscribe from this group and stop receiving emails from it, send an email to chromium-reviews+unsubscribe@chromium.org.
On 2015/12/24 at 17:36:55, esprehn wrote: > I don't think this fixes the bug, the parent will be already attached since > we're incrementally rendering. It definitely addresses an n^2 in attaching children that happens at https://mxr.mozilla.org/mozilla-central/source/layout/generic/nsBlockFrame.cp... - you can see it if you apply this patch: --- a/third_party/WebKit/Source/core/layout/LayoutInline.cpp +++ b/third_party/WebKit/Source/core/layout/LayoutInline.cpp @@ -893,9 +893,11 @@ IntRect LayoutInline::linesBoundingBox() const InlineBox* LayoutInline::culledInlineFirstLineBox() const { + int count = 0; for (LayoutObject* curr = firstChild(); curr; curr = curr->nextSibling()) { if (curr->isFloatingOrOutOfFlowPositioned()) continue; + count++; // We want to get the margin box in the inline direction, and then use our font ascent/descent in the block // direction (aligned to the root box's baseline). @@ -912,6 +914,8 @@ InlineBox* LayoutInline::culledInlineFirstLineBox() const return currText->firstTextBox(); } } + if (!parent()->isLayoutInline()) + printf("%p count: %i\n", this, count); return nullptr; } The inline children are all getting added at once in both my test case and mozilla page so we end up running culledInlineFirstInlineBox() every time we add a child to the parent. I don't think there's incremental rendering happening here - the nodes arent't getting appended one at a time, they're getting added all at once. > > You need to null check node there btw, Yes, good point. > I need to think more about this > optimization, I don't think this case hkappens very often. It happens every time we run attachChildren - the parent node needsAttach() while attaching its children. To my knowledge this will happen any time we load a page of static mark up like the one in the mozilla page or simulate it by using innerHTML. > When detaching we > destroy the layout tree from the bottom up so I don't know why the parent > would have needsAttach() but still have a LayoutObject. The parent gets a layout object before it attaches its children and needsAttach() until all the children are attached. My point in this CL is that there is no point in milling through the descendants re-dirtying lines every time we attach a child while the parent is still attaching its siblings so needsAttach() is my way of telling if the parent is in the middle of this mass-attach operation. Really we only need to call dirtyLinesFromChangedChild() if we're appending a child to an already attached parent.
You're just observing network speed and parser yielding. The parser may yield at any time when loading that Mozilla page, especially if your network is slow, that would mean the parent is already attached and then the n^2 is back. This patch doesn't fix the bug. -- You received this message because you are subscribed to the Google Groups "Blink Reviews" group. To unsubscribe from this group and stop receiving emails from it, send an email to blink-reviews+unsubscribe@chromium.org.
You're just observing network speed and parser yielding. The parser may yield at any time when loading that Mozilla page, especially if your network is slow, that would mean the parent is already attached and then the n^2 is back. This patch doesn't fix the bug. -- You received this message because you are subscribed to the Google Groups "Chromium-reviews" group. To unsubscribe from this group and stop receiving emails from it, send an email to chromium-reviews+unsubscribe@chromium.org.
On 2015/12/28 at 17:58:43, esprehn wrote: > You're just observing network speed and parser yielding. The parser may > yield at any time when loading that Mozilla page, especially if your > network is slow, that would mean the parent is already attached and then > the n^2 is back. This patch doesn't fix the bug. > Fair enough - I've updated the test accordingly and created an early return in culledInlineBox if the object's parent is detached or is attaching children. The test case improves by about 60%.
https://codereview.chromium.org/1550513003/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/layout/LayoutInline.cpp (right): https://codereview.chromium.org/1550513003/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/layout/LayoutInline.cpp:896: if (node() && node()->childNeedsStyleRecalc()) why is it okay to return null from the first line box whenever the inline needs a style recalc? This would definitely need a comment to explain why this early return exists as well. Why not do it for culledInlineLastLineBox(), also what if line box culling is disabled because there's padding?
On 2016/01/05 at 07:40:38, esprehn wrote: > https://codereview.chromium.org/1550513003/diff/60001/third_party/WebKit/Sour... > File third_party/WebKit/Source/core/layout/LayoutInline.cpp (right): > > https://codereview.chromium.org/1550513003/diff/60001/third_party/WebKit/Sour... > third_party/WebKit/Source/core/layout/LayoutInline.cpp:896: if (node() && node()->childNeedsStyleRecalc()) > why is it okay to return null from the first line box whenever the inline needs a style recalc? We're here to dirty lineboxes but the style recalc will ensure the object gets a layout anyway. > This would definitely need a comment to explain why this early return exists as well. OK. >Why not do it for culledInlineLastLineBox()? I don't think we need to - doing it for culledInlineFirstLineBox achieves the early return from dirtyLinesFromChangedChild() that we need. > also what if line box culling is disabled because there's padding? Then we don't end up here and don't iterate through the inlines looking for the 'first' - firstLineBoxIncludingCulling() just returns firstLineBox(). I've updated the CL to return early from dirtyLinesFromChangeChild() instead, it makes more sense there. Also updated the test.
On 2016/01/05 at 09:52:56, rhogan wrote: > On 2016/01/05 at 07:40:38, esprehn wrote: > > https://codereview.chromium.org/1550513003/diff/60001/third_party/WebKit/Sour... > > File third_party/WebKit/Source/core/layout/LayoutInline.cpp (right): > > > > https://codereview.chromium.org/1550513003/diff/60001/third_party/WebKit/Sour... > > third_party/WebKit/Source/core/layout/LayoutInline.cpp:896: if (node() && node()->childNeedsStyleRecalc()) > > why is it okay to return null from the first line box whenever the inline needs a style recalc? > > We're here to dirty lineboxes but the style recalc will ensure the object gets a layout anyway. > > > This would definitely need a comment to explain why this early return exists as well. > OK. > > >Why not do it for culledInlineLastLineBox()? > I don't think we need to - doing it for culledInlineFirstLineBox achieves the early return from dirtyLinesFromChangedChild() that we need. > > > also what if line box culling is disabled because there's padding? > Then we don't end up here and don't iterate through the inlines looking for the 'first' - firstLineBoxIncludingCulling() just returns firstLineBox(). > > I've updated the CL to return early from dirtyLinesFromChangeChild() instead, it makes more sense there. Also updated the test. @esprehn - should I iterate on this or am I on the wrong track?
I don't think looking at the recalcStyle dirty bits from inside the linebox dirtying code is right, childNeedsStyleRecalc doesn't mean attach either. What if a child just has new padding? Why does this code exist at all if we can just skip it much of the time?
On 2016/01/20 at 09:01:45, esprehn wrote: > I don't think looking at the recalcStyle dirty bits from inside the linebox dirtying code is right, childNeedsStyleRecalc doesn't mean attach either. What if a child just has new padding? Why does this code exist at all if we can just skip it much of the time? This is still in my queue - and the updated patch looks right to me now. Want to take another look?
Description was changed from ========== Skip dirtying lines when attaching children prior to attaching oneself If a parent is about to be (re)attached then there is no point in keeping its dirty lines up to date as we attach children. The parent will get a full layout anyway and we end up having to dirty the lineboxes for every inlines we add - which can get expensive if there are a lot of inlines. BUG=345972 ========== to ========== Skip dirtying lines when attaching children prior to attaching oneself If a parent is about to be (re)attached then there is no point in keeping its dirty lines up to date as we attach children. The parent will get a full layout anyway and we end up having to dirty the lineboxes for every inlines we add - which can get expensive if there are a lot of inlines. BUG=627242 ==========
Description was changed from ========== Skip dirtying lines when attaching children prior to attaching oneself If a parent is about to be (re)attached then there is no point in keeping its dirty lines up to date as we attach children. The parent will get a full layout anyway and we end up having to dirty the lineboxes for every inlines we add - which can get expensive if there are a lot of inlines. BUG=627242 ========== to ========== Skip dirtying lines when attaching children prior to attaching oneself If a parent is about to be (re)attached then there is no point in keeping its dirty lines up to date as we attach children. The parent will get a full layout anyway and we end up having to dirty the lineboxes for every inlines we add - which can get expensive if there are a lot of inlines. BUG=345972 ==========
robhogan@gmail.com changed reviewers: + eae@chromium.org
Looks fine to me but please wait for Elliott to chime in again before landing. LGTM
What's the perf numbers on your test with/without the patch? I think this is probably okay, though it's a bit fragile. It doesn't help the case where the parent is already attached though so it seems like a bit of strange bandaid. ex. var p = document.body.appendChild(document.createElement("p")); for (var i = 0; i < 100; ++i) p.appendChild(document.createElement("span")).textContent = "span"; p.offsetTop; // hits your fast path. for (var i = 0; i < 1000; ++i) p.appendChild(document.createElement("span")).textContent = "span"; p.offsetTop; // misses your fast path.
https://codereview.chromium.org/1550513003/diff/100001/third_party/WebKit/Per... File third_party/WebKit/PerformanceTests/Layout/attach-inlines.html (right): https://codereview.chromium.org/1550513003/diff/100001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Layout/attach-inlines.html:11: var innerHTML = "<span>Text</span>"; innerHTML = "<span>Text</span>".repeat(N); https://codereview.chromium.org/1550513003/diff/100001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Layout/attach-inlines.html:13: innerHTML = innerHTML + "<span>Text</span>"; this is making it exponentially bigger btw, lets just use a real number in repeat() https://codereview.chromium.org/1550513003/diff/100001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Layout/attach-inlines.html:19: span.innerHTML = originalLines; do all mutations inside the test https://codereview.chromium.org/1550513003/diff/100001/third_party/WebKit/Per... third_party/WebKit/PerformanceTests/Layout/attach-inlines.html:25: span.innerHTML += originalLines; This is measuring the performance of serializing tons of spans and then innerHTML'ing tons and tons of them. I'm not sure if that's what you what to benchmark. Using += like this is also very sketchy, I see you reset the test below.
On 2016/07/18 at 22:12:19, esprehn wrote: > What's the perf numbers on your test with/without the patch? > With: [robert@mwenge WebKit (345972-2)]$ ../../out/Release/content_shell --run-layout-test PerformanceTests/Layout/attach-inlines.html #READY Content-Type: text/plain Running 5 times Ignoring warm-up run (6.580072907207815 runs/s) 6.635391853065882 runs/s 6.626246562634591 runs/s 6.63636061983608 runs/s 6.6403707983053675 runs/s 6.628882039044118 runs/s Description: Measures performance of attaching a large number of inlines to an inline. Without: sys 0m1.069s [robert@mwenge WebKit (345972-2)]$ ../../out/Release/content_shell --run-layout-test PerformanceTests/Layout/attach-inlines.html #READY Content-Type: text/plain Running 5 times Ignoring warm-up run (5.790790327063837 runs/s) 5.838291015453954 runs/s 5.834680172006371 runs/s 5.846107077297228 runs/s 5.827064383234367 runs/s 5.820925061410752 runs/s Description: Measures performance of attaching a large number of inlines to an inline. > I think this is probably okay, though it's a bit fragile. It doesn't help the case where the parent is already attached though so it seems like a bit of strange bandaid. > > ex. > > var p = document.body.appendChild(document.createElement("p")); > for (var i = 0; i < 100; ++i) > p.appendChild(document.createElement("span")).textContent = "span"; > p.offsetTop; // hits your fast path. > for (var i = 0; i < 1000; ++i) > p.appendChild(document.createElement("span")).textContent = "span"; > p.offsetTop; // misses your fast path. Your example has the spans getting added a block-layout element, the performance hit is specific to inlines getting attached to an inline. We want to avoid continually searching through the inlines as they get added to the inline container - this doesn't happen for block containers, it just calls firstLineBox() directly: InlineBox* firstBox = inlineContainer ? inlineContainer.firstLineBoxIncludingCulling() : firstLineBox(); If I adapt your example to adding spans to an already attached span, I still get a performance gain. This is because if we bail early from dirtyLinesFromChangedChild() on each new span that we attach we avoid this (because the span we're attaching doesn't have its text added yet): // If we have no first line box, then just bail early. if (!firstBox) { // For an empty inline, go ahead and propagate the check up to our parent, unless the parent // is already dirty. if (container.isInline() && !container.ancestorLineBoxDirty() && canDirtyAncestors) { container.parent().dirtyLinesFromChangedChild(container); container.setAncestorLineBoxDirty(); // Mark the container to avoid dirtying the same lines again across multiple destroy() calls of the same subtree. } return; }
The CQ bit was checked by robhogan@gmail.com to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
On 2016/07/24 at 11:46:03, rhogan wrote: > On 2016/07/18 at 22:12:19, esprehn wrote: > > What's the perf numbers on your test with/without the patch? Got time to take a look? > > > With: > > [robert@mwenge WebKit (345972-2)]$ ../../out/Release/content_shell --run-layout-test PerformanceTests/Layout/attach-inlines.html > #READY > Content-Type: text/plain > Running 5 times > Ignoring warm-up run (6.580072907207815 runs/s) > 6.635391853065882 runs/s > 6.626246562634591 runs/s > 6.63636061983608 runs/s > 6.6403707983053675 runs/s > 6.628882039044118 runs/s > Description: Measures performance of attaching a large number of inlines to an inline. > > > > Without: > sys 0m1.069s > [robert@mwenge WebKit (345972-2)]$ ../../out/Release/content_shell --run-layout-test PerformanceTests/Layout/attach-inlines.html > #READY > Content-Type: text/plain > Running 5 times > Ignoring warm-up run (5.790790327063837 runs/s) > 5.838291015453954 runs/s > 5.834680172006371 runs/s > 5.846107077297228 runs/s > 5.827064383234367 runs/s > 5.820925061410752 runs/s > Description: Measures performance of attaching a large number of inlines to an inline. > > > > I think this is probably okay, though it's a bit fragile. It doesn't help the case where the parent is already attached though so it seems like a bit of strange bandaid. > > > > ex. > > > > var p = document.body.appendChild(document.createElement("p")); > > for (var i = 0; i < 100; ++i) > > p.appendChild(document.createElement("span")).textContent = "span"; > > p.offsetTop; // hits your fast path. > > for (var i = 0; i < 1000; ++i) > > p.appendChild(document.createElement("span")).textContent = "span"; > > p.offsetTop; // misses your fast path. > > Your example has the spans getting added a block-layout element, the performance hit is specific to inlines getting attached to an inline. We want to avoid continually searching through the inlines as they get added to the inline container - this doesn't happen for block containers, it just calls firstLineBox() directly: > > InlineBox* firstBox = inlineContainer ? inlineContainer.firstLineBoxIncludingCulling() : firstLineBox(); > > If I adapt your example to adding spans to an already attached span, I still get a performance gain. This is because if we bail early from dirtyLinesFromChangedChild() on each new span that we attach we avoid this (because the span we're attaching doesn't have its text added yet): > > // If we have no first line box, then just bail early. > if (!firstBox) { > // For an empty inline, go ahead and propagate the check up to our parent, unless the parent > // is already dirty. > if (container.isInline() && !container.ancestorLineBoxDirty() && canDirtyAncestors) { > container.parent().dirtyLinesFromChangedChild(container); > container.setAncestorLineBoxDirty(); // Mark the container to avoid dirtying the same lines again across multiple destroy() calls of the same subtree. > } > return; > }
lgtm
On 2016/07/28 at 17:45:40, esprehn wrote: > lgtm Thanks so much for all your diligence here!
The CQ bit was checked by robhogan@gmail.com
The patchset sent to the CQ was uploaded after l-g-t-m from eae@chromium.org Link to the patchset: https://codereview.chromium.org/1550513003/#ps140001 (title: "Skip dirtying lines when attaching children prior to attaching oneself")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Message was sent while issue was closed.
Committed patchset #8 (id:140001)
Message was sent while issue was closed.
Description was changed from ========== Skip dirtying lines when attaching children prior to attaching oneself If a parent is about to be (re)attached then there is no point in keeping its dirty lines up to date as we attach children. The parent will get a full layout anyway and we end up having to dirty the lineboxes for every inlines we add - which can get expensive if there are a lot of inlines. BUG=345972 ========== to ========== Skip dirtying lines when attaching children prior to attaching oneself If a parent is about to be (re)attached then there is no point in keeping its dirty lines up to date as we attach children. The parent will get a full layout anyway and we end up having to dirty the lineboxes for every inlines we add - which can get expensive if there are a lot of inlines. BUG=345972 Committed: https://crrev.com/dcb4562e8f888588dfe686b1b9d864e39b3dc5cb Cr-Commit-Position: refs/heads/master@{#408601} ==========
Message was sent while issue was closed.
Patchset 8 (id:??) landed as https://crrev.com/dcb4562e8f888588dfe686b1b9d864e39b3dc5cb Cr-Commit-Position: refs/heads/master@{#408601} |