haikuwebkit/PerformanceTests/Layout
Myles C. Maxfield d5d49f5de5 Laying out complex text in columns is O(n^2)
https://bugs.webkit.org/show_bug.cgi?id=223363
<rdar://problem/68279075>

Reviewed by Zalan Bujtas.

PerformanceTests:

* Layout/complex-columns.html: Added.

Source/WebCore:

When we perform line breaking in complex text, we create a persistent TextLayout object for the entire element, and ask
it questions about how wide various substrings are in the element. Our calling pattern is like this:

layout.width(a, b);
layout.width(b, c);
layout.width(c, d);
layout.width(d, e);

The implementation of TextLayout::width() is like this:

m_controller->advance(before);
float beforeWidth = m_controller->runWidthSoFar();
m_controller->advance(after);
float afterWidth = m_controller->runWidthSoFar();

This means that ComplexTextController is getting called twice in a row with the same position. However, the implementation of
ComplexTextController::advance() has:

if (offset <= m_currentCharacter) {
    …
    m_glyphInCurrentRun = 0;
    …
}

The condition is true here, because it's getting called twice in a row with the same condition. However, when the condition
is true, we throw away all the previous work we've done during previous calls to ComplexTextController::advance().

This patch causes an 18x speedup on the performance test.

Performance Test: Layout/complex-columns.html

* platform/graphics/ComplexTextController.cpp:
(WebCore::ComplexTextController::advance):


Canonical link: https://commits.webkit.org/235412@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@274567 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2021-03-17 17:23:51 +00:00
..
Multicol
Shapes
resources
ArabicLineLayout-pre-and-wrap.html
ArabicLineLayout.html
ComplexLongUnique.html
LineLayoutJapanese.html
RegionsAuto.html
RegionsAutoMaxHeight.html
RegionsExtendingSelectionMixedContent.html
RegionsFixed.html
RegionsFixedShort.html
RegionsSelectAllMixedContent.html
RegionsSelection.html
RegionsShapes.html
auto-grid-lots-of-data.html
chapter-reflow-once-random.html
chapter-reflow-once.html
chapter-reflow-thrice.html
chapter-reflow-twice.html
chapter-reflow.html
complex-columns.html Laying out complex text in columns is O(n^2) 2021-03-17 17:23:51 +00:00
fixed-grid-lots-of-data.html
fixed-grid-lots-of-stretched-data.html
flexbox-column-nowrap.html
flexbox-column-wrap.html
flexbox-lots-of-data.html
flexbox-row-nowrap.html
flexbox-row-wrap.html
floats_2_100.html
floats_2_100_nested.html
floats_20_100.html
floats_20_100_nested.html
floats_50_100.html
floats_50_100_nested.html
floats_100_100.html
floats_100_100_nested.html
font-fallback-2.html
font-fallback-font-family.html
font-fallback.html
hindi-line-layout.html
inline-layout-no-text.html
large-table-with-collapsed-borders-and-colspans-wider-than-table.html
large-table-with-collapsed-borders-and-colspans.html
large-table-with-collapsed-borders-and-no-colspans.html
layers_overlap_2d.html
layers_overlap_3d.html
line-layout-inline-block.html
line-layout-inline-level-boxes.html
line-layout-long-long-text.html
line-layout-simple.html
line-layout.html
nested-column-flexboxes-relative-height.html
nested-grid.html
simple-line-layout-innertext.html
simple-line-layout-non-repeating-text.html
simple-line-layout-with-varying-content-and-optimized-speed.html
simple-line-layout-with-varying-content.html
simple-line-layout-word-break-long-text.html
subtree-detaching.html
system-ui-rebuild-emoji.html
system-ui.html
word-joiner.html