Bug 137275 – Speed up line parsing for simple line layout.

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[zalan]

Loading ./PerformanceTests/Layout/line-layout-simple.html (slightly modified version) produces the following result:
 
current: 
number of lines produced:  1258 
runs created: 2109
number of "fast" text measurement calls (renderText.width()):  3648 on the total length of 26968 characters. 
number of "slow" text measurement calls (style.font.width(run)): 7899 on the total length of 33306 characters 
all text measurements calls: 11547 on the total length of 60274 characters.

after applying this patch: 
number of lines produced:  1258 
runs created: 1704
number of "fast" text measurement calls:  3264 on the total length of 19240 characters. 
number of "slow" text measurement calls: 4095 on the total length of 24164 characters 
all text measurement calls: 7359 on the total length of 43404 characters.

current result: (line-layout-simple.html)
Running 20 times
    0: 73.8498789346247 runs/s (Ignored warm-up run)
    1: 74.6268656716418 runs/s
    2: 73.61963190184049 runs/s
    3: 75.18796992481202 runs/s
    4: 75.09386733416771 runs/s
    5: 74.71980074719801 runs/s
    6: 74.34944237918215 runs/s
    7: 72.81553398058253 runs/s
    8: 73.52941176470588 runs/s
    9: 73.43941248470013 runs/s
    10: 73.71007371007371 runs/s
    11: 73.80073800738008 runs/s
    12: 73.34963325183374 runs/s
    13: 73.17073170731707 runs/s
    14: 74.16563658838072 runs/s
    15: 74.81296758104739 runs/s
    16: 74.25742574257426 runs/s
    17: 73.98273736128236 runs/s
    18: 72.81553398058253 runs/s
    19: 72.72727272727273 runs/s
    20: 73.89162561576354 runs/s

:Runs -> [74.6268656716418, 73.61963190184049, 75.18796992481202, 75.09386733416771, 74.71980074719801, 74.34944237918215, 72.81553398058253, 73.52941176470588, 73.43941248470013, 73.71007371007371, 73.80073800738008, 73.34963325183374, 73.17073170731707, 74.16563658838072, 74.81296758104739, 74.25742574257426, 73.98273736128236, 72.81553398058253, 72.72727272727273, 73.89162561576354] runs/s
    mean: 73.90331562311695 runs/s
    median: 73.84618181157181 runs/s
    stdev: 0.7455580219232821 runs/s
    min: 72.72727272727273 runs/s
    max: 75.18796992481202 runs/s

after applying the patch:

Running 20 times
    0: 77.60814249363868 runs/s (Ignored warm-up run)
    1: 80.18327605956472 runs/s
    2: 79.36507936507937 runs/s
    3: 80.83140877598153 runs/s
    4: 79.89347536617844 runs/s
    5: 79.57559681697613 runs/s
    6: 80.64516129032258 runs/s
    7: 78.84362680683311 runs/s
    8: 79.6812749003984 runs/s
    9: 78.3289817232376 runs/s
    10: 78.63695937090432 runs/s
    11: 80.64516129032258 runs/s
    12: 78.63695937090432 runs/s
    13: 80.73817762399078 runs/s
    14: 80.64516129032258 runs/s
    15: 80.92485549132948 runs/s
    16: 80.73817762399078 runs/s
    17: 80.64516129032258 runs/s
    18: 78.84362680683311 runs/s
    19: 78.63695937090432 runs/s
    20: 79.57559681697613 runs/s

:Runs -> [80.18327605956472, 79.36507936507937, 80.83140877598153, 79.89347536617844, 79.57559681697613, 80.64516129032258, 78.84362680683311, 79.6812749003984, 78.3289817232376, 78.63695937090432, 80.64516129032258, 78.63695937090432, 80.73817762399078, 80.64516129032258, 80.92485549132948, 80.73817762399078, 80.64516129032258, 78.84362680683311, 78.63695937090432, 79.57559681697613] runs/s
    mean: 79.80073387256866 runs/s
    median: 79.78737513328842 runs/s
    stdev: 0.9019693694373813 runs/s
    min: 78.3289817232376 runs/s
    max: 80.92485549132948 runs/s

[zalan]

Created attachment 238974 [details]
Patch

[WebKit Commit Bot]

Attachment 238974 [details] did not pass style-queue:


ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:319:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:321:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:579:  Multi line control clauses should use braces.  [whitespace/braces] [4]
Total errors found: 3 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[zalan]

Created attachment 238975 [details]
SimpleLineLayout.cpp as the patch diff is far from perfect.

Added the entire file to have a better view on the changeset. (as it completely changes the parsing functions)

[Build Bot]

Comment on attachment 238974 [details]
Patch

Attachment 238974 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/6623868777136128

New failing tests:
tables/mozilla_expected_failures/bugs/bug2479-5.html

[Build Bot]

Created attachment 238981 [details]
Archive of layout-test-results from webkit-ews-10 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-10  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 238974 [details]
Patch

Attachment 238974 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/5255022971453440

New failing tests:
tables/mozilla_expected_failures/bugs/bug2479-5.html

[Build Bot]

Created attachment 238984 [details]
Archive of layout-test-results from webkit-ews-05 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-05  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[zalan]

Created attachment 238986 [details]
Patch

[WebKit Commit Bot]

Attachment 238986 [details] did not pass style-queue:


ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:319:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:321:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
Total errors found: 2 in 17 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Build Bot]

Comment on attachment 238986 [details]
Patch

Attachment 238986 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/5220023282958336

New failing tests:
tables/mozilla_expected_failures/bugs/bug2479-5.html

[Build Bot]

Created attachment 238993 [details]
Archive of layout-test-results from webkit-ews-15 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-15  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 238986 [details]
Patch

Attachment 238986 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/5116903265665024

New failing tests:
tables/mozilla_expected_failures/bugs/bug2479-5.html

[Build Bot]

Created attachment 238994 [details]
Archive of layout-test-results from webkit-ews-07 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-07  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[zalan]

Created attachment 239028 [details]
Patch

[WebKit Commit Bot]

Attachment 239028 [details] did not pass style-queue:


ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:319:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:321:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
Total errors found: 2 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[zalan]

Created attachment 239039 [details]
SimpleLineLayout.cpp to have a better view on the changeset as the diff is far from being perfect.

[zalan]

I'll put the rebaseline change to separate patch.

[Antti Koivisto]

Comment on attachment 239028 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=239028&action=review

Very nice, r=me

> Source/WebCore/ChangeLog:19
> +        The patch changes the behavior of overflow-wrap: break-word. Currently
> +        we wrap words at arbitrary positions regardless whether there's a valid wrapping
> +        position earlier on the line, while this patch checks it and wraps accordingly.
> +        It is inline with Firefox current behavior.  

This patch changes simple layout only. How about the line boxes?

> Source/WebCore/ChangeLog:43
> +        * rendering/SimpleLineLayout.cpp:
> +        (WebCore::SimpleLineLayout::skipWhitespace):
> +        (WebCore::SimpleLineLayout::computeLineLeft):
> +        (WebCore::SimpleLineLayout::TextFragment::TextFragment):
> +        (WebCore::SimpleLineLayout::TextFragment::operator=):
> +        (WebCore::SimpleLineLayout::TextFragment::isEmpty):
> +        (WebCore::SimpleLineLayout::LineState::LineState):
> +        (WebCore::SimpleLineLayout::LineState::commitAndCreateRun):
> +        (WebCore::SimpleLineLayout::LineState::addUncommitted):
> +        (WebCore::SimpleLineLayout::LineState::addUncommittedWhitespace):
> +        (WebCore::SimpleLineLayout::LineState::jumpTo):
> +        (WebCore::SimpleLineLayout::LineState::width):
> +        (WebCore::SimpleLineLayout::LineState::fits):
> +        (WebCore::SimpleLineLayout::LineState::removeCommittedTrailingWhitespace):
> +        (WebCore::SimpleLineLayout::removeTrailingWhitespace):
> +        (WebCore::SimpleLineLayout::initializeLine):
> +        (WebCore::SimpleLineLayout::splitFragmentToFitThisLine):
> +        (WebCore::SimpleLineLayout::nextFragment):
> +        (WebCore::SimpleLineLayout::createLineRuns):
> +        (WebCore::SimpleLineLayout::updateLineConstrains):
> +        (WebCore::SimpleLineLayout::createTextRuns):

Some function level comments would be nice to explain the refactoring.

> Source/WebCore/rendering/SimpleLineLayout.cpp:471
> +static TextFragment splitFragmentToFitThisLine(float availableWidth, TextFragment& fragmentToSplit, bool keepAtLeastOneCharacter, const RenderText& textRenderer, const CharacterType* text,

'This' doesn't add anything. 
fragmentToSplit could be the first parameter since it is being operated on.

> Source/WebCore/rendering/SimpleLineLayout.cpp:489
> +    // Simple binary search to find out what fits the current line.
> +    // FIXME: add surrogate pair support.
> +    unsigned left = fragmentToSplit.start;
> +    unsigned right = fragmentToSplit.end - 1; // We can ignore the last character. It surely does not fit.
> +    float width = 0;
> +    while (left < right) {

Nice optimization!

> Source/WebCore/rendering/SimpleLineLayout.cpp:521
> +    TextFragment current;

current->fragment perhaps

> Source/WebCore/rendering/SimpleLineLayout.cpp:563
> +        TextFragment currentFragment = nextFragment(line.end, lineBreakIterator, style, text, textLength, line.width(), textRenderer);

'current' doesn't really add much, maybe just 'fragment'

> Source/WebCore/rendering/SimpleLineLayout.cpp:571
> +            bool firstFragment = !line.width();

isFirstFragment

> Source/WebCore/rendering/SimpleLineLayout.cpp:575
> +                else // No need to add the new line fragment if there's already content on the line. We are about to close this line anyway.

Better to put the comment on the next line (and add {})

> Source/WebCore/rendering/SimpleLineLayout.cpp:585
> +            } else if (firstFragment) // Non-breakable non-whitespace first fragment. Add it to the current line. -it overflows though.

Here too

> Source/WebCore/rendering/SimpleLineLayout.cpp:587
> +            else // Non-breakable non-whitespace fragment when there's already a fragment on the line. Push it to the next line.

And here.

> Source/WebCore/rendering/SimpleLineLayout.cpp:620
> +static void updateLineConstrains(RenderBlockFlow& flow, float& availableWidth, float& logicalLeftOffset)

const RenderBlockFlow&

[Antti Koivisto]

Comment on attachment 239028 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=239028&action=review

> PerformanceTests/Layout/line-layout-simple.html:187
> +        <div style="text-align: justify">
> +            <h4>ARGUMENTUM</h4>

It would be good to land the performance test change first separately an wait a bit for the bots to get some results with the updated test before landing the code changes.

[Antti Koivisto]

Comment on attachment 239028 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=239028&action=review

> Source/WebCore/rendering/SimpleLineLayout.cpp:311
> +    TextFragment(const TextFragment& f)
> +        : start(f.start)
> +        , isCollapsedWhitespace(f.isCollapsedWhitespace)
> +        , end(f.end)
> +        , isWhitespaceOnly(f.isWhitespaceOnly)
> +        , isBreakable(f.isBreakable)
> +        , mustBreak(f.mustBreak)
> +        , width(f.width)
> +    {
>      }
> -}
>  
> -template <typename CharacterType>
> -void createTextRuns(Layout::RunVector& runs, unsigned& lineCount, RenderBlockFlow& flow, RenderText& textRenderer)
> -{
> -    const Style style(flow.style());
> +    TextFragment& operator=(const TextFragment& f)
> +    {
> +        start = f.start;
> +        end = f.end;
> +        isCollapsedWhitespace = f.isCollapsedWhitespace;
> +        isWhitespaceOnly = f.isWhitespaceOnly;
> +        isBreakable = f.isBreakable;
> +        mustBreak = f.mustBreak;
> +        width = f.width;
> +        return *this;
> +    }

Do you actually need these? The implicit copy constructor/operator should work right?

[zalan]

Committed r175048: <http://trac.webkit.org/changeset/175048>

[zalan]

(In reply to comment #21)
> Committed r175048: <http://trac.webkit.org/changeset/175048>
^^ performance test change only.

[zalan]

Created attachment 240505 [details]
Patch

[WebKit Commit Bot]

Attachment 240505 [details] did not pass style-queue:


ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:296:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:298:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
Total errors found: 2 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Build Bot]

Created attachment 240515 [details]
Archive of layout-test-results from webkit-ews-01 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-01  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[zalan]

Created attachment 240537 [details]
Patch

[WebKit Commit Bot]

Attachment 240537 [details] did not pass style-queue:


ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:296:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
ERROR: Source/WebCore/rendering/SimpleLineLayout.cpp:298:  Please declare enum bitfields as unsigned integral types.  [runtime/enum_bitfields] [5]
Total errors found: 2 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[WebKit Commit Bot]

Comment on attachment 240537 [details]
Patch

Clearing flags on attachment: 240537

Committed r175259: <http://trac.webkit.org/changeset/175259>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Alexey Proskuryakov]

This patch broke tables/mozilla_expected_failures/bugs/bug2479-5.html on Mavericks.

Updated the results in r175329 - the change was the same as on Yosemite, so I'm assuming that it's good.

It's surprising to have so many test result changes from a performance patch. Is the behavior changed explained somewhere? I looked though bugzilla comments, but couldn't find an explanation.

[zalan]

(In reply to comment #30)
> This patch broke tables/mozilla_expected_failures/bugs/bug2479-5.html on
> Mavericks.
> 
> Updated the results in r175329 - the change was the same as on Yosemite, so
> I'm assuming that it's good.
> 
> It's surprising to have so many test result changes from a performance
> patch. Is the behavior changed explained somewhere? I looked though bugzilla
> comments, but couldn't find an explanation.
If you look at the nature of the expected result changes, you'll see it's all about removing unnecessary (empty) text runs. Not creating empty runs has not that much of an impact on measurable performance, but the same time creating them is just a waste.
Thanks for the r175329 change.