Bug 136584 – Laying out a TextRun using an SVG font is O(n^2)

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

[Myles C. Maxfield]

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))

[Myles C. Maxfield]

Created attachment 237728 [details]
Patch

[Myles C. Maxfield]

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.

[Andreas Kling]

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.

[Myles C. Maxfield]

http://trac.webkit.org/changeset/173349

[Carlos Alberto Lopez Perez]

(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.

[Darin Adler]

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?

[Csaba Osztrogonác]

Are you planning to fix or skip this new but failing performance test?

[Csaba Osztrogonác]

The test was fixed in https://trac.webkit.org/changeset/173417

[Myles C. Maxfield]

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.

[Myles C. Maxfield]

Addressing Darin's comments in https://trac.webkit.org/r173476