Bug 152939 - Cache the Path instead of creating it every time it is required
Summary: Cache the Path instead of creating it every time it is required
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Animations (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Said Abou-Hallawa
URL:
Keywords:
Depends on: 153109 153279
Blocks:
  Show dependency treegraph
 
Reported: 2016-01-08 19:22 PST by Said Abou-Hallawa
Modified: 2016-02-01 11:45 PST (History)
11 users (show)

See Also:


Attachments
Patch (34.25 KB, patch)
2016-01-08 20:08 PST, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (37.85 KB, patch)
2016-01-08 20:45 PST, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
css-bouncing-clipped-rects-without-path-caching (1.42 MB, application/zip)
2016-01-14 14:25 PST, Said Abou-Hallawa
no flags Details
css-bouncing-clipped-rects-with-path-caching (1.62 MB, application/zip)
2016-01-14 14:25 PST, Said Abou-Hallawa
no flags Details
profile-comparison (547.55 KB, image/png)
2016-01-14 14:26 PST, Said Abou-Hallawa
no flags Details
Patch (14.55 KB, patch)
2016-01-21 18:31 PST, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (18.62 KB, patch)
2016-01-25 13:42 PST, Said Abou-Hallawa
no flags Details | Formatted Diff | Diff
Patch (18.40 KB, patch)
2016-02-01 10:46 PST, 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 Said Abou-Hallawa 2016-01-08 19:22:09 PST
At least on Mac, creating the Path is an expensive operation. We should cache it since it does depends only on the geometry of the shape.
Comment 1 Said Abou-Hallawa 2016-01-08 20:08:07 PST
Created attachment 268604 [details]
Patch
Comment 2 Said Abou-Hallawa 2016-01-08 20:45:24 PST
Created attachment 268607 [details]
Patch
Comment 3 Simon Fraser (smfr) 2016-01-08 21:42:35 PST
Comment on attachment 268607 [details]
Patch

This looks reasonable, but I think you need to break it up, and it has one serious problem.

I suggest breaking it up into the KeyedMRUCache/CFLocaleCache changes. In a second commit, make the CGColor cache change. In a third commit, start caching paths.

The big problem is that you can't pass Path& around. You never know if someone is going to hold onto a ref to that Path which outlives the cache entry.
Comment 4 Simon Fraser (smfr) 2016-01-08 21:46:20 PST
Also, Paths are mutable.
Comment 5 Said Abou-Hallawa 2016-01-14 14:25:10 PST
Created attachment 269004 [details]
css-bouncing-clipped-rects-without-path-caching
Comment 6 Said Abou-Hallawa 2016-01-14 14:25:45 PST
Created attachment 269005 [details]
css-bouncing-clipped-rects-with-path-caching
Comment 7 Said Abou-Hallawa 2016-01-14 14:26:26 PST
Created attachment 269007 [details]
profile-comparison
Comment 8 Said Abou-Hallawa 2016-01-14 14:33:50 PST
I attached Instruments profiles for running css-bouncing-clipped-rects test with and without caching the path. The profiles show 5% gain when running this test and caching the path versus not caching it. However the animometer did not show big difference and actually sometimes the score is worse with the path caching. I guess this is because measuring the FPS with css animation is unreliable. It involves layout followed by display. Maybe this is what we need to investigate next since the raw FPS shows unpredictable results; e.g. the FPS sometimes is way above 60 FPS which is not true. And this seems to happen every time we change the test contents which means running the layout.
Comment 9 Said Abou-Hallawa 2016-01-21 18:31:37 PST
Created attachment 269534 [details]
Patch
Comment 10 Darin Adler 2016-01-24 14:37:40 PST
Comment on attachment 269534 [details]
Patch

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

> Source/WebCore/rendering/ClipPathOperation.h:109
> -    const Path pathForReferenceRect(const FloatRect& boundingRect)
> +    const Path& pathForReferenceRect(const FloatRect& boundingRect)
>      {
> -        Path path;
> -        m_shape.get().path(path, boundingRect);
> -        return path;
> +        return m_shape.get().path(boundingRect);
>      }

I suggest fixing the formatting here to be a one-liner like the other functions. My style preference is to have only one-liners in the class definition. Any inline that is longer can be separate outside the class definition after it. This helps the class definition stay readable.

> Source/WebCore/rendering/style/BasicShapes.cpp:67
> +template<>
> +struct TinyLRUCachePolicy<FloatRect, Path> {

I suggest putting template<> on the same line here and below.

> Source/WebCore/rendering/style/BasicShapes.cpp:68
> +    static TinyLRUCache<FloatRect, Path>& cache()

It’s a little “clever” to make these create functions be members of the policy class, in a bad way. It makes it confusing at the call sites that use the cache; the policy has nothing to do with the fact that there is a shared global cache and every time I read it, I find it unnecessarily oblique. These functions could just be free functions with clear names instead, and I think that would be better. It’s “forced” to make them members of the class that supplies the policy.

Let me say this even more strongly: There’s nothing that makes it clear that the FloatRect->Path cache is for circles and ellipses. So this function should be named ellipsePathCache() and it should not be a member of the policy struct. Same for the rest.

Or there’s yet another way to say it: Did you intentionally make the circle and ellipse implementations share a cache? If so, you should state that. It’s not good to have that be a subtle thing.

> Source/WebCore/rendering/style/BasicShapes.cpp:182
> +    FloatRect rect(centerX - radius + boundingBox.x(), centerY - radius + boundingBox.y(), radius * 2, radius * 2);
> +    return TinyLRUCachePolicy<FloatRect, Path>::cache().get(rect);

I think this would read nicely without the local variable. Maybe the line would be a bit long.

> Source/WebCore/rendering/style/BasicShapes.cpp:238
> +    FloatRect rect(centerX - radiusX + boundingBox.x(), centerY - radiusY + boundingBox.y(), radiusX * 2, radiusY * 2);
> +    return TinyLRUCachePolicy<FloatRect, Path>::cache().get(rect);

Ditto.

> Source/WebCore/rendering/style/BasicShapes.cpp:335
> +    static NeverDestroyed<Path> path;

Requires a comment to explain why this is needed and also why it’s OK.

Could also avoid this by having the LRU cache key be a struct that includes include both the byte stream and the bounding box location.
Comment 11 Simon Fraser (smfr) 2016-01-24 18:56:56 PST
Comment on attachment 269534 [details]
Patch

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

> Source/WebCore/rendering/style/BasicShapes.cpp:124
> +        Path path;
> +        path.moveTo(points[0]);
> +
> +        for (size_t i = 1; i < points.size(); ++i)
> +            path.addLineTo(points[i]);
> +        
> +        path.closeSubpath();
> +        return path;

This should use polygonPathFromPoints().
Comment 12 Said Abou-Hallawa 2016-01-25 13:42:54 PST
Created attachment 269787 [details]
Patch
Comment 13 Said Abou-Hallawa 2016-01-25 13:51:15 PST
Comment on attachment 269534 [details]
Patch

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

>> Source/WebCore/rendering/ClipPathOperation.h:109
>>      }
> 
> I suggest fixing the formatting here to be a one-liner like the other functions. My style preference is to have only one-liners in the class definition. Any inline that is longer can be separate outside the class definition after it. This helps the class definition stay readable.

Done. This function is now one-liner inside the class.

>> Source/WebCore/rendering/style/BasicShapes.cpp:68
>> +    static TinyLRUCache<FloatRect, Path>& cache()
> 
> It’s a little “clever” to make these create functions be members of the policy class, in a bad way. It makes it confusing at the call sites that use the cache; the policy has nothing to do with the fact that there is a shared global cache and every time I read it, I find it unnecessarily oblique. These functions could just be free functions with clear names instead, and I think that would be better. It’s “forced” to make them members of the class that supplies the policy.
> 
> Let me say this even more strongly: There’s nothing that makes it clear that the FloatRect->Path cache is for circles and ellipses. So this function should be named ellipsePathCache() and it should not be a member of the policy struct. Same for the rest.
> 
> Or there’s yet another way to say it: Did you intentionally make the circle and ellipse implementations share a cache? If so, you should state that. It’s not good to have that be a subtle thing.

I agree. I would be in trouble if two different path contents are created with the same key type. For example if we had a rectangle path, specializing the policy template for the FloatRect would not work for both ellipse path and rectangle path.

So I added the policy type as an argument to the TinyLRUCache. This should the code more readable and will allow creating caches for different value types for the same key type.

>> Source/WebCore/rendering/style/BasicShapes.cpp:124
>> +        return path;
> 
> This should use polygonPathFromPoints().

Done. Thanks for pointing this out.

>> Source/WebCore/rendering/style/BasicShapes.cpp:182
>> +    return TinyLRUCachePolicy<FloatRect, Path>::cache().get(rect);
> 
> I think this would read nicely without the local variable. Maybe the line would be a bit long.

Done.

>> Source/WebCore/rendering/style/BasicShapes.cpp:238
>> +    return TinyLRUCachePolicy<FloatRect, Path>::cache().get(rect);
> 
> Ditto.

Done.

>> Source/WebCore/rendering/style/BasicShapes.cpp:335
>> +    static NeverDestroyed<Path> path;
> 
> Requires a comment to explain why this is needed and also why it’s OK.
> 
> Could also avoid this by having the LRU cache key be a struct that includes include both the byte stream and the bounding box location.

A new struct named SVGPathTranslatedByteStream is now used as the LRU cache key for the translated SVGPathByteStream.
Comment 14 Darin Adler 2016-01-30 11:56:59 PST
Comment on attachment 269787 [details]
Patch

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

> Source/WebCore/platform/graphics/FloatRoundedRect.h:146
> +    return a.topLeft() != b.topLeft() || a.topRight() != b.topRight() || a.bottomLeft() != b.bottomLeft() || a.bottomRight() != b.bottomRight();

I prefer:

    return !(a == b);

> Source/WebCore/platform/graphics/FloatRoundedRect.h:156
> +    return a.rect() != b.rect() || a.radii() != b.radii();

Ditto.

> Source/WebCore/rendering/style/BasicShapes.cpp:73
> +    bool operator!=(const SVGPathTranslatedByteStream& other) const { return other.m_offset != m_offset || other.m_rawStream != m_rawStream; }

I prefer:

    return !(*this == other);

> Source/WebCore/rendering/style/BasicShapes.cpp:89
> +class EllipsePathPolicy : public TinyLRUCachePolicy<FloatRect, Path> {
> +public:

Could use struct for this. Often we do.

> Source/WebCore/rendering/style/BasicShapes.cpp:101
> +class RoundedRectPathPolicy : public TinyLRUCachePolicy<FloatRoundedRect, Path> {
> +public:

Could use struct for this. Often we do.

> Source/WebCore/rendering/style/BasicShapes.cpp:113
> +class PolygonPathPolicy : public TinyLRUCachePolicy<Vector<FloatPoint>, Path> {
> +public:

Could use struct for this. Often we do.

> Source/WebCore/rendering/style/BasicShapes.cpp:120
> +class TranslatedByteStreamPathPolicy : public TinyLRUCachePolicy<SVGPathTranslatedByteStream, Path> {
> +public:

Could use struct for this. Often we do.

> Source/WebCore/svg/SVGPathByteStream.h:60
> +        return m_data != other.m_data;

I prefer:

    return !(*this == other);
Comment 15 Said Abou-Hallawa 2016-02-01 10:46:38 PST
Created attachment 270400 [details]
Patch
Comment 16 WebKit Commit Bot 2016-02-01 11:45:24 PST
Comment on attachment 270400 [details]
Patch

Clearing flags on attachment: 270400

Committed r195970: <http://trac.webkit.org/changeset/195970>
Comment 17 WebKit Commit Bot 2016-02-01 11:45:31 PST
All reviewed patches have been landed.  Closing bug.