I talked with Chris and he suggested that we could add a special-case in CompositingInputsUpdater::UpdateRecursive for the root layer to avoid work.

Tien-Ren, this is a pretty targeted optimization. Can you make fixed-and-many-layers-scroll fast with RLS enabled?

Attaching profiles showing the top self-weight functions with and without RLS.

Deleted: rls_profile.png 1.1 MB

	rls_profile.png 1.1 MB View Download

Deleted: norls_profile.png 1.1 MB

	norls_profile.png 1.1 MB View Download

 Issue 809499  has been merged into this issue.

I recently found that linux perf bot is not updating so the graph in the original report can be deceptive. Lets use the following graph for tracking this regression instead:
https://chromeperf.appspot.com/report?sid=50dcb9e270a687c25436a725ef9d5fadc506f2d3bb19dbb1df62fd5fb3abc726

Update: Initially I thought that the regression was due to an optimization to skip scroll parent and clip parent computation became no longer effective with RLS enabled. Turns out in this particular benchmark the layer tree is very flat, the O(d) algorithm consists only a very small fraction of the run time.

I added more detailed instrumentation using rdtsc counter, the actual bottleneck is this line: https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/paint/compositing/CompositingInputsUpdater.cpp?rcl=72c62e41665343965502d9a4d1d6829f7df0b0f0&l=197

I haven't yet figured out exactly why that line runs ~75% slower with RLS than without. :/

NVM. I forgot I usually build with DCHECK. The non-DCHECK build has a very different profile. There is still a small difference in LayoutGeometryMap::AbsoluteRect(), but the source of regression indeed comes from clip parent and scroll parent computation.

I re-ran the benchmark with non-DCHECK builds in 6 configuration (No-RLS, RLS)X(Vanilla, O(1) scroll parent, O(1) scroll parent + O(1) clip parent) and look at the average time for CompositingInputsUpdater::update:

               No-RLS     RLS
Vanilla          21ms    28ms
1 patch        17.5ms  21.5ms
both patches   19.5ms  19.5ms

I think we should proceed to apply both patches.

Nice!

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/06f244ec11ee17699c98c7c59bf4bba664eb14cb

commit 06f244ec11ee17699c98c7c59bf4bba664eb14cb
Author: Tien-Ren Chen <trchen@chromium.org>
Date: Fri Mar 09 05:35:41 2018

[Blink] Avoid O(d) lookup during scroll parent computation

This CL changes CompositingInputsUpdater to keep track of scrolling
container for different type of positioned descendants, so we won't need
to walk up ancestor chain to look for them. This is similar to the
technique used by PrePaintTreeWalk.

No behavior change is expected.

BUG= 818768 

Cq-Include-Trybots: master.tryserver.blink:linux_trusty_blink_rel;master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2
Change-Id: I2409dd91e5b2903e348bdebca7f6ac2f1544ea94
Reviewed-on: https://chromium-review.googlesource.com/952540
Commit-Queue: Tien-Ren Chen <trchen@chromium.org>
Reviewed-by: Philip Rogers <pdr@chromium.org>
Cr-Commit-Position: refs/heads/master@{#542041}
[modify] https://crrev.com/06f244ec11ee17699c98c7c59bf4bba664eb14cb/third_party/WebKit/Source/core/paint/compositing/CompositingInputsUpdater.cpp
[modify] https://crrev.com/06f244ec11ee17699c98c7c59bf4bba664eb14cb/third_party/WebKit/Source/core/paint/compositing/CompositingInputsUpdater.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/ffc26d979f5e1b236278ab23f5f9e9c32a0ae9bb

commit ffc26d979f5e1b236278ab23f5f9e9c32a0ae9bb
Author: Tien-Ren Chen <trchen@chromium.org>
Date: Mon Mar 12 21:32:02 2018

[Blink] Avoid O(n) lookup during clip parent computation

Similar to the previous alike-titled CL "[Blink] Avoid O(n) lookup during
scroll parent computation", this CL changes CompositingInputsUpdater to
keep track of clip chain information in recursion context for different
type of positioned descendants to achieve O(1) lookup.

And conveniently workaround  crbug.com/817175 

BUG= 818768 , 817175 

Cq-Include-Trybots: master.tryserver.blink:linux_trusty_blink_rel;master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2
Change-Id: Ib8bb76eb219a7056d6488484cc8439d44e7d7aac
Reviewed-on: https://chromium-review.googlesource.com/956503
Commit-Queue: Tien-Ren Chen <trchen@chromium.org>
Reviewed-by: Philip Rogers <pdr@chromium.org>
Cr-Commit-Position: refs/heads/master@{#542605}
[modify] https://crrev.com/ffc26d979f5e1b236278ab23f5f9e9c32a0ae9bb/third_party/WebKit/LayoutTests/FlagExpectations/enable-slimming-paint-v2
[modify] https://crrev.com/ffc26d979f5e1b236278ab23f5f9e9c32a0ae9bb/third_party/WebKit/LayoutTests/TestExpectations
[add] https://crrev.com/ffc26d979f5e1b236278ab23f5f9e9c32a0ae9bb/third_party/WebKit/LayoutTests/compositing/overflow/clip-escaping-reverse-order-should-not-crash-expected.html
[add] https://crrev.com/ffc26d979f5e1b236278ab23f5f9e9c32a0ae9bb/third_party/WebKit/LayoutTests/compositing/overflow/clip-escaping-reverse-order-should-not-crash.html
[modify] https://crrev.com/ffc26d979f5e1b236278ab23f5f9e9c32a0ae9bb/third_party/WebKit/Source/core/paint/compositing/CompositingInputsUpdater.cpp
[modify] https://crrev.com/ffc26d979f5e1b236278ab23f5f9e9c32a0ae9bb/third_party/WebKit/Source/core/paint/compositing/CompositingInputsUpdater.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/0d2f4351ca12d64119d1aed52faf538a852a12c0

commit 0d2f4351ca12d64119d1aed52faf538a852a12c0
Author: Tien-Ren Chen <trchen@chromium.org>
Date: Tue Mar 13 00:28:29 2018

[Blink] Make PaintLayer::AncestorDependentCompositingInputs in-place

Before this CL it was owned by PaintLayer through a std::unique_ptr.
This is probably because it was a rare data back in the age when we had
non-composited mode. Now every PaintLayer always have it.

BUG= 818768 

Cq-Include-Trybots: master.tryserver.blink:linux_trusty_blink_rel;master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2
Change-Id: Ice8612a3cbe4a3da28e81f3d17f80cf5574ce17a
Reviewed-on: https://chromium-review.googlesource.com/959557
Commit-Queue: Tien-Ren Chen <trchen@chromium.org>
Reviewed-by: Philip Rogers <pdr@chromium.org>
Cr-Commit-Position: refs/heads/master@{#542668}
[modify] https://crrev.com/0d2f4351ca12d64119d1aed52faf538a852a12c0/third_party/WebKit/Source/core/paint/PaintLayer.cpp
[modify] https://crrev.com/0d2f4351ca12d64119d1aed52faf538a852a12c0/third_party/WebKit/Source/core/paint/PaintLayer.h

We have 3 CLs for this bug:
r542041 [Blink] Avoid O(d) lookup during scroll parent computation
r542605 [Blink] Avoid O(n) lookup during clip parent computation
r542668 [Blink] Make PaintLayer::AncestorDependentCompositingInputs in-place

The first CL triggered a squashing / overlap testing related bug, which I'm still investigating. Definitely not ready for merge right now.

The second CL haven't got a bug report to it so far, but nevertheless it is much more complex and I'd rather bake a few days to get comfortable with it. That said, eventually we need to merge it because it also fixes a crash bug.

At this moment we should merge only the last one to M66. The last CL only moves data layout around and contains no logic change whatsoever. Also it is expected to regain about half of the performance we lost.

What are the impacted OS's? Can you please mark them in bug?

Your change meets the bar and is auto-approved for M66. Please go ahead and merge the CL to branch 3359 manually. Please contact milestone owner if you have questions.
Owners: cmasso@(Android), cmasso@(iOS), josafat@(ChromeOS), abdulsyed@(Desktop)

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/47392260d9938b9b767aaee6fedf01910ca55641

commit 47392260d9938b9b767aaee6fedf01910ca55641
Author: Tien-Ren Chen <trchen@chromium.org>
Date: Fri Mar 16 00:24:28 2018

[Blink] Make PaintLayer::AncestorDependentCompositingInputs in-place

Before this CL it was owned by PaintLayer through a std::unique_ptr.
This is probably because it was a rare data back in the age when we had
non-composited mode. Now every PaintLayer always have it.

BUG= 818768 
TBR=trchen@chromium.org

(cherry picked from commit 0d2f4351ca12d64119d1aed52faf538a852a12c0)

Cq-Include-Trybots: master.tryserver.blink:linux_trusty_blink_rel;master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2
Change-Id: Ice8612a3cbe4a3da28e81f3d17f80cf5574ce17a
Reviewed-on: https://chromium-review.googlesource.com/959557
Commit-Queue: Tien-Ren Chen <trchen@chromium.org>
Reviewed-by: Philip Rogers <pdr@chromium.org>
Cr-Original-Commit-Position: refs/heads/master@{#542668}
Reviewed-on: https://chromium-review.googlesource.com/965015
Reviewed-by: Tien-Ren Chen <trchen@chromium.org>
Cr-Commit-Position: refs/branch-heads/3359@{#279}
Cr-Branched-From: 66afc5e5d10127546cc4b98b9117aff588b5e66b-refs/heads/master@{#540276}
[modify] https://crrev.com/47392260d9938b9b767aaee6fedf01910ca55641/third_party/WebKit/Source/core/paint/PaintLayer.cpp
[modify] https://crrev.com/47392260d9938b9b767aaee6fedf01910ca55641/third_party/WebKit/Source/core/paint/PaintLayer.h

I expect these micro optimization covered the regression we had. Closing bug for now.

For clarification, in M66 we may still see some regression, while in M67 it should be faster in all cases.

 Issue 827827  has been merged into this issue.