commit 99d504fd35a7e07c4cf16bbbe1464044e2195b4e
author Koji Ishii <kojii@chromium.org> Thu Jun 14 04:26:37 2018
committer Commit Bot <commit-bot@chromium.org> Thu Jun 14 04:26:37 2018
tree c684eea19e8ded68c65faacc41e1b3fa747df75e
parent 8c4bab31b7a092870355565d1255009229ba3f20

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}