All graphs for this bug:
  https://chromeperf.appspot.com/group_report?bug_id=700093

Original alerts at time of bug-filing:
  https://chromeperf.appspot.com/group_report?keys=agxzfmNocm9tZXBlcmZyFAsSB0Fub21hbHkYgIDg1IX4pgsM,agxzfmNocm9tZXBlcmZyFAsSB0Fub21hbHkYgIDglJX68QsM


Bot(s) for this bug's original alert(s):

chromium-rel-mac11-air
chromium-rel-mac12

Started bisect job https://chromeperf.appspot.com/buildbucket_job_status/8985573939886954416

=== BISECT JOB RESULTS ===
Perf regression found but unable to narrow commit range

Build failures prevented the bisect from narrowing the range further.


Bisect Details
  Configuration: mac_air_perf_bisect
  Benchmark    : blink_perf.dom
  Metric       : long-sibling-list/long-sibling-list
  Change       : 1.99% | 183.497968257 -> 179.847604458

Suspected Commit Range
  3 commits in range
  https://chromium.googlesource.com/chromium/src/+log/04af4448e4833d6d1e9e06059ab9947a4d936111..06e52a1425e72fe847d8a33a975bc9fdbe780ee6


Revision             Result                  N
chromium@454726      183.498 +- 5.04274      9        good
chromium@454802      181.405 +- 4.56831      9        good
chromium@454833      180.897 +- 2.58908      14       good
chromium@454840      180.703 +- 10.3855      21       good
chromium@454851      180.266 +- 8.8993       14       good
chromium@454852      ---                     ---      build failure
chromium@454853      ---                     ---      build failure
chromium@454854      178.462 +- 8.83542      14       bad
chromium@454875      178.889 +- 6.16191      9        bad
chromium@454990      179.848 +- 4.01882      6        bad

To Run This Test
  src/tools/perf/run_benchmark -v --browser=release --output-format=chartjson --upload-results --pageset-repeat=1 --also-run-disabled-tests blink_perf.dom

Debug Info
  https://chromeperf.appspot.com/buildbucket_job_status/8985573939886954416

Is this bisect wrong?
  https://chromeperf.appspot.com/bad_bisect?try_job_id=6630675513344000


| O O | Visit http://www.chromium.org/developers/speed-infra/perf-bug-faq
|  X  | for more information addressing perf regression bugs. For feedback,
| / \ | file a bug with component Speed>Bisection.  Thank you!

Started bisect job https://chromeperf.appspot.com/buildbucket_job_status/8985504326522087104

=== Auto-CCing suspected CL author nainar@chromium.org ===

Hi nainar@chromium.org, the bisect results pointed to your CL, please take a look at the
results.


=== BISECT JOB RESULTS ===
Perf regression found with culprit

Suspected Commit
  Author : nainar
  Commit : f4c976fc1f4578b0c75ba304553ef2ff6134f551
  Date   : Mon Mar 06 04:05:17 2017
  Subject: Call Element::rebuildLayoutTree from Document::updateStyle directly

Bisect Details
  Configuration: mac_10_12_perf_bisect
  Benchmark    : blink_perf.dom
  Metric       : long-sibling-list/long-sibling-list
  Change       : 11.07% | 168.172254507 -> 149.561698151

Revision             Result                  N
chromium@454726      168.172 +- 1.39564      6      good
chromium@454790      167.464 +- 6.90583      6      good
chromium@454821      167.438 +- 4.26961      6      good
chromium@454823      167.785 +- 2.40461      6      good
chromium@454824      149.488 +- 3.27063      6      bad       <--
chromium@454826      148.876 +- 1.80233      6      bad
chromium@454831      148.785 +- 3.15521      6      bad
chromium@454840      149.668 +- 1.49815      5      bad
chromium@454852      150.072 +- 4.60957      6      bad
chromium@454977      149.562 +- 6.60612      6      bad

To Run This Test
  src/tools/perf/run_benchmark -v --browser=release --output-format=chartjson --upload-results --pageset-repeat=1 --also-run-disabled-tests blink_perf.dom

Debug Info
  https://chromeperf.appspot.com/buildbucket_job_status/8985504326522087104

Is this bisect wrong?
  https://chromeperf.appspot.com/bad_bisect?try_job_id=4727385989054464


| O O | Visit http://www.chromium.org/developers/speed-infra/perf-bug-faq
|  X  | for more information addressing perf regression bugs. For feedback,
| / \ | file a bug with component Speed>Bisection.  Thank you!

https://cs.chromium.org/chromium/src/third_party/WebKit/PerformanceTests/DOM/long-sibling-list.html

This benchmark is doing:

#text(stuff) <a></a> #text(whitespace)

alternated back and forth 300 times.

A regression like this smells like we broke the n^2 protection somewhere in there? Did rune@'s recent patch fix it?

The dashboard seems to think not. https://chromeperf.appspot.com/group_report?keys=agxzfmNocm9tZXBlcmZyFAsSB0Fub21hbHkYgIDg1IX4pgsM,agxzfmNocm9tZXBlcmZyFAsSB0Fub21hbHkYgIDglJX68QsM

Going to take a stab at trying to profile this.
Also stab in the dark. Similar to the way we retain needsStyleRecalc information in Element::recalcOwnStyle. There may be need to retain that information in Text::recalcTextStyle? 
In Text::rebuildLayoutTree we enter Text::reattachLayoutTreeIfNeeded() via Node::reattachWhitespaceSiblingsIfNeeded() where again we have a guard on detachLayoutTree(). 

Looking at the commits in the graph rune@'s change is in there but the graph didn't move. You can also clearly see the revert of nainar@'s patch in there as the graph recovers and then goes down again when it was landed a second time.

Probably need to look at it in a profiler?

In the midst of profiling will post results here once I have something. 

We just spend the day looking at this and staring into the profiler, almost all of the time is spent inside the call to LayoutTreeBuilderTraversal::previousSiblingLayoutObject calling previousSibling() which is n^2 (limited to 50). That shouldn't have changed with the patch since we're still attaching everyone in the same order. There's also about 9% of realcStyle going into managing the nonAttachedStyle map, but we've been adding things to that map for a while now before this patch landed.

This also only seems to reproduce on the Mac bots, we can't see the same regression on Android or Windows.

rune@ Got any ideas? Perhaps nainar@ and I are missing something?

Also I'd like to see the design doc for how where we're going with the display: contents stuff, I worry we're making the complexity around style computation worse, when instead we should add a second O(n) pass over all of the kids inside Element::rebuildLayoutTree() that just processes all the whitespace and instead make ContainerNode::rebuildChildrenLayoutTrees skip whitespace nodes in general.

So what this is really doing is:

#whitespace <a> #text </a>

x300

So this would only be an exponential blowup if we broke the sibling limit, I guess (which is unlikely of that CL). I think it would be easy to check if previousSiblingLayoutObject traverses the same amount of nodes before and after that patch.

If that wasn't the culprit, that regression might just be from splitting the traversal in two, which is what that patch is doing? And if so, I don't think much can be done about it, this seems like the worst case of that split. Maybe I'm missing something though.

Regarding whitespace and display: contents/shadow DOM stuff, I need to check what the status of it is now. My idea the first time I looked at this stuff was indeed complexity-introducing.

Now, with this split, perhaps we can just keep the children traversal in styling working using the light tree, and the rebuildChildrenLayoutTree should just operate using LayoutTreeBuilderTraversal. I need to see the feasibility of it, but sounds like it would keep the complexity down while not getting a perf hit? In any case, this issue isn't the place to discuss it, I'll mail to style-dev@.

Without looking at any perf data, I'm guessing the two-pass traversal Emilio mentions above. Unless you have evidence there's a polynomial change like introducing an n^2 in there if you change the node count from 300.

Ran the test locally with content_shell.

Translated from runs/s to ms per run:

300 nodes: 5.8ms
600 nodes: 9.8ms
900 nodes: 13.5ms
1200 nodes: 18.9ms

which looks linear.

According to a callgrind run I have, reattachLayoutTree() and reattachWhitespaceSiblingsIfNeeded() accounts for nearly 92% of rebuildLayoutTree(), which means there is 8% overhead in traversal and bit clearing. rebuildLayoutTree() is in turn 82% of updateStyle().

Unrelated to this regression, I believe, out of the 100% of rebuildLayoutTree(), 38.33% is spent in textLayoutObjectIsNeeded(). That's crazy, and it seems we are walking unnecessary many siblings. I'm looking at the details in the context of  issue 399816 .

esprehn@ and I looked at the number of times each function executes and the numbers made sense to us. Reducing the number of appended nodes to 2 in long-sibling-list.html, here is the output:
( Element::attachLayoutTree HTML
  ( Element::attachLayoutTree HEAD )
  ( Element::attachLayoutTree BODY )
)
( Element::detachLayoutTree 'HEAD' )
( Element::detachLayoutTree 'BODY' )
( Element::detachLayoutTree 'HTML' )
( Element::attachLayoutTree HTML
  ( Element::attachLayoutTree HEAD )
  ( Element::attachLayoutTree BODY
    ( Element::attachLayoutTree DIV )
    ( Text::attachLayoutTree '
' )
    ( Element::attachLayoutTree SCRIPT
      ( Text::attachLayoutTree '
const num_words = 2;
document.documentElement.offsetTop;
for (var i = 0; i < num_words; i++) {
  var a = document.createElement('a');
  a.appendChild(document.createTextNode('' + i));
  container.appendChild(a);
  container.appendChild(document.createTextNode(' '));
}
document.documentElement.offsetHeight;
' )
    )
  )
)
( Text::attachLayoutTree ' ' )
( Element::attachLayoutTree A
  ( Text::attachLayoutTree '1'
    ( Text::createTextLayoutObject )
  )
)
( Text::reattachLayoutTreeIfNeeded ' '
  ( Text::detachLayoutTree ' ' )
  ( Text::createTextLayoutObject )
)
( Text::attachLayoutTree ' ' )
( Element::attachLayoutTree A
  ( Text::attachLayoutTree '0'
    ( Text::createTextLayoutObject )
  )
)
( Text::reattachLayoutTreeIfNeeded ' '
  ( Text::detachLayoutTree ' ' )
  ( Text::createTextLayoutObject )
)
( Text::attachLayoutTree '
' )

We tto noticed what rune@ said about an inordinately large time of rebuildLayoutTree() being spent in textLayoutObjectIsNeeded().

This is a style benchmark.

Please note that this regression isn't a straight forward fix but will instead one that will be solved by large architecture level changes. The failing testcase here does so because we have introduced a HashMap lookup inside stylesharing which was initially a free operation. Reverting my patch would fix this but however given that this is a toy case unless we see realworld concerns with regards to this perf regression we will retain my patch in the codebase. Also rune has done some great work on top of my patch which would also then require a revert. 

Hence removing the Stylimations label as that is meant to track regressions that need to be fixed. 

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

commit 95862a52c7bc1a5846259619243289805d095b70
Author: nainar <nainar@chromium.org>
Date: Thu Apr 27 01:44:18 2017

Store nonAttachedStyle on NodeLayoutData instead of on HashMap in Document.

This patch stores the ComputedStyle to be passed between recalcStyle
and rebuildLayoutTree on NodeLayoutData instead of storing it on the
HashMap on Document.

This potentially fixes the perf regression in  crbug.com/700093  as it
removes the HashMap lookup in SharedStyleFinder and making it a free
operation again.

BUG= 595137 ,  700093 

Review-Url: https://codereview.chromium.org/2821193003
Cr-Commit-Position: refs/heads/master@{#467542}

[modify] https://crrev.com/95862a52c7bc1a5846259619243289805d095b70/third_party/WebKit/Source/core/css/resolver/SharedStyleFinder.cpp
[modify] https://crrev.com/95862a52c7bc1a5846259619243289805d095b70/third_party/WebKit/Source/core/dom/Document.cpp
[modify] https://crrev.com/95862a52c7bc1a5846259619243289805d095b70/third_party/WebKit/Source/core/dom/Document.h
[modify] https://crrev.com/95862a52c7bc1a5846259619243289805d095b70/third_party/WebKit/Source/core/dom/Element.cpp
[modify] https://crrev.com/95862a52c7bc1a5846259619243289805d095b70/third_party/WebKit/Source/core/dom/Node.cpp
[modify] https://crrev.com/95862a52c7bc1a5846259619243289805d095b70/third_party/WebKit/Source/core/dom/Node.h

Since we're killing StyleSharing marking this as WontFix - please change if needed.