Bug 105230 – [Graphics] PathTraversalState.cpp does too many sqrts!

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

[Philip Rogers]

Check out this profile of SvgCubics.html:
    62.73%  SignalSender  libm.so               [.] sqrtf
     7.08%  SignalSender  libDumpRenderTree.so  [.] WebCore::PathTraversalState::cubicBezierTo(WebCore::FloatPoint const&, WebCore::FloatPoint const&, WebCore::FloatPoint const&)
     5.95%  SignalSender  libDumpRenderTree.so  [.] WebCore::CubicBezier::split(WebCore::CubicBezier&, WebCore::CubicBezier&) const
     4.70%  SignalSender  libDumpRenderTree.so  [.] WebCore::distanceLine(WebCore::FloatPoint const&, WebCore::FloatPoint const&)
...

And the stack version:
    62.73%  SignalSender  libm.so               [.] sqrtf
            |
            --- WebCore::PathTraversalState::cubicBezierTo(WebCore::FloatPoint const&, WebCore::FloatPoint const&, WebCore::FloatPoint const&)
                WebCore::pathLengthApplierFunction(void*, WebCore::PathElement const*)
                WebCore::Path::apply(void*, void (*)(void*, WebCore::PathElement const*)) const
               |          
               |--50.53%-- WebCore::Path::pointAtLength(float, bool&) const
               |          WebCore::SVGTextLayoutEngine::layoutTextOnLineOrPath(WebCore::SVGInlineTextBox*, WebCore::RenderSVGInlineText*, WebCore::RenderStyle const*)
               |          WebCore::SVGTextLayoutEngine::layoutInlineTextBox(WebCore::SVGInlineTextBox*)
...


62% of the time spent in sqrtf! There may be some low hanging fruit here, such as working with squared length values in curveLength(...) or consolidating distanceLine(...) calls so only a single sqrt is needed in approximateDistance().

[Eric Seidel (no email)]

It appears I added this code... 6 years ago.
http://trac.webkit.org/browser/trunk/Source/WebCore/platform/graphics/PathTraversalState.cpp

[Philip Rogers]

(In reply to comment #1)
> It appears I added this code... 6 years ago.
> http://trac.webkit.org/browser/trunk/Source/WebCore/platform/graphics/PathTraversalState.cpp

I think you can be exonerated... this time ;)

In laying out text on a path in SVGTextLayoutEngine::layoutTextOnLineOrPath(...), both pointAtLength(..) and normalAngleAtLength(..) are called for each character. Each of these methods walks the entire path to determine the character's point&normal. Boo, O(n^2).

We should store the PathTraversalState and have it inch forward for each character instead.

[Philip Rogers]

Created attachment 180265 [details]
Preview patch: Switch to Skia's path measurements, 36% perf improvement

Note: this patch depends on https://code.google.com/p/skia/issues/detail?id=1035 landing.

[Eric Seidel (no email)]

I'd rather fix WebCore's general case, unless you expect every graphics library to implement this?

Why can't we just make WebCore's faster? :)

[Eric Seidel (no email)]

Comment on attachment 180265 [details]
Preview patch: Switch to Skia's path measurements, 36% perf improvement

I guess it's already an SkPath, so maybe this does make sense to let the graphics libraries do this for us.

[Dirk Schulze]

Comment on attachment 180265 [details]
Preview patch: Switch to Skia's path measurements, 36% perf improvement

I actually agree with Erics first comment. We use the PathTraversal logic for SVG which gives us stable results cross platform. There are some edge cases that even Skia does wrong. Using PathTraversal fixed these issues. I think we should work on a cross platform solution instead, where we can relay on the data. This will be more important when we have normalized path logic in SVG.

[Philip Rogers]

Thanks for the reviews!

(In reply to comment #4)
> I'd rather fix WebCore's general case, unless you expect every graphics library to implement this?
> 
> Why can't we just make WebCore's faster? :)

We can't make WebCore's Path implementation much faster because we're hamstrung by bad APIs from our platform paths :( CoreGraphics for example (https://developer.apple.com/library/mac/#documentation/graphicsimaging/Reference/CGPath/Reference/reference.html) only supports the CGApply(..) function which calls a callback function for every segment.

In SVG-land there is a partial solution to the problem: SVG invented the SVGPathByteStream which keeps an external representation of the path that _can_ be iterated over. Sadly, SVGPathByteStream does not expose iteration functions either: SVGPathByteStream uses SVGPathParser to iterate but the parser is missing infrastructure for resuming iteration.

I'd like to discuss this further, but as a trial balloon:
1) We can mirobench the current Path.cpp code and fix any slowness.

2) We could then land the PathSkia::length() function which is a bit faster than Path::length() because it skips converting SkPath segments to Path::PathElementType in Path::apply(...) (TODO: measure this). Path.length() is used outside SVG, such as in RenderBoxModelObject::drawBoxSideFromPath.

3) We could then rework the SVG path byte stream to support resumable iteration. Once that is available, we could switch SVGTextLayoutEngine.cpp to iterate on the SVGPathByteStream instead of using Path::pointAtLength(..) and Path::normalAngleAtLength(..) for each character.

[Eric Seidel (no email)]

Comment on attachment 180265 [details]
Preview patch: Switch to Skia's path measurements, 36% perf improvement

Looking at this again, I realize that the path-applier stuff is really just an option for ports which don't provide this (like CG).  This seems like a good fix to me after a second look.  Dirk?

[Dirk Schulze]

(In reply to comment #8)
> (From update of attachment 180265 [details])
> Looking at this again, I realize that the path-applier stuff is really just an option for ports which don't provide this (like CG).  This seems like a good fix to me after a second look.  Dirk?

I agree with Philip that there is a lot of micro optimizations possible.

But the data for the measure counts a lot here.

- Does the path have a lot of curves or mainly lineTos (given that 'split' is called the first one).
- Does the path have huge curves or curves of average size.

Little changes can have an huge impact dependent on the test. The code for curves uses curveLength, which serializes the splitting and puts them into a queue (thanks to your contributions Eric). This seems to be a fantastic opportunity to parallelize the code in threats and to get a quite good speedup.

Philip tests this feature on SVG text on path. This actually gives us an opportunity to not run the code for every glyph, but get the position and angle of each glyph in one go! I am experimenting with this on multiple markers at the moment. The complexity would shrink from O(n^2) to linear or better (don't see a way to do this with Skia dependent code).

The patch from Philip brings an impressive speedup already for Skia, but I believe we can even be better with platform independent code.

[Ahmad Saleem]

We don't have SkiaPath.cpp in WebKit anymore. So I think it is not applicable.

CCing - Said and Simon for any input.

Marking this as 'RESOLVED INVALID'.

[Said Abou-Hallawa]

The sqrt was used in the static function distanceLine(). The call to sqrt was replaced by std::hypot(), see bug 198483. But I think std::hypot() has to call sqrt anyway. So technically the call to sqrt is still there.

But maybe it is okay to keep it resolved - invalid for now.

[Ahmad Saleem]

Should we make it 'RESOLVED LATER' to make it be more concise that we should look into afterwards?