Bug 136584 - Laying out a TextRun using an SVG font is O(n^2)
Summary: Laying out a TextRun using an SVG font is O(n^2)
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Myles C. Maxfield
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-09-05 13:15 PDT by Myles C. Maxfield
Modified: 2014-09-10 11:59 PDT (History)
13 users (show)

See Also:


Attachments
Patch (145.24 KB, patch)
2014-09-05 19:23 PDT, Myles C. Maxfield
kling: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Myles C. Maxfield 2014-09-05 13:15:20 PDT
SVGTextRunRenderingContext::glyphDataForCharacter() (called for each character in a run) calls SVGFontData::applySVGGlyphSelection(), which calls Font::normalizeSpaces() on the entire rest of the run (which is O(n))
Comment 1 Myles C. Maxfield 2014-09-05 19:23:27 PDT
Created attachment 237728 [details]
Patch
Comment 2 Myles C. Maxfield 2014-09-05 19:24:53 PDT
Comment on attachment 237728 [details]
Patch

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

> Source/WebCore/platform/graphics/TextRun.h:239
> +    mutable String m_normalizedSpaces;

We may want this cached value to live in WidthIterator::advanceInternal() instead of in TextRun.
Comment 3 Andreas Kling 2014-09-05 19:43:06 PDT
Comment on attachment 237728 [details]
Patch

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

r=me

> Source/WebCore/platform/graphics/TextRun.cpp:61
> +    if (m_normalizedSpaces.length() != static_cast<unsigned>(charactersLength())) {

Could do early return here.

>> Source/WebCore/platform/graphics/TextRun.h:239
>> +    mutable String m_normalizedSpaces;
> 
> We may want this cached value to live in WidthIterator::advanceInternal() instead of in TextRun.

I agree.
Comment 4 Myles C. Maxfield 2014-09-05 21:58:48 PDT
http://trac.webkit.org/changeset/173349
Comment 5 Carlos Alberto Lopez Perez 2014-09-06 07:50:39 PDT
(In reply to comment #4)
> http://trac.webkit.org/changeset/173349

The new perf test added by this commit (SVG/SVG-Text.html) is failing on all the performance bots:

AppleMavericks: http://build.webkit.org/builders/Apple%20Mavericks%20Release%20%28Perf%29/builds/2454
AppleMountainLion: http://build.webkit.org/builders/Apple%20MountainLion%20Release%20%28Perf%29/builds/9928
GTK: http://build.webkit.org/builders/GTK%20Linux%2064-bit%20Release%20%28Perf%29/builds/726
EFL: (offline)


It shouldn't fail.
Comment 6 Darin Adler 2014-09-06 17:45:54 PDT
Comment on attachment 237728 [details]
Patch

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

> Source/WebCore/platform/graphics/Font.h:273
> +    static inline bool treatAsSpace(UChar c) { return c == ' ' || c == '\t' || c == '\n' || c == noBreakSpace; }
> +    static inline bool treatAsZeroWidthSpace(UChar c) { return treatAsZeroWidthSpaceInComplexScript(c) || c == 0x200c || c == 0x200d; }
> +    static inline bool treatAsZeroWidthSpaceInComplexScript(UChar c) { return c < 0x20 || (c >= 0x7F && c < 0xA0) || c == softHyphen || c == zeroWidthSpace || (c >= 0x200e && c <= 0x200f) || (c >= 0x202a && c <= 0x202e) || c == zeroWidthNoBreakSpace || c == objectReplacementCharacter; }

These changes are unnecessary and unhelpful. They should have no effect on whether the functions get inlined.

> Source/WebCore/platform/graphics/TextRun.cpp:63
> +            m_normalizedSpaces = String(data8(0), charactersLength());

characters8() rather than data8(0)

But why copy these characters into a String? Why not just pass this pointer and length to Font::normalizeSpaces?

> Source/WebCore/platform/graphics/TextRun.cpp:66
> +            m_normalizedSpaces = String(data16(0), charactersLength());

characters16() rather than data16(0)

But why copy these characters into a String? Why not just pass this pointer and length to Font::normalizeSpaces?
Comment 7 Csaba Osztrogonác 2014-09-08 09:15:25 PDT
Are you planning to fix or skip this new but failing performance test?
Comment 8 Csaba Osztrogonác 2014-09-09 05:33:03 PDT
The test was fixed in https://trac.webkit.org/changeset/173417
Comment 9 Myles C. Maxfield 2014-09-10 11:57:27 PDT
Comment on attachment 237728 [details]
Patch

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

>> Source/WebCore/platform/graphics/Font.h:273
>> +    static inline bool treatAsZeroWidthSpaceInComplexScript(UChar c) { return c < 0x20 || (c >= 0x7F && c < 0xA0) || c == softHyphen || c == zeroWidthSpace || (c >= 0x200e && c <= 0x200f) || (c >= 0x202a && c <= 0x202e) || c == zeroWidthNoBreakSpace || c == objectReplacementCharacter; }
> 
> These changes are unnecessary and unhelpful. They should have no effect on whether the functions get inlined.

I believe I have created a patch a few months ago where I created a tiny static function and you instructed me to make it inline. What is the best practice for this?

Undone.

>> Source/WebCore/platform/graphics/TextRun.cpp:63
>> +            m_normalizedSpaces = String(data8(0), charactersLength());
> 
> characters8() rather than data8(0)
> 
> But why copy these characters into a String? Why not just pass this pointer and length to Font::normalizeSpaces?

Done.

Whoops. This was a case of not seeing the forest for the trees. Done.

>> Source/WebCore/platform/graphics/TextRun.cpp:66
>> +            m_normalizedSpaces = String(data16(0), charactersLength());
> 
> characters16() rather than data16(0)
> 
> But why copy these characters into a String? Why not just pass this pointer and length to Font::normalizeSpaces?

Done.

Done.
Comment 10 Myles C. Maxfield 2014-09-10 11:59:24 PDT
Addressing Darin's comments in https://trac.webkit.org/r173476