Bug 141570 - textPath layout performance improvement
Summary: textPath layout performance improvement
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: SVG (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Said Abou-Hallawa
URL:
Keywords: InRadar
Depends on: 143751
Blocks:
  Show dependency treegraph
 
Reported: 2015-02-13 11:40 PST by Dean Jackson
Modified: 2015-04-15 02:10 PDT (History)
7 users (show)

See Also:


Attachments
Patch (27.56 KB, patch)
2015-04-08 17:29 PDT, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (27.25 KB, patch)
2015-04-08 18:34 PDT, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
test case (2.10 KB, image/svg+xml)
2015-04-09 10:30 PDT, Said Abou-Hallawa
no flags Details
Patch (30.58 KB, patch)
2015-04-09 11:13 PDT, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (55.14 KB, patch)
2015-04-12 20:49 PDT, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (65.16 KB, patch)
2015-04-14 15:53 PDT, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (66.45 KB, patch)
2015-04-14 16:50 PDT, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (66.49 KB, patch)
2015-04-14 17:02 PDT, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (63.00 KB, patch)
2015-04-14 17:28 PDT, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Dean Jackson 2015-02-13 11:40:23 PST
According to Ralph Thomas:
https://twitter.com/i_am_ralpht/status/566280495374168064

we could improve textPath performance by caching the bezier curve, or by not measuring the path twice for each glyph.
Comment 1 Radar WebKit Bug Importer 2015-02-13 11:41:05 PST
<rdar://problem/19830230>
Comment 2 Ralph T 2015-02-13 22:41:09 PST
In SVGTextLayoutEngine.cpp:557:

bool ok = false;
FloatPoint point = m_textPath.pointAtLength(textPathOffset, ok);
ASSERT(ok);

x = point.x();
y = point.y();
angle = m_textPath.normalAngleAtLength(textPathOffset, ok);
ASSERT(ok);

m_textPath is a Path, where the core of pointAtLength and normalAngleAtLength vary form platform to platform, but I think they all play the whole path back from the start.

Two possible improvements:
 - merge pointAtLength and normalAngleAtLength so the path only has to be walked once.
 - fix path iteration to continue from the last queried point instead of the start if the current query is ahead of the previous query (the SVG code walks the path sequentially because it's using glyph offsets, so this is a huge improvement).

The code currently is a bottleneck for animating the offset of text on a path.
Comment 3 Said Abou-Hallawa 2015-04-08 17:29:53 PDT
Created attachment 250396 [details]
Patch
Comment 4 Jon Lee 2015-04-08 17:38:32 PDT
Can we add a perf test here? Do we have measurements on how much faster this is?
Comment 5 Said Abou-Hallawa 2015-04-08 18:34:50 PDT
Created attachment 250400 [details]
Patch
Comment 6 Said Abou-Hallawa 2015-04-09 10:30:44 PDT
Created attachment 250444 [details]
test case
Comment 7 Said Abou-Hallawa 2015-04-09 10:34:57 PDT
(In reply to comment #4)
> Can we add a perf test here? Do we have measurements on how much faster this
> is?

When running the attached test case using the webkit performance runner, the results are:

Without the patch: 

    mean: 1792.106688497006 ms
    median: 1788.6809015180916 ms
    stdev: 39.76658446899556 ms
    min: 1748.82149300538 ms
    max: 1904.532784014009 ms

With the patch:

    mean: 909.9649922456591 ms
    median: 907.5612444721628 ms
    stdev: 6.427914386842484 ms
    min: 900.7325859856792 ms
    max: 925.5951620289125 ms

We almost cut the the time spent loading the page into half. I will add this test case to the patch.
Comment 8 Said Abou-Hallawa 2015-04-09 11:13:04 PDT
Created attachment 250448 [details]
Patch
Comment 9 Said Abou-Hallawa 2015-04-12 20:49:28 PDT
Created attachment 250621 [details]
Patch
Comment 10 Darin Adler 2015-04-13 09:36:40 PDT
Comment on attachment 250621 [details]
Patch

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

> Source/WebCore/platform/graphics/Path.h:63
> +    class PathTraversalState;

Seems like this should be a member of the Path class, Path::TraversalState. Something we can come back to and do later. Same thought on PathElementType and PathElement.

> Source/WebCore/platform/graphics/Path.h:108
> +        PathTraversalState traversalStateAtLength(float, bool&) const;
> +        FloatPoint pointAtLength(float, bool&) const;
> +        float normalAngleAtLength(float, bool&) const;

I don’t think the meaning of these bool& arguments is clear without an argument name. Not that "ok" is all that great, but no name at all is confusing. Same thought about "length"; not sure that it’s clear that the float is the length from "AtLength" without the name "length".

> Source/WebCore/platform/graphics/PathTraversalState.cpp:119
> +static float curveLength(PathTraversalState& traversalState, const CurveType& elementCurve)

Are you sure that using a reference here is better for performance? I guess the point was to not modify the argument, but I think the old code was really OK.

> Source/WebCore/platform/graphics/PathTraversalState.h:36
>      enum PathTraversalAction {

Seems like this should be "enum class Action"; no need to repeat the name of the class it’s a member of.

> Source/WebCore/platform/graphics/PathTraversalState.h:42
> +    PathTraversalState(PathTraversalAction, float = 0);

Not clear what this second argument is without an argument name.

> Source/WebCore/platform/graphics/PathTraversalState.h:52
> +private:
> +    void closeSubpath();
> +    void moveTo(const FloatPoint&);
> +    void lineTo(const FloatPoint&);
> +    void quadraticBezierTo(const FloatPoint&, const FloatPoint&);
> +    void cubicBezierTo(const FloatPoint&, const FloatPoint&, const FloatPoint&);
> +
> +    bool finalizeAppendPathElement();
> +    bool appendPathElement(PathElementType, const FloatPoint*);

Normally we put all the public members first, then move on to the private ones.

> Source/WebCore/platform/graphics/PathTraversalState.h:71
> +    bool m_zeroVector { false };

I think this should be named m_isZeroVector or something like that. The value is a predicate, not a vector, so it’s strange to name the member “zero vector”.

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:54
> +    if (SVGTextContentElement* textContentElement = SVGTextContentElement::elementFromRenderer(box->renderer().parent())) {

I suggest auto* here.

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:78
> +        const Vector<SVGTextFragment>& fragments = box->textFragments();

No need for this local variable. Just:

    for (auto& fragment : box->textFragments())

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:91
> +    for (auto it = m_boxes.begin(), end = m_boxes.end(); it != end; ++it) {

Should use a modern for loop here:

    for (auto* box : m_boxes) {

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:92
> +        const Vector<SVGTextFragment>& fragments = (*it)->textFragments();

Should use auto& here.

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:99
> +    for (auto it = m_boxes.rbegin(), end = m_boxes.rend(); it != end; ++it) {

Can’t use modern for loop here because we don’t yet have an adapter to let us iterate backwards through a vector, but we should write one!

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:100
> +        const Vector<SVGTextFragment>& fragments = (*it)->textFragments();

Should use auto& here.

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:149
> +        Vector<SVGTextFragment>& fragments = box->textFragments();

No need for a local variable here:

    for (auto& fragment : box->textFragments()) {

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:204
> +        Vector<SVGTextFragment>& fragments = box->textFragments();

No need for a local variable here:

    for (auto& fragment : box->textFragments()) {

> Source/WebCore/rendering/svg/SVGTextChunk.h:44
> +    SVGTextChunk(const Vector<SVGInlineTextBox*>::const_iterator&, const Vector<SVGInlineTextBox*>::const_iterator&);

I think this is overkill. Vector iterators are just raw pointers. Passing one by const& is unnecessarily inefficient, and also wordy. Also, with no argument names it’s not clear what the two iterators are supposed to be. I guess I’m suggesting:

    SVGTextChunk(SVGInlineTextBox** begin, SVGInlineTextBox** end);

> Source/WebCore/rendering/svg/SVGTextChunkBuilder.cpp:34
>  void SVGTextChunkBuilder::transformationForTextBox(SVGInlineTextBox* textBox, AffineTransform& transform) const

We should use a return value instead of an out argument for this.

> Source/WebCore/rendering/svg/SVGTextChunkBuilder.cpp:36
> +    static NeverDestroyed<const AffineTransform> s_identityTransform;

Not sure this is a helpful optimization. Instead I think we should just do:

    transform = AffineTransform();

> Source/WebCore/rendering/svg/SVGTextChunkBuilder.cpp:51
> +    Vector<SVGInlineTextBox*>::const_iterator it = lineLayoutBoxes.begin();
> +    Vector<SVGInlineTextBox*>::const_iterator end = lineLayoutBoxes.end();
> +    Vector<SVGInlineTextBox*>::const_iterator start = end;

For vectors we normally consider it safer to use indices rather than iterators. Also, I suggest using auto for these three if you are going to use iterators.

> Source/WebCore/rendering/svg/SVGTextChunkBuilder.cpp:78
> +    for (const auto& chunk : m_textChunks) {
> +        chunk.layout(m_textBoxTransformations);
>      }

No braces in WebKit coding style for a single line loop body like this.

> Source/WebCore/rendering/svg/SVGTextLayoutEngine.cpp:554
> +            PathTraversalState traversalState(m_textPath.traversalStateAtLength(textPathOffset, ok));

I would write:

   auto traversalState = m_textPath.traversalStateAtLength(textPathOffset, ok);

> Source/WebCore/svg/SVGAnimateMotionElement.cpp:219
> +    PathTraversalState traversalState(m_animationPath.traversalStateAtLength(positionOnPath, ok));

Ditto.
Comment 11 Said Abou-Hallawa 2015-04-14 15:53:46 PDT
Created attachment 250749 [details]
Patch
Comment 12 Said Abou-Hallawa 2015-04-14 16:16:22 PDT
Comment on attachment 250621 [details]
Patch

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

>> Source/WebCore/platform/graphics/Path.h:108
>> +        float normalAngleAtLength(float, bool&) const;
> 
> I don’t think the meaning of these bool& arguments is clear without an argument name. Not that "ok" is all that great, but no name at all is confusing. Same thought about "length"; not sure that it’s clear that the float is the length from "AtLength" without the name "length".

Done. I returned back the argument name "length" and I changed "ok" to be "success". I was assuming mistakenly that I should always omit the argument name in the header file. But now I learnt that the argument name is still needed if the function name is not enough to tell what it is if it is omitted.

>> Source/WebCore/platform/graphics/PathTraversalState.cpp:119
>> +static float curveLength(PathTraversalState& traversalState, const CurveType& elementCurve)
> 
> Are you sure that using a reference here is better for performance? I guess the point was to not modify the argument, but I think the old code was really OK.

The reason for me changing it to const CurveType& was because I wanted to assert the right-most split curve and the original curve have the same end.  So instead of having it as it was "CurveType curve" and make a copy of it to be used before exiting the function, I thought if I do it this way it will serve my purpose and it is cleaner.

>> Source/WebCore/platform/graphics/PathTraversalState.h:36
>>      enum PathTraversalAction {
> 
> Seems like this should be "enum class Action"; no need to repeat the name of the class it’s a member of.

Done.

>> Source/WebCore/platform/graphics/PathTraversalState.h:42
>> +    PathTraversalState(PathTraversalAction, float = 0);
> 
> Not clear what this second argument is without an argument name.

Done. I added the argument name "float desiredLength = 0" to the constructor definition. And I added the following assertion to the constructor:

ASSERT(action != Action::TotalLength || !desiredLength);

To prevent any one from creating an instance of this class with Action::TotalLength but passing a non-zero desiredLength.

>> Source/WebCore/platform/graphics/PathTraversalState.h:52
>> +    bool appendPathElement(PathElementType, const FloatPoint*);
> 
> Normally we put all the public members first, then move on to the private ones.

Done. I also made all the data members private and added the needed access methods. This class looks much cleaner with these changes.

>> Source/WebCore/platform/graphics/PathTraversalState.h:71
>> +    bool m_zeroVector { false };
> 
> I think this should be named m_isZeroVector or something like that. The value is a predicate, not a vector, so it’s strange to name the member “zero vector”.

Done.

>> Source/WebCore/rendering/svg/SVGTextChunk.cpp:54
>> +    if (SVGTextContentElement* textContentElement = SVGTextContentElement::elementFromRenderer(box->renderer().parent())) {
> 
> I suggest auto* here.

Done.

>> Source/WebCore/rendering/svg/SVGTextChunk.cpp:78
>> +        const Vector<SVGTextFragment>& fragments = box->textFragments();
> 
> No need for this local variable. Just:
> 
>     for (auto& fragment : box->textFragments())

Done.

>> Source/WebCore/rendering/svg/SVGTextChunk.cpp:91
>> +    for (auto it = m_boxes.begin(), end = m_boxes.end(); it != end; ++it) {
> 
> Should use a modern for loop here:
> 
>     for (auto* box : m_boxes) {

Done.

>> Source/WebCore/rendering/svg/SVGTextChunk.cpp:92
>> +        const Vector<SVGTextFragment>& fragments = (*it)->textFragments();
> 
> Should use auto& here.

Done.

>> Source/WebCore/rendering/svg/SVGTextChunk.cpp:100
>> +        const Vector<SVGTextFragment>& fragments = (*it)->textFragments();
> 
> Should use auto& here.

Done.

>> Source/WebCore/rendering/svg/SVGTextChunk.cpp:149
>> +        Vector<SVGTextFragment>& fragments = box->textFragments();
> 
> No need for a local variable here:
> 
>     for (auto& fragment : box->textFragments()) {

Done.

>> Source/WebCore/rendering/svg/SVGTextChunk.cpp:204
>> +        Vector<SVGTextFragment>& fragments = box->textFragments();
> 
> No need for a local variable here:
> 
>     for (auto& fragment : box->textFragments()) {

Done,

>> Source/WebCore/rendering/svg/SVGTextChunk.h:44
>> +    SVGTextChunk(const Vector<SVGInlineTextBox*>::const_iterator&, const Vector<SVGInlineTextBox*>::const_iterator&);
> 
> I think this is overkill. Vector iterators are just raw pointers. Passing one by const& is unnecessarily inefficient, and also wordy. Also, with no argument names it’s not clear what the two iterators are supposed to be. I guess I’m suggesting:
> 
>     SVGTextChunk(SVGInlineTextBox** begin, SVGInlineTextBox** end);

Done. The constructor of this class is now taking integers instead of iterators as you suggested below when the SVGTextChunk is created from the SVGTextChunkBuilder.

SVGTextChunk(const Vector<SVGInlineTextBox*>&, unsigned first, unsigned limit);

>> Source/WebCore/rendering/svg/SVGTextChunkBuilder.cpp:34
>>  void SVGTextChunkBuilder::transformationForTextBox(SVGInlineTextBox* textBox, AffineTransform& transform) const
> 
> We should use a return value instead of an out argument for this.

Done.

>> Source/WebCore/rendering/svg/SVGTextChunkBuilder.cpp:36
>> +    static NeverDestroyed<const AffineTransform> s_identityTransform;
> 
> Not sure this is a helpful optimization. Instead I think we should just do:
> 
>     transform = AffineTransform();

Done. The static variable was removed.

>> Source/WebCore/rendering/svg/SVGTextChunkBuilder.cpp:51
>> +    Vector<SVGInlineTextBox*>::const_iterator start = end;
> 
> For vectors we normally consider it safer to use indices rather than iterators. Also, I suggest using auto for these three if you are going to use iterators.

Done. Integers are now used to pass the range of boxes to the SVGTextChunk constructor.

>> Source/WebCore/rendering/svg/SVGTextChunkBuilder.cpp:78
>>      }
> 
> No braces in WebKit coding style for a single line loop body like this.

Done.

>> Source/WebCore/rendering/svg/SVGTextLayoutEngine.cpp:554
>> +            PathTraversalState traversalState(m_textPath.traversalStateAtLength(textPathOffset, ok));
> 
> I would write:
> 
>    auto traversalState = m_textPath.traversalStateAtLength(textPathOffset, ok);

Done.

>> Source/WebCore/svg/SVGAnimateMotionElement.cpp:219
>> +    PathTraversalState traversalState(m_animationPath.traversalStateAtLength(positionOnPath, ok));
> 
> Ditto.

Done.
Comment 13 Said Abou-Hallawa 2015-04-14 16:50:55 PDT
Created attachment 250756 [details]
Patch
Comment 14 Said Abou-Hallawa 2015-04-14 17:02:03 PDT
Created attachment 250759 [details]
Patch
Comment 15 Said Abou-Hallawa 2015-04-14 17:28:12 PDT
Created attachment 250764 [details]
Patch
Comment 16 WebKit Commit Bot 2015-04-14 18:35:27 PDT
Comment on attachment 250764 [details]
Patch

Clearing flags on attachment: 250764

Committed r182828: <http://trac.webkit.org/changeset/182828>
Comment 17 WebKit Commit Bot 2015-04-14 18:35:34 PDT
All reviewed patches have been landed.  Closing bug.
Comment 18 Csaba Osztrogonác 2015-04-15 02:10:43 PDT
Comment on attachment 250764 [details]
Patch

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

> Source/WebCore/rendering/svg/SVGTextChunk.cpp:32
> +SVGTextChunk::SVGTextChunk(const Vector<SVGInlineTextBox*>& lineLayoutBoxes, unsigned first, unsigned limit)
>  {
> -}
> +    ASSERT(first < limit);
> +    ASSERT(first >= 0 && limit <= lineLayoutBoxes.size());
>  

first >= 0 is always true, which broke the debug builds:
buildfix can be found here - bug143751