Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

When there are multiple BidiRun in a line (multiple inline elements,
whitespace collapsing, or RTL,) setLogicalWidthForTextRun has
O(#BidiRun * #WordMeasurement), resulting similar characteristics as
O(n!) for the line length.

This patch fixes this for LTR.

For RTL, we could improve up to log2(N) by using binary search, or
better by using fast index for LineLayoutText for multiple elements
case. It was once tried but removed due to its complexity, we can do it
if they came up as real cases.

Following performance tests are now 10-20x faster. The amount of text
for these tests were increased by 12x, matching to
long-line-nowrap.html.

PerformanceTests/Layout/long-line-nowrap-collapse.html
PerformanceTests/Layout/long-line-nowrap-spans-collapse.html

BUG=583711, 642345
Committed: https://crrev.com/ccd49c63f329c36da86b128b30e277d72f5bc76d
Cr-Commit-Position: refs/heads/master@{#415647}

[kojii, 2016-08-27 18:43:58]

The CQ bit was checked by kojii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-27 18:44:09]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-27 18:56:20]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-27 18:56:21]

Dry run: Try jobs failed on following builders:
  cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)

[kojii, 2016-08-28 05:13:12]

The CQ bit was checked by kojii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-28 05:13:17]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-28 06:09:34]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-28 06:09:35]

Dry run: Try jobs failed on following builders:
  cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)

[kojii, 2016-08-29 01:05:44]

The CQ bit was checked by kojii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-29 01:05:57]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-29 01:45:09]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-29 01:45:10]

Dry run: Try jobs failed on following builders:
  linux_chromium_chromeos_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[kojii, 2016-08-30 06:59:40]

The CQ bit was checked by kojii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-30 06:59:55]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-30 08:20:50]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-30 08:20:51]

Dry run: Try jobs failed on following builders:
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[kojii, 2016-08-31 09:02:27]

The CQ bit was checked by kojii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-31 09:02:49]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-31 10:52:22]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-31 10:52:23]

Dry run: This issue passed the CQ dry run.

[kojii, 2016-08-31 13:10:39]

The CQ bit was checked by kojii@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-31 13:10:52]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[kojii, 2016-08-31 13:31:09]

Description was changed from

==========
Still WIP

BUG=
==========

to

==========
Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

When there are multiple BidiRun in a line (multiple inline elements,
whitespace collapsing, or RTL,) setLogicalWidthForTextRun has
O(#BidiRun * #WordMeasurement), resulting similar characteristics as
O(n!) for the line length.

This patch fixes this for LTR.

For RTL, we could improve up to log2(N) by using binary search, or
better by using fast index for LineLayoutText for multiple elements
case. It was once tried but removed due to its complexity, we can do it
if that came up as a real case.

BUG=583711, 642345
==========

[kojii, 2016-08-31 13:34:26]

Description was changed from

==========
Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

When there are multiple BidiRun in a line (multiple inline elements,
whitespace collapsing, or RTL,) setLogicalWidthForTextRun has
O(#BidiRun * #WordMeasurement), resulting similar characteristics as
O(n!) for the line length.

This patch fixes this for LTR.

For RTL, we could improve up to log2(N) by using binary search, or
better by using fast index for LineLayoutText for multiple elements
case. It was once tried but removed due to its complexity, we can do it
if that came up as a real case.

BUG=583711, 642345
==========

to

==========
Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

When there are multiple BidiRun in a line (multiple inline elements,
whitespace collapsing, or RTL,) setLogicalWidthForTextRun has
O(#BidiRun * #WordMeasurement), resulting similar characteristics as
O(n!) for the line length.

This patch fixes this for LTR.

For RTL, we could improve up to log2(N) by using binary search, or
better by using fast index for LineLayoutText for multiple elements
case. It was once tried but removed due to its complexity, we can do it
if that came up as a real case.

Following performance tests are now 10-20x faster. The amount of text
for these tests were increased by 12x, matching to
long-line-nowrap.html.

PerformanceTests/Layout/long-line-nowrap-collapse.html
PerformanceTests/Layout/long-line-nowrap-spans-collapse.html

BUG=583711, 642345
==========

[kojii, 2016-08-31 13:38:30]

Description was changed from

==========
Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

When there are multiple BidiRun in a line (multiple inline elements,
whitespace collapsing, or RTL,) setLogicalWidthForTextRun has
O(#BidiRun * #WordMeasurement), resulting similar characteristics as
O(n!) for the line length.

This patch fixes this for LTR.

For RTL, we could improve up to log2(N) by using binary search, or
better by using fast index for LineLayoutText for multiple elements
case. It was once tried but removed due to its complexity, we can do it
if that came up as a real case.

Following performance tests are now 10-20x faster. The amount of text
for these tests were increased by 12x, matching to
long-line-nowrap.html.

PerformanceTests/Layout/long-line-nowrap-collapse.html
PerformanceTests/Layout/long-line-nowrap-spans-collapse.html

BUG=583711, 642345
==========

to

==========
Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

When there are multiple BidiRun in a line (multiple inline elements,
whitespace collapsing, or RTL,) setLogicalWidthForTextRun has
O(#BidiRun * #WordMeasurement), resulting similar characteristics as
O(n!) for the line length.

This patch fixes this for LTR.

For RTL, we could improve up to log2(N) by using binary search, or
better by using fast index for LineLayoutText for multiple elements
case. It was once tried but removed due to its complexity, we can do it
if they came up as real cases.

Following performance tests are now 10-20x faster. The amount of text
for these tests were increased by 12x, matching to
long-line-nowrap.html.

PerformanceTests/Layout/long-line-nowrap-collapse.html
PerformanceTests/Layout/long-line-nowrap-spans-collapse.html

BUG=583711, 642345
==========

[commit-bot: I haz the power, 2016-08-31 15:00:24]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-31 15:00:25]

Dry run: This issue passed the CQ dry run.

[kojii, 2016-08-31 15:01:31]

kojii@chromium.org changed reviewers:
+ eae@chromium.org

[kojii, 2016-08-31 15:01:33]

PTAL.

[eae, 2016-08-31 16:07:02]

LGTM

This is great, thanks for working on this!

[kojii, 2016-08-31 16:12:12]

The CQ bit was checked by kojii@chromium.org

[commit-bot: I haz the power, 2016-08-31 16:12:38]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-31 16:18:05]

Committed patchset #7 (id:120001)

[commit-bot: I haz the power, 2016-08-31 16:19:51]

Description was changed from

==========
Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

When there are multiple BidiRun in a line (multiple inline elements,
whitespace collapsing, or RTL,) setLogicalWidthForTextRun has
O(#BidiRun * #WordMeasurement), resulting similar characteristics as
O(n!) for the line length.

This patch fixes this for LTR.

For RTL, we could improve up to log2(N) by using binary search, or
better by using fast index for LineLayoutText for multiple elements
case. It was once tried but removed due to its complexity, we can do it
if they came up as real cases.

Following performance tests are now 10-20x faster. The amount of text
for these tests were increased by 12x, matching to
long-line-nowrap.html.

PerformanceTests/Layout/long-line-nowrap-collapse.html
PerformanceTests/Layout/long-line-nowrap-spans-collapse.html

BUG=583711, 642345
==========

to

==========
Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine)

When there are multiple BidiRun in a line (multiple inline elements,
whitespace collapsing, or RTL,) setLogicalWidthForTextRun has
O(#BidiRun * #WordMeasurement), resulting similar characteristics as
O(n!) for the line length.

This patch fixes this for LTR.

For RTL, we could improve up to log2(N) by using binary search, or
better by using fast index for LineLayoutText for multiple elements
case. It was once tried but removed due to its complexity, we can do it
if they came up as real cases.

Following performance tests are now 10-20x faster. The amount of text
for these tests were increased by 12x, matching to
long-line-nowrap.html.

PerformanceTests/Layout/long-line-nowrap-collapse.html
PerformanceTests/Layout/long-line-nowrap-spans-collapse.html

BUG=583711, 642345

Committed: https://crrev.com/ccd49c63f329c36da86b128b30e277d72f5bc76d
Cr-Commit-Position: refs/heads/master@{#415647}
==========

[commit-bot: I haz the power, 2016-08-31 16:19:53]

Patchset 7 (id:??) landed as
https://crrev.com/ccd49c63f329c36da86b128b30e277d72f5bc76d
Cr-Commit-Position: refs/heads/master@{#415647}

[drott, 2016-09-02 10:03:38]

Nice one!