Improve line breaking performance for complex text

• Component: Text
• Status: RESOLVED FIXED

[Ned Holbrook]

Profiling on Mac and iOS has shown that measuring complex text by creating a ComplexTextController for each word is suboptimal. This patch addresses this for RenderBlock::LineBreaker::nextLineBreak by creating and reusing a ComplexTextController per RenderText. Benchmarks using a simple test app show a 35% improvement when laying out a paragraph of English text with optimizeLegibility.

[Ned Holbrook]

Created attachment 135359 [details]
Proposed changes.

[Build Bot]

Comment on attachment 135359 [details]
Proposed changes.

Attachment 135359 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12323213

[Philippe Normand]

Comment on attachment 135359 [details]
Proposed changes.

Attachment 135359 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/12322256

[Ned Holbrook]

Created attachment 135366 [details]
Fix EWS failures.

[Ned Holbrook]

Sorry, that's probably going to need a nullptr...

[Ned Holbrook]

Created attachment 135369 [details]
Fix EWS failures, again.

[Ned Holbrook]

Created attachment 141204 [details]
Rebased patch.

Rebased and retested (on Lion). I made one change relative to the previous patch by not taking the new path when positional effects (tabs) are enabled; although there were no test failures due to the previous patch, tabs could have had unwanted side effects.

[Darin Adler]

Comment on attachment 141204 [details]
Rebased patch.

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

This generally looks good to me. There are some stylistic issues that should be fixed before landing. I’m going to say r=me but I’d also like the patch to state what performance results we achieved with this change.

Someone even more expert with this part of WebKit might have some other more substantive comments.

> Source/WebCore/ChangeLog:24
> +        (WTF): Define deleteOwnedPtr for TextLayout as calling through destroyLayout; relying on operator delete is not workable as the class does not exist on all platforms.

Normally what we’d do is put a platform #if around the line of code that defines the data member of type OwnPtr<TextLayout>.

> Source/WebCore/ChangeLog:26
> +        (WebCore): Implement no-op TextLayout wrappers for non-Mac platforms.

I’m not sure this is the right approach.

> Source/WebCore/platform/graphics/Font.cpp:33
> +#if !PLATFORM(MAC)
> +#include "NotImplemented.h"
> +#endif

Conditional includes normally go in a separate paragraph after the main includes.

Alternatively, I think it’s OK to include this unconditionally.

> Source/WebCore/platform/graphics/Font.cpp:47
> +template <> void deleteOwnedPtr<WebCore::TextLayout>(WebCore::TextLayout* ptr)

Might be useful to put ac moment here explaining why we did this. I think the answer is that it allows use to compile the destruction of OwnPtr<TextLayout> in source files that don’t have access to the TextLayout class definition.

I’m not sure it’s worth it -- we haven’t done this for any other classes in WebCore -- but it’s probably OK.

> Source/WebCore/platform/graphics/Font.h:316
> +template <> void deleteOwnedPtr<WebCore::TextLayout>(WebCore::TextLayout* ptr);

Should omit the argument name here to match usual WebKit coding style.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:53
> +        TextRun run = RenderBlock::constructTextRun(text, font, text->characters(), text->textLength(), text->style());
> +        Font::CodePath codePathToUse = font.codePath(run);
> +        return codePathToUse == Font::Complex;

Might be more readable to eliminate the two local variables. Or you could at least omit the second one.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:57
> +        : m_font(font)

I suggest adding a helper function that returns a font with word spacing set to 0 so we can initialize this.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:58
> +        , m_run(0, 0)

Then we can initialize this properly as well. I suggest making a helper function to do that so we don’t have to first initialize it to (0, 0) just to overwrite it a moment later.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:68
> +        m_controller = new ComplexTextController(&m_font, m_run, true);

Then this could be done with initialization too. This should use an OwnPtr and adoptPtr.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:73
> +    ~TextLayout()
> +    {
> +        delete m_controller;
> +    }

This function wouldn’t be necessary if we used OwnPtr.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:86
> +    TextRun m_run;

Do we need to keep the TextRun around after making the ComplexTextController? I think I can see why we might need to keep m_font around, but not clear on why we have to keep m_run around.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:106
> +void Font::destroyLayout(TextLayout* layout)
> +{
> +    delete layout;
> +}

On further reflection, I think we should just put the TextLayout class in a header so we don’t need this function.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:111
> +float Font::width(TextLayout& layout, unsigned from, unsigned to)
> +{
> +    return layout.width(from, to);
> +}

Or this function.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:485
> +            const ComplexTextRun& complexTextRun = *m_complexTextRuns[r];
> +            leftmostGlyph += complexTextRun.glyphCount();

I don’t think you need the local variable here.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:493
> +            unsigned r = m_runIndices.last();

I don’t think this local variable helps readability.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:494
> +            const ComplexTextRun& currentTextRun = *m_complexTextRuns[r];

I suggest naming this local variable just "run" rather than "currentTextRun".

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:495
> +            offset = currentTextRun.stringLocation() + currentTextRun.indexEnd();

If there was a helper function that did this addition, either a member function or a free function, then we would not need the local variable.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:498
> +        for (unsigned q = 0; q < runCount; ++q) {

We normally name these loop variables i in WebKit.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:499
> +            const ComplexTextRun& complexTextRun = *m_complexTextRuns[q];

More of the same.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:500
> +            if (offset == complexTextRun.stringLocation() + complexTextRun.indexBegin()) {

More of the same.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:507
> +    unsigned r = m_runIndices[m_currentRun];

We typically use words rather than letters for variable names in WebKit, with only one or two customary exceptions.

Maybe this could be named currentRunIndex?

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:508
> +    for (unsigned q = 0; q < r; ++q) {

We normally name these loop variables i in WebKit.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:510
> +        const ComplexTextRun& complexTextRun = *m_complexTextRuns[q];
> +        leftmostGlyph += complexTextRun.glyphCount();

More of the same.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:519
> +        const ComplexTextRun& currentTextRun = *m_complexTextRuns[m_currentRun++];
> +        leftmostGlyph += currentTextRun.glyphCount();

Again, I think this would read better without the local variable.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:546
> +    unsigned r = indexOfCurrentRun(leftmostGlyph);

Should be named leftmostGlyphIndex.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:552
>          unsigned g = ltr ? m_glyphInCurrentRun : glyphCount - 1 - m_glyphInCurrentRun;
> +        unsigned k = leftmostGlyph + g;

Sad to see the existing code used "g" and "k" for these. I don’t recommend changing that at this time, though.

> Source/WebCore/platform/graphics/mac/ComplexTextController.h:171
> +    Vector<unsigned, 16> m_runIndices;

Where did the number 16 come from? I guess the vectors above all say 64 with no comment saying where that came from.

[Ned Holbrook]

(In reply to comment #8)
> On further reflection, I think we should just put the TextLayout class in a header so we don’t need this function.

Unless I'm missing something, this is actually the cleanest approach without simply moving the problem elsewhere. Part of the problem stems from the class definition needing to be visible at the point of OwnPtr declaration: this means that any header TextLayout is in also needs to include ComplexTextController.h but of course that is meant to be a private implementation detail too.
 
> > Source/WebCore/platform/graphics/mac/ComplexTextController.h:171
> > +    Vector<unsigned, 16> m_runIndices;
> 
> Where did the number 16 come from? I guess the vectors above all say 64 with no comment saying where that came from.

It was just a seat of the pants number. Since it's meant to correlate to reasonable number of bidi runs in a layout anyway I've decreased it to 8 since in my tests it doesn't seem to make much difference.

[Ned Holbrook]

Created attachment 152485 [details]
Changes per review.

Made the changes per Darin's review (minus moving TextLayout, since I haven't figured how to do so cleanly).

[Ned Holbrook]

Comment on attachment 152485 [details]
Changes per review.

Additional testing revealed a bug, setting r- and cq- until I have a fix ready.

[Ned Holbrook]

Created attachment 153881 [details]
Fixed and rebased patch.

The issue I was seeing was due a bug in my handling of the missing glyphs run constructor and has been fixed. I also rebased the patch since Mitz was kind enough to obsolete the ATSUI path.

[Darin Adler]

Comment on attachment 153881 [details]
Fixed and rebased patch.

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

> Source/WebCore/ChangeLog:11
> +        Currently RenderBlock::LineBreaker::nextLineBreak assumes that measuring individual words is as cheap
> +        as free. This is not the case when dealing with complex text, which benefits from laying out as much
> +        text as possible and by reusing that layout when feasible: by doing so this patch improves line
> +        breaking by 35% as measured with a simple test app.

Do we have data that indicates no additional cost when not using the complex text case?

> Source/WebCore/platform/graphics/Font.cpp:213
> +PassOwnPtr<TextLayout> Font::createLayout(RenderText*, float xPos, bool collapseWhiteSpace) const

Normally we’d leave out all the argument names here to avoid unused argument warnings.

> Source/WebCore/platform/graphics/Font.cpp:222
> +float Font::width(TextLayout&, unsigned from, unsigned to)

Here too. Leave out the argument names.

> Source/WebCore/platform/graphics/Font.cpp:224
> +    notImplemented();

I think we want ASSERT_NOT_REACHED() here rather than just notImplemented().

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:50
> +    static Font fontWithNoWordSpacing(const Font& originalFont)

Seems this could be private. Or a non-member helper function outside the class.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:57
> +    static TextRun constructTextRun(RenderText* text, const Font& font, float xPos)

This could/should be private.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:70
> +        , m_controller(adoptPtr(new ComplexTextController(&m_font, m_run, true)))

The use of a boolean here leads to not-all-that-readable code. What does true mean? In WebKit we normally avoid this, or used named enums for them, to prevent that problem.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:76
> +        m_controller->advance(from, 0, true);

Same problem here with the boolean argument.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:78
> +        m_controller->advance(from + len, 0, true);

And here.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:94
> +    if (collapseWhiteSpace && TextLayout::isNeeded(text, *this))
> +        return adoptPtr(new TextLayout(text, *this, xPos));
> +    return nullptr;

It’s idiomatic in WebKit to use “early return”, which means we’d have the if statement reversed. Or use two separate if statements. The case where we actually create a TextLayout would be the one not indented.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:100
> +void Font::destroyLayout(TextLayout* layout)
> +{
> +    delete layout;
> +}

I’d have called this deleteLayout, for reasons that may be obvious here.

> Source/WebCore/platform/graphics/mac/ComplexTextController.h:97
> +        bool ltr() const { return m_ltr; }

Normally we’d name this isLTR() rather than ltr().

> Source/WebCore/platform/graphics/mac/ComplexTextController.h:119
> +        bool m_ltr;

Normally we’d name this m_isLTR rather than m_ltr.

> Source/WebCore/platform/graphics/mac/ComplexTextController.h:133
> +    Vector<unsigned, 8> m_runIndices;

We typically put a “why” comment near constants like this 8, to indicate where the number came from.

> Source/WebCore/platform/graphics/mac/ComplexTextController.h:137
> +    bool m_ltrOnly;

Normally we’d name this m_isLTROnly rather than m_ltrOnly.

[Ned Holbrook]

(In reply to comment #13)
> (From update of attachment 153881 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=153881&action=review
> 
> Do we have data that indicates no additional cost when not using the complex text case?

Said simple test app has options to test both paths and I observed no regression when not using the complex text case.

> > Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:70
> > +        , m_controller(adoptPtr(new ComplexTextController(&m_font, m_run, true)))
> 
> The use of a boolean here leads to not-all-that-readable code. What does true mean? In WebKit we normally avoid this, or used named enums for them, to prevent that problem.

Agreed, although this boolean argument predates this patch.

> > Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:76
> > +        m_controller->advance(from, 0, true);
> 
> Same problem here with the boolean argument.

This one is my fault, I'll fix it.

> > Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:78
> > +        m_controller->advance(from + len, 0, true);
> 
> And here.

Ditto.

As for the rest of the comments, I'll make the suggested changes. Thanks, Darin.

[Ned Holbrook]

Created attachment 153968 [details]
More changes per review.

[Eric Seidel (no email)]

Comment on attachment 141204 [details]
Rebased patch.

Cleared Darin Adler's review+ from obsolete attachment 141204 [details] so that this bug does not appear in http://webkit.org/pending-commit.

[Eric Seidel (no email)]

Comment on attachment 153881 [details]
Fixed and rebased patch.

Cleared Darin Adler's review+ from obsolete attachment 153881 [details] so that this bug does not appear in http://webkit.org/pending-commit.

Comment on attachment 153968 [details]
More changes per review.

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

> Source/WebCore/rendering/RenderBlockLineLayout.cpp:2368
> +            if (textLayoutInfo.first != t) {
> +                textLayoutInfo.first = t;
> +                textLayoutInfo.second = f.createLayout(t, width.currentWidth(), collapseWhiteSpace);
> +            }
> +            TextLayout* textLayout = textLayoutInfo.second.get();

This is very similar to the treatment of lineBreakIteratorInfo further down, so I want to understand the two differences:
1) It’s not checking for a change to t->characters() (which, I believe, can occur with counters, see r107733
2) It’s outside the loop that iterates over positions in the text. I think this is actually fine, and the lineBreakIteratorInfo check can also be moved outside the loop, but I am not sure

If there’s no good reason for the textLayoutInfo treatment to differ from the lineBreakIteratorInfo treatment, then can they be united?

(In reply to comment #18)
> If there’s no good reason for the textLayoutInfo treatment to differ from the lineBreakIteratorInfo treatment, then can they be united?

I mean, can a single struct be used to hold both the line break iterator and the text layout for the current RenderText.

[Darin Adler]

Comment on attachment 153968 [details]
More changes per review.

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

Once you answer Dan’s comment mentioning lineBreakIteratorInfo then I’d say review+.

> Source/WebCore/platform/graphics/mac/ComplexTextController.cpp:84
> +    // ComplexTextController has only references to its Font and TextRun so they must be kept alive here

Need a period at the end of this sentence-style comment.

[Eric Seidel (no email)]

Looks like this (very cool) patch got forgotten.  Ned?

[Ned Holbrook]

(In reply to comment #21)
> Looks like this (very cool) patch got forgotten.  Ned?

I made a change to hopefully address Dan's question and am rebasing it now. I plan to make the new patch available by tomorrow.

[Ned Holbrook]

Created attachment 160348 [details]
Consolidate TextLayout and LazyLineBreakIterator into new RenderTextInfo struct.

[WebKit Review Bot]

Comment on attachment 160348 [details]
Consolidate TextLayout and LazyLineBreakIterator into new RenderTextInfo struct.

Rejecting attachment 160348 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 2

Last 500 characters of output:

Hunk #7 succeeded at 2433 (offset 47 lines).
Hunk #8 succeeded at 2461 (offset 47 lines).
Hunk #9 succeeded at 2487 (offset 47 lines).
Hunk #10 succeeded at 2506 (offset 47 lines).
Hunk #11 succeeded at 2632 (offset 47 lines).
1 out of 11 hunks FAILED -- saving rejects to file Source/WebCore/rendering/RenderBlockLineLayout.cpp.rej

Failed to run "[u'/mnt/git/webkit-commit-queue/Tools/Scripts/svn-apply', u'--force', u'--reviewer', u'Dan Bernst..." exit_code: 1 cwd: /mnt/git/webkit-commit-queue/

Full output: http://queues.webkit.org/results/13623051

(In reply to comment #24)
> 1 out of 11 hunks FAILED -- saving rejects to file Source/WebCore/rendering/RenderBlockLineLayout.cpp.rej

I’ll land the patch myself.

Committed as <http://trac.webkit.org/r126763>.

[Julien Chaffraix]

Fixed the Chromium Mac build in http://trac.webkit.org/changeset/126770

(In reply to comment #26)
> Committed as <http://trac.webkit.org/r126763>.

This caused bug 96890.

(In reply to comment #26)
> Committed as <http://trac.webkit.org/r126763>.

This caused bug 97280.

[Dominik Röttsches (drott)]

(In reply to comment #0)
> Profiling on Mac and iOS has shown that measuring complex text by creating a ComplexTextController for each word is suboptimal. This patch addresses this for RenderBlock::LineBreaker::nextLineBreak by creating and reusing a ComplexTextController per RenderText. Benchmarks using a simple test app show a 35% improvement when laying out a paragraph of English text with optimizeLegibility.

Ned, could you publish that test app or give some details on how you measured? Was it a web page based benchmark? Or a native app that links against some of the line layout code and tested that with some demo strings?

I am looking at this code in Blink now and it looks like the optimization is not as effective any more - when setting the TextLayout to nullptr and running the old path is actually now faster for example for Arabic line layout - but I'd like to get better data.