commit 786b1994bf6f43f2ff038894a1891435f2de22b9
author Koji Ishii <kojii@chromium.org> Thu Oct 11 14:22:14 2018
committer Commit Bot <commit-bot@chromium.org> Thu Oct 11 14:22:14 2018
tree 3f90e9675129b7ed9ca904b83029b419d95cd868
parent 452711acab89b10dcfbd062c1b654ec0330f570b

Reland "Improve performance of PreviousBreakOpportunity"

This reverts commit 209909630cf94d4568bc62157053bae5791908eb.

Reason for revert: The revert did not fix crbug.com/883963.
Requested to re-run bisect.

Original change's description:
> Revert "Improve performance of PreviousBreakOpportunity"
> 
> This reverts commit 99d504fd35a7e07c4cf16bbbe1464044e2195b4e.
> 
> Reason for revert:
> 
> crbug.com/883963 bisected to this CL. I'm not sure how this
> affects print preview, reverting to see the effect.
> 
> This revert may affect LayoutNG performance, but should not
> affect the currently shipping line breaker.
> 
> Original change's description:
> > Improve performance of PreviousBreakOpportunity
> >
> > In the current layout engine, PreviousBreakOpportunity is used
> > only when mid-word break (break-all or break-word), but it is
> > much more heavily used in LayoutNG.
> >
> > LazyLineBreakIterator is designed for forward only.
> > PreviousBreakOpportunity is implemented by repeatedly calling
> > NextBreakablePosition, but since NextBreakablePosition look
> > for the next break opportunity until the end of the string,
> > when a very long word without break opportunity is given,
> > PreviousBreakOpportunity is O(n!).
> >
> > This patch changes it to O(n) by limiting the end position
> > NextBreakablePosition can look for.
> >
> > blink/perf_tests/layout/word-break-break-word.html consumes
> > 78% of the total time in LayoutNG. The average run is:
> >   Current engine:    469ms
> >   LayoutNG:       26,644ms
> >   This patch:      2,250ms
> >
> > It's still 4-5 times slower, more improvements will be in
> > following patches.
> >
> > Bug: 636993
> > Cq-Include-Trybots: master.tryserver.chromium.linux:linux_layout_tests_layout_ng
> > Change-Id: I814e2c45c8030aa682c7f5e3a3b785b3c0733c84
> > Reviewed-on: https://chromium-review.googlesource.com/1095894
> > Commit-Queue: Koji Ishii <kojii@chromium.org>
> > Reviewed-by: Emil A Eklund <eae@chromium.org>
> > Cr-Commit-Position: refs/heads/master@{#567133}
> 
> TBR=eae@chromium.org,kojii@chromium.org
> 
> Bug: 636993, 883963
> Change-Id: I2c453a011208b014e342d7b44646eb90b5b7bbd2
> Reviewed-on: https://chromium-review.googlesource.com/c/1270396
> Commit-Queue: Koji Ishii <kojii@chromium.org>
> Reviewed-by: Koji Ishii <kojii@chromium.org>
> Cr-Commit-Position: refs/heads/master@{#597876}

TBR=eae@chromium.org,kojii@chromium.org

# Not skipping CQ checks because original CL landed > 1 day ago.

Bug: 636993, 883963
Change-Id: I8e9881deca736c5b574dc287d04f9c2fffe76680
Reviewed-on: https://chromium-review.googlesource.com/c/1275985
Reviewed-by: Koji Ishii <kojii@chromium.org>
Commit-Queue: Koji Ishii <kojii@chromium.org>
Cr-Commit-Position: refs/heads/master@{#598754}