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}diff --git a/third_party/WebKit/LayoutTests/flag-specific/enable-blink-features=LayoutNG/fast/text/midword-break-before-surrogate-pair-expected.png b/third_party/WebKit/LayoutTests/flag-specific/enable-blink-features=LayoutNG/fast/text/midword-break-before-surrogate-pair-expected.png
index 12edf86..5a5eaaa5 100644
--- a/third_party/WebKit/LayoutTests/flag-specific/enable-blink-features=LayoutNG/fast/text/midword-break-before-surrogate-pair-expected.png
+++ b/third_party/WebKit/LayoutTests/flag-specific/enable-blink-features=LayoutNG/fast/text/midword-break-before-surrogate-pair-expected.png
Binary files differ
diff --git a/third_party/blink/renderer/platform/text/text_break_iterator.cc b/third_party/blink/renderer/platform/text/text_break_iterator.cc
index e39e8df0..d9cd41f 100644
--- a/third_party/blink/renderer/platform/text/text_break_iterator.cc
+++ b/third_party/blink/renderer/platform/text/text_break_iterator.cc
@@ -298,8 +298,8 @@
BreakSpaceType break_space>
inline int LazyLineBreakIterator::NextBreakablePosition(
int pos,
- const CharacterType* str,
- int len) const {
+ const CharacterType* str) const {
+ int len = static_cast<int>(string_.length());
DCHECK_GE(pos, 0);
DCHECK_GE(static_cast<unsigned>(pos), start_offset_);
int next_break = -1;
@@ -379,35 +379,30 @@
template <typename CharacterType, LineBreakType lineBreakType>
inline int LazyLineBreakIterator::NextBreakablePosition(
int pos,
- const CharacterType* str,
- int len) const {
+ const CharacterType* str) const {
switch (break_space_) {
case BreakSpaceType::kBeforeEverySpace:
return NextBreakablePosition<CharacterType, lineBreakType,
- BreakSpaceType::kBeforeEverySpace>(pos, str,
- len);
+ BreakSpaceType::kBeforeEverySpace>(pos, str);
case BreakSpaceType::kBeforeSpaceRun:
return NextBreakablePosition<CharacterType, lineBreakType,
- BreakSpaceType::kBeforeSpaceRun>(pos, str,
- len);
+ BreakSpaceType::kBeforeSpaceRun>(pos, str);
}
NOTREACHED();
return NextBreakablePosition<CharacterType, lineBreakType,
- BreakSpaceType::kBeforeEverySpace>(pos, str,
- len);
+ BreakSpaceType::kBeforeEverySpace>(pos, str);
}
template <LineBreakType lineBreakType>
-inline int LazyLineBreakIterator::NextBreakablePosition(int pos,
- int len) const {
+inline int LazyLineBreakIterator::NextBreakablePosition(int pos) const {
if (UNLIKELY(string_.IsNull()))
return 0;
if (string_.Is8Bit()) {
- return NextBreakablePosition<LChar, lineBreakType>(
- pos, string_.Characters8(), len);
+ return NextBreakablePosition<LChar, lineBreakType>(pos,
+ string_.Characters8());
}
- return NextBreakablePosition<UChar, lineBreakType>(
- pos, string_.Characters16(), len);
+ return NextBreakablePosition<UChar, lineBreakType>(pos,
+ string_.Characters16());
}
int LazyLineBreakIterator::NextBreakablePositionBreakCharacter(int pos) const {
@@ -420,16 +415,16 @@
return next != kTextBreakDone ? next + start_offset_ : string_.length();
}
-int LazyLineBreakIterator::NextBreakablePosition(int pos,
- LineBreakType line_break_type,
- int len) const {
+int LazyLineBreakIterator::NextBreakablePosition(
+ int pos,
+ LineBreakType line_break_type) const {
switch (line_break_type) {
case LineBreakType::kNormal:
- return NextBreakablePosition<LineBreakType::kNormal>(pos, len);
+ return NextBreakablePosition<LineBreakType::kNormal>(pos);
case LineBreakType::kBreakAll:
- return NextBreakablePosition<LineBreakType::kBreakAll>(pos, len);
+ return NextBreakablePosition<LineBreakType::kBreakAll>(pos);
case LineBreakType::kKeepAll:
- return NextBreakablePosition<LineBreakType::kKeepAll>(pos, len);
+ return NextBreakablePosition<LineBreakType::kKeepAll>(pos);
case LineBreakType::kBreakCharacter:
return NextBreakablePositionBreakCharacter(pos);
}
@@ -437,15 +432,9 @@
return NextBreakablePosition(pos, LineBreakType::kNormal);
}
-int LazyLineBreakIterator::NextBreakablePosition(
- int pos,
- LineBreakType line_break_type) const {
- return NextBreakablePosition(pos, line_break_type,
- static_cast<int>(string_.length()));
-}
-
unsigned LazyLineBreakIterator::NextBreakOpportunity(unsigned offset) const {
- int next_break = NextBreakablePosition(offset, break_type_);
+ int next_break = -1;
+ IsBreakable(offset, next_break);
DCHECK_GE(next_break, 0);
return next_break;
}
@@ -453,7 +442,10 @@
unsigned LazyLineBreakIterator::NextBreakOpportunity(unsigned offset,
unsigned len) const {
DCHECK_LE(len, string_.length());
- int next_break = NextBreakablePosition(offset, break_type_, len);
+ // TODO(kojii): |len| is not utilized for perf benefit as
+ // |NextBreakablePosition| does not accept it due to a revert in
+ // crbug.com/883963.
+ int next_break = NextBreakablePosition(offset, break_type_);
DCHECK_GE(next_break, 0);
return next_break;
}
@@ -461,20 +453,9 @@
unsigned LazyLineBreakIterator::PreviousBreakOpportunity(unsigned offset,
unsigned min) const {
unsigned pos = std::min(offset, string_.length());
- // +2 to ensure at least one code point is included.
- unsigned end = std::min(pos + 2, string_.length());
- while (pos > min) {
- int next_break = NextBreakablePosition(pos, break_type_, end);
- DCHECK_GE(next_break, 0);
- if (static_cast<unsigned>(next_break) == pos)
- return next_break;
-
- // There's no break opportunities at |pos| or after.
- end = pos;
- if (string_.Is8Bit())
- --pos;
- else
- U16_BACK_1(string_.Characters16(), 0, pos);
+ for (; pos > min; pos--) {
+ if (IsBreakable(pos))
+ return pos;
}
return min;
}
diff --git a/third_party/blink/renderer/platform/text/text_break_iterator.h b/third_party/blink/renderer/platform/text/text_break_iterator.h
index f7f02eb..e2ce60c0 100644
--- a/third_party/blink/renderer/platform/text/text_break_iterator.h
+++ b/third_party/blink/renderer/platform/text/text_break_iterator.h
@@ -242,8 +242,7 @@
// Limit length to pos + 1.
// TODO(layout-dev): We should probably try to break out an actual
// IsBreakable method from NextBreakablePosition and get rid of this hack.
- int len = std::min(pos + 1, static_cast<int>(string_.length()));
- int next_breakable = NextBreakablePosition(pos, break_type_, len);
+ int next_breakable = NextBreakablePosition(pos, break_type_);
return pos == next_breakable;
}
@@ -306,13 +305,12 @@
}
template <typename CharacterType, LineBreakType, BreakSpaceType>
- int NextBreakablePosition(int pos, const CharacterType* str, int len) const;
+ int NextBreakablePosition(int pos, const CharacterType* str) const;
template <typename CharacterType, LineBreakType>
- int NextBreakablePosition(int pos, const CharacterType* str, int len) const;
+ int NextBreakablePosition(int pos, const CharacterType* str) const;
template <LineBreakType>
- int NextBreakablePosition(int pos, int len) const;
+ int NextBreakablePosition(int pos) const;
int NextBreakablePositionBreakCharacter(int pos) const;
- int NextBreakablePosition(int pos, LineBreakType, int len) const;
int NextBreakablePosition(int pos, LineBreakType) const;
static const unsigned kPriorContextCapacity = 2;
