Chromium Code Reviews
Help | Chromium Project | Gerrit Changes | Sign in
(130)

Issue 24350009: Reverse style resolution to avoid N^2 walk when building the render tree (Closed)

Created:
5 years, 11 months ago by leviw_travelin_and_unemployed
Modified:
5 years, 11 months ago
Reviewers:
esprehn, ojan
CC:
blink-reviews, webcomponents-bugzilla_chromium.org, eae+blinkwatch, dglazkov+blink, apavlov+blink_chromium.org, adamk+blink_chromium.org, darktears
Visibility:
Public.

Description

Reverse style resolution to avoid N^2 walk when building the render tree Blink resolves style by walking each element from first child to last, but when we go to insert their renderer, we look for the next renderer to insert before. On the initial style resolve, this means we'll walk the entire DOM tree trying to find the right renderer to insert before leading to an N^2 loop over the DOM on load. This could be fixed by changing the semantics by which we insert renderers (insert after instead of insert before). Instead, here I reverse the order we resolve style. This should ensure that in the common case, we'll find the renderer to insert before immediately. Testing this change uncovered a bug in checkForSiblingStyleChanges whereby we'd invalidate the wrong sibling in certain cases for changed children of elements with directly adjacent sibling selectors. I fixed this and added a simplified test (acid3 caught it with this change, but it's a nightmare to debug). We still attempt to process whitespace text nodes in DOM order by keeping a stack-allocated vector of whitespace children we postpone recalcing style on until the end. If we go past that limit, we process them and continue going. Also removing the didReattach check to force whitespace reattachment. This causes some whitespace layout tests results to change, but doesn't appear to break anything. BUG=288225, 245478 R=esprehn@chromium.org, ojan@chromium.org Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=158839

Patch Set 1 #

Patch Set 2 : Adding mac NeedsRebaseline keyword for acid3 #

Patch Set 3 : Adding more results that needs new baselines from Mac #

Patch Set 4 : Another test that needs updating. #

Patch Set 5 : Another Mac updated expectation... #

Patch Set 6 : And another for Linux... #

Patch Set 7 : fast/events/onload-fires-twice.html also fails on Win #

Patch Set 8 : Yet 2 more tests with blank line changes... #

Patch Set 9 : Previous upload failed... #

Patch Set 10 : Giving delayed processing of whitespace nodes a try on the trybots #

Patch Set 11 : Adding test expectations for 4 tests that reliably change whitespace expectations with this change. #

Patch Set 12 : Updated to ToT. #

Patch Set 13 : Fixing loops in Regions #

Total comments: 2

Patch Set 14 : Abstracting the whitespace list and re-using it in ShadowRoot. #

Patch Set 15 : Fix flakiness by reversing the whitespace node loop and removing the whitespace node reattachment #

Patch Set 16 : Merged to ToT #

Patch Set 17 : Adding WhitespaceChildList.h to core.gypi #

Patch Set 18 : fixing Unsigned/signed on Windows #

Patch Set 19 : Merge to ToT #

Unified diffs Side-by-side diffs Delta from patch set Stats (+350 lines, -271 lines) Patch
M LayoutTests/TestExpectations View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 chunk +33 lines, -0 lines 0 comments Download
M LayoutTests/editing/execCommand/outdent-break-with-style-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +4 lines, -0 lines 0 comments Download
M LayoutTests/editing/selection/focus-crash-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +1 line, -1 line 0 comments Download
M LayoutTests/editing/style/remove-underline-after-paragraph-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +28 lines, -28 lines 0 comments Download
M LayoutTests/editing/style/remove-underline-after-paragraph-in-bold-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +28 lines, -28 lines 0 comments Download
M LayoutTests/editing/style/typing-style-003-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +18 lines, -18 lines 0 comments Download
M LayoutTests/editing/style/underline-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +19 lines, -19 lines 0 comments Download
M LayoutTests/fast/css/getComputedStyle/getComputedStyle-resolved-values-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
A LayoutTests/fast/css/next-sibling-changed.html View 1 chunk +30 lines, -0 lines 0 comments Download
A LayoutTests/fast/css/next-sibling-changed-expected.txt View 1 chunk +10 lines, -0 lines 0 comments Download
M LayoutTests/inspector/elements/edit-dom-actions-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +1 line, -1 line 0 comments Download
M LayoutTests/platform/win/editing/deleting/delete-block-merge-contents-001-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/deleting/delete-block-merge-contents-019-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/deleting/delete-block-merge-contents-020-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/inserting/editable-html-element-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/inserting/editing-empty-divs-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 chunks +0 lines, -2 lines 0 comments Download
M LayoutTests/platform/win/editing/pasteboard/copy-standalone-image-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/pasteboard/paste-match-style-001-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -2 lines 0 comments Download
M LayoutTests/platform/win/editing/selection/4983858-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/selection/drag-to-contenteditable-iframe-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-across-paragraph-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +28 lines, -28 lines 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-across-paragraph-in-bold-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +28 lines, -28 lines 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +20 lines, -20 lines 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-from-stylesheet-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +2 lines, -0 lines 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-in-bold-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +20 lines, -20 lines 0 comments Download
M LayoutTests/platform/win/editing/style/style-boundary-005-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -2 lines 0 comments Download
M LayoutTests/platform/win/fast/body-propagation/background-color/004-xhtml-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/fast/body-propagation/background-image/004-xhtml-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/fast/dynamic/move-node-with-selection-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -3 lines 0 comments Download
M LayoutTests/platform/win/fast/inline/positionedLifetime-expected.txt View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 chunk +0 lines, -1 line 0 comments Download
M Source/core/core.gypi View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 chunk +1 line, -0 lines 0 comments Download
M Source/core/css/SiblingTraversalStrategies.h View 2 chunks +8 lines, -8 lines 0 comments Download
M Source/core/dom/Element.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 3 chunks +29 lines, -21 lines 0 comments Download
A + Source/core/dom/WhitespaceChildList.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 chunks +30 lines, -16 lines 0 comments Download
M Source/core/dom/shadow/ShadowRoot.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 chunks +10 lines, -13 lines 0 comments Download
M Source/core/rendering/RenderRegion.cpp View 1 2 3 4 5 6 7 8 9 10 11 12 2 chunks +2 lines, -2 lines 0 comments Download

Messages

Total messages: 25 (0 generated)
leviw_travelin_and_unemployed
5 years, 11 months ago (2013-09-23 20:49:54 UTC) #1
ojan
lgtm
5 years, 11 months ago (2013-09-23 21:21:58 UTC) #2
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/1
5 years, 11 months ago (2013-09-23 21:22:09 UTC) #3
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/22001
5 years, 11 months ago (2013-09-24 03:06:15 UTC) #4
esprehn
LGTM, amazing work!
5 years, 11 months ago (2013-09-24 03:50:19 UTC) #5
commit-bot: I haz the power
Retried try job too often on win_blink_rel for step(s) webkit_tests http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_rel&number=6973
5 years, 11 months ago (2013-09-24 06:32:22 UTC) #6
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/33012
5 years, 11 months ago (2013-09-24 20:53:51 UTC) #7
commit-bot: I haz the power
Retried try job too often on win_blink_rel for step(s) webkit_tests http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_rel&number=7117
5 years, 11 months ago (2013-09-25 01:32:03 UTC) #8
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/33012
5 years, 11 months ago (2013-09-25 02:49:13 UTC) #9
commit-bot: I haz the power
Retried try job too often on win_blink_rel for step(s) webkit_tests http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_rel&number=7125
5 years, 11 months ago (2013-09-25 03:39:44 UTC) #10
leviw_travelin_and_unemployed
Looking at the Linux layout tests results, it's totally adding flake (the Acid3 test sometimes ...
5 years, 11 months ago (2013-09-25 18:19:02 UTC) #11
leviw_travelin_and_unemployed
FWIW: I can reproduce the flake on Acid3 on my Linux box. I get my ...
5 years, 11 months ago (2013-09-25 23:45:11 UTC) #12
leviw_travelin_and_unemployed
On 2013/09/25 23:45:11, Levi wrote: > FWIW: I can reproduce the flake on Acid3 on ...
5 years, 11 months ago (2013-09-30 22:16:56 UTC) #13
ojan
lgtm, but I'd like Elliott to look over the recalcTextStyle bit before committing this.
5 years, 11 months ago (2013-09-30 22:50:34 UTC) #14
esprehn
You missed the Vector for ShadowRoot :/ LGTM if this works and we can evolve ...
5 years, 11 months ago (2013-09-30 22:52:03 UTC) #15
esprehn
https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/Element.cpp File Source/core/dom/Element.cpp (right): https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/Element.cpp#newcode1573 Source/core/dom/Element.cpp:1573: if (textChild->containsOnlyWhitespace()) { This also makes us do the ...
5 years, 11 months ago (2013-09-30 22:55:33 UTC) #16
leviw_travelin_and_unemployed
On 2013/09/30 22:55:33, esprehn wrote: > https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/Element.cpp > File Source/core/dom/Element.cpp (right): > > https://codereview.chromium.org/24350009/diff/72001/Source/core/dom/Element.cpp#newcode1573 > ...
5 years, 11 months ago (2013-09-30 22:56:58 UTC) #17
esprehn
On 2013/09/30 22:56:58, Levi wrote: > ... > > > > Watch the perf bots ...
5 years, 11 months ago (2013-09-30 23:03:12 UTC) #18
ojan
lgtm The change description could explain why all these expected results change.
5 years, 11 months ago (2013-10-02 00:56:54 UTC) #19
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/89001
5 years, 11 months ago (2013-10-02 17:58:50 UTC) #20
commit-bot: I haz the power
Sorry for I got bad news for ya. Compile failed with a clobber build on ...
5 years, 11 months ago (2013-10-02 18:47:57 UTC) #21
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/105001
5 years, 11 months ago (2013-10-02 20:41:55 UTC) #22
commit-bot: I haz the power
Retried try job too often on win_blink_rel for step(s) webkit_lint, webkit_python_tests, webkit_tests http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_blink_rel&number=8328
5 years, 11 months ago (2013-10-02 23:16:14 UTC) #23
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/leviw@chromium.org/24350009/119001
5 years, 11 months ago (2013-10-03 18:24:11 UTC) #24
leviw_travelin_and_unemployed
5 years, 11 months ago (2013-10-03 20:33:58 UTC) #25
Message was sent while issue was closed.
Committed patchset #19 manually as r158839 (presubmit successful).

Powered by Google App Engine
This is Rietveld 408576698