555877 - Extend cairo API to allow caching of reusable paths

Status: RESOLVED WONTFIX

(Core :: Graphics, enhancement)

Description

[Matt Woodrow (:mattwoodrow)]

User-Agent:       Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.3a4pre) Gecko/20100329 Minefield/3.7a4pre
Build Identifier: 

The new Direct2D API allows us to cache Geometry objects and reuse them on later graphics, so we should extend the cairo API to reflect this. On operating systems that don't support this functionality we need to maintain the cairo_path_t cache of path segments.



Reproducible: Always

Comment 1

[Matt Woodrow (:mattwoodrow)]

Attachment: Quartz Benchmark

I've done some benchmarks using the quartz 2d backend to measure the possible gain of reusing the path instead of recreating it.

The attached benchmark file draws a both a stroke and fill objects and repeats 10000x on each method.

Output is either to pdf file, or just into memory as bitmap format (set the BITMAP define)

Platform.h/.cpp courtesy of David Anderson

Results:

mattwoodrow@Matt-Woodrows-MacBook-Pro ~/cairo/quartz $ ./build.sh 
Slow Loop: 21.680869
Fast Loop: 17.394858
mattwoodrow@Matt-Woodrows-MacBook-Pro ~/cairo/quartz $ ./build.sh 
Slow Loop: 25.653502
Fast Loop: 14.342508
mattwoodrow@Matt-Woodrows-MacBook-Pro ~/cairo/quartz $ ./build.sh 
Slow Loop: 21.904928
Fast Loop: 17.291937
mattwoodrow@Matt-Woodrows-MacBook-Pro ~/cairo/quartz $ ./build.sh 
Slow Loop: 22.574986
Fast Loop: 14.292288

Comment 2

[Matt Woodrow (:mattwoodrow)]

Attachment: Possible new API

Possible new API, and method stubs to handle falling back to the original code where an OS specific implementation isn't available

Comment 3

[Robert O'Callahan (:roc) (email my personal email if necessary)]

The API looks good. Just one thing: instead of returning NULL on error, the cairo way is to return an object "in the error state". Attempts to use this object will put the cairo_t that you try to use it on into an error state. See the path_create_in_error code that's already in cairo.c.

One thing to watch out for when we implement backend-specific magic is what happens when someone does
  cairo_append_retained_path(...);
  cairo_path_t* path = cairo_copy_path(...);
We'll need backend-specific code to extract data from the native path object. And we can't guarantee that the resulting data will actually be exactly what the user put into the path in the first place. We could guarantee that by keeping a copy of the cairo path data *as well as* the native path object, but that seems like it would use memory unnecessarily. (We should keep in mind that some SVG files can have megabytes of path data.)

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

We might want to take the 'data' field out for now, until we add backend-specific code that actually needs it.

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

comments on the test code:
-- probably should factor out the CreateContext/DestroyContext from both loops; use the same context over and over again.
-- we're doing an extra save and restore of the graphics state in 'fastloop', I think.
-- it's also quite hard to see that the retained-path and the normal code are actually drawing the same thing. Might be easier to draw simple shapes that don't require any CTM changes, using just a bunch of constants in CGContextAddLineToPoint/CGContextAddCurveToPoint. Just make up a rounded rectangle or something. Then you could get rid of all the saves/restores.
-- were the numbers you quoted using the BITMAP define? Drawing into a PDF target is probably not that interesting.

Comment 6

[Matt Woodrow (:mattwoodrow)]

Attachment: Cairo API with Quartz Backend, SVG integration

Should be more or less complete (not 100% I've handled all the cairo API calls properly), and passes all SVG reftests.

Very unscientific performance testing on my macbook pro (timing the svg reftest suite on a debug build) suggests around a 10% improvement.

ToDo:

Look into storing retained paths in user co-ordinates instead of device ones.
Fix the tab/space mess.
Add more reftests to try and stress this code more thoroughly.

Comment 7

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Need to invalidate mCachedPath if the path attribute changes. Better add a reftest that catches that bug!

I believe this doesn't catch the cases like nsSVGCircleElement etc. We probably need to do this path caching somewhere else. nsSVGPathGeometryFrame maybe?

Let's have separate patches for cairo, gfx/thebes and layout/svg.

+    	cairo_retained_path_t* mPath;
+		cairo_path_t* mOldPath;
+	} u;
+	bool mOldPath;

"old" is often a bad term to use in variables because its meaning changes over time :-). how about calling the union parts "mRetainedPath" and "mCairoPath" and making the bool an enum?

gfxFlattenedPath::GetLength etc should assert that it's an mCairoPath, I guess?

Otherwise looks awesome. I need to read the cairo code properly.

Comment 8

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+	if (cr->path->path_object != NULL) {
+		assert(cairo_supports_retained_paths(cr->path->path_backend));
+		cr->path->path_backend->separate_path_object(cr, cr->path->path_object);
+		cr->path->path_object = NULL;
+		cr->path->path_backend = NULL;
+	}

This should be moved to some kind of helper function since it's repeated.

cairo_supports_retained_paths should perhaps be private?

Need to document what the backend functions do. 'separate_path_object' feels like it could have a better name, perhaps 'path_object_extract_data' or something.

Basically the structure of the cairo code looks good to me. We could potentially simplify (and deoptimize) things by removing one or two backend functions but it doesn't seem worth it. It's nice how you've avoided adding overhead to cairo_move_to etc.

The other backends need a NULL for copy_path_object. Do we need _cairo_quartz_copy_path_object though? Maybe we should just refcount cairo_retained_path_t? I'm not sure.

     rv = _cairo_quartz_cairo_path_to_quartz_context (path, &stroke);
     if (rv)
         goto BAIL;
 
+	if (path->path_object != NULL)
+		CGContextAddPath(surface->cgContext, (CGMutablePathRef)path->path_object);

Here, we're appending the retained path after the cairo path data, but shouldn't we be prepending it instead? In fact, surely this code should be inside _cairo_quartz_cairo_path_to_quartz_context?

Seems like we have two ways of turning cairo paths into quartz paths now. One builds a CGPath object and the other does it directly to a CGContext. Maybe we should just have the former?

In fact, it would be nice if doing a fill or stroke actually built a Quartz CGPath and stored it as the current path, so if someone does a fill() followed by a copy_retained_path then the extra step is free. I suppose that might rely on the path objects being refcounted. But Quartz and Windows path objects are refcounted internally anyway so maybe we should just do that.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

The Quartz backend code uses CGMutablePathRef as the native path object type. Would there be any advantage to making it a non-mutable path ref?

Comment 10

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Then _cairo_quartz_copy_path_object could just add a ref instead of calling CGPathCreateMutableCopy. And if we can assume that copying the path is cheap like that, and we guarantee that the native path objects are immutable, we can do what I suggested above without explicit addref/release (copy_path_object is addref and free_path_object is release, effectively).

For kCGPathElementAddQuadCurveToPoint, I think you can just represent the quadratic curve as a degenerate cubic Bezier, but I'd have to look up how that works.

Comment 11

[Jeff Muizelaar [:jrmuizel]]

(In reply to comment #10)
> For kCGPathElementAddQuadCurveToPoint, I think you can just represent the
> quadratic curve as a degenerate cubic Bezier, but I'd have to look up how that
> works.

There's code for this in our canvas implementation:

QuadraticCurveTo(float cpx, float cpy, float x, float y)
{

    // we will always have a current point, since beginPath forces
    // a moveto(0,0)
    gfxPoint c = mThebes->CurrentPoint();
    gfxPoint p(x,y);
    gfxPoint cp(cpx, cpy);

    mThebes->CurveTo((c+cp*2)/3.0, (p+cp*2)/3.0, p);

}

Comment 12

[Matt Woodrow (:mattwoodrow)]

Attachment: Cairo Changes

I've currently left out combining the two methods of processing path data into quartz because it would add extra overhead to the normal operation (translating into user co-ordinates and then back again).

Not against adding this if you think it's worthwhile.

Comment 13

[Matt Woodrow (:mattwoodrow)]

Attachment: Thebes integration

Comment 14

[Matt Woodrow (:mattwoodrow)]

Attachment: SVG integration

Comment 15

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+    NULL,  /* merge_path_object */

Fix spacing (several occurrences)

I'm thrilled to see D2D support! But you're not using it for drawing yet?

Can we break up the cairo patch into a patch that adds the core retained-path functionality, followed by another patch to add a Quartz implementation and another patch to add a D2D implementation?

> I've currently left out combining the two methods of processing path data into
> quartz because it would add extra overhead to the normal operation
> (translating into user co-ordinates and then back again).

That's OK.

+static const cairo_retained_path_t _cairo_retained_path_nil = { CAIRO_STATUS_NO_MEMORY, NULL, NULL, NULL };
+                cr->path->path_backend->path_object_extract_data(cr, cr->path->path_object, &cr->path->path_matrix);

80 column limit? I'm actually not sure what the cairo limit is.

Is _cairo_retained_path_create_in_error really needed? We don't store the error in the path anyway, so why can't we just return the nil object?

+                cairo_new_path(cr);
+                cr->path->path_backend->path_object_extract_data(cr, cr->path->path_object, &cr->path->path_matrix);

I'm confused. cairo_new_path is going to wipe out cr->path so why are we extracting data from it here?

+            cairo_path_t *cur = _cairo_path_create (cr->path, cr->gstate);
+            cairo_new_path(cr);
+            path->backend->path_object_extract_data(cr, path->data, &cr->gstate->ctm);
+            cairo_append_path(cr, cur);

Doesn't this append the current path to the given retained path, instead of appending the given retained path to the current path?

+            assert(path->backend == cr->path->path_backend);
+            const void *temp = path->backend->merge_path_object(cr->path->path_object, path->data);
+            cr->path->path_backend->free_path_object(cr->path->path_object);
+            cr->path->path_object = temp;

Seems like this should be using the CTM...

 				       unsigned int height);
 
+
 /* Load all extra symbols */

Stray newline

+    user_to_backend = *matrix;
+    cairo_matrix_multiply (&user_to_backend,
+                    &user_to_backend,
+                    &cr->gstate->target->device_transform);

Skip the first assignment and pass 'matrix' to cairo_matrix_multiply

Where's the code to use the native Quartz path object?

     gfxPath(cairo_path_t* aPath);
-
+	

Don't add trailing whitespace

+        if (path->u.mCairoPath->status == CAIRO_STATUS_SUCCESS && 
+                        path->u.mCairoPath->num_data != 0)

Indent to line up 'path'?

+            cairo_append_path(mCairo, path->u.mCairoPath);

Most one-line if bodies should be in {} except for 'return', 'goto', 'continue', 'break'

+    enum PathType {
+        Path_Retained,
+    Path_Cairo,
+    } mPathType;

Fix indent. Use PathRetained or PATH_RETAINED, but not mixed CamelCase and _

                                          PRInt32         aModType)
 {
+

Unwanted blank line

+  if (aFlags & COORD_CONTEXT_CHANGED | aFlags & TRANSFORM_CHANGED) {
+    mCachedPath = nsnull;

I'd use () around the & expressions because the precedence is not clear.

Clearing the cached path on TRANSFORM_CHANGED is bad. We want to reuse the cached path when the transform changes.

+  if (mCachedPath != nsnull)
+    aContext->AppendPath(mCachedPath);
+  else {

{}

Use "if (mCachedPath)"

+  }
 }
-
+ 

Don't add trailing whitespace

-  nsRefPtr<gfxASurface> tmpSurface =
+  nsRefPtr<gfxASurface> tmpSurface = 

Here too

Comment 16

[Bas Schouten (:bas.schouten)]

Comment on attachment 438945 [details] [diff] [review]
Cairo Changes

I had a look at the D2D part, first of all it's looking pretty good!

Cairo has a 4 indent-width 8 tab-size modeline. This means that only 8 character whitespace gets a tab, then in the case of space % 8 = 4 the 4 remaining characters whitespace are spaces. The patch just seems to use 4 indent-width and 4 tab-size. I realize the cairo standard is a pain :(.

Additionally, D2D has a tendency to mess with the FPU state, we ought to make sure that doesn't happen here (since we're being called from D2D code), the cairo_double_to_fixed makes certain assumptions about FPU state. An example of this can be found in the DirectWrite cairo backend. Perhaps this interface's callers are more careful though.

A couple of nits and suggestions, ofcourse :-).

>diff --git a/gfx/cairo/cairo/src/cairo-d2d-surface.cpp b/gfx/cairo/cairo/src/cairo-d2d-surface.cpp
>--- a/gfx/cairo/cairo/src/cairo-d2d-surface.cpp
>+++ b/gfx/cairo/cairo/src/cairo-d2d-surface.cpp

Overall, I suggest we make the following class a stack based helper. Do not refcount it and just create/destroy it on the stack.

>+class D2DExtractObjectSink : public ID2DGeometrySink
>+{
>+public:
>+	static Create(cairo_t *cr, cairo_matrix_t *matrix)
>+	{
>+		D2DExtractObjectSink *sink = new D2DExtractObjectSink(cr, matrix);
>+		sink->refs = 1;
>+		return sink;
>+	}
>+
>+	HRESULT QueryInterface(REFIID riid, void **ppvObject)
>+	{
>+		return E_NOINTERFACE;
>+	}
The COM gods really don't approve of this! :-)

>+
>+	ULONG AddRef()
>+	{
>+		return ++refs;
>+	}
>+
>+	ULONG Release()
>+	{
>+		refs--;
>+
>+		if (refs <= 0) {
>+			delete this;
>+			return 0;
>+		}
>+
>+		return refs;
>+	}

if (--refs <= 0) ?

>+	void AddLines(const D2D1_POINT_2F *points, UINT pointsCount)
>+	{
>+		for (int i=0; i<pointsCount; i++)
Space around operators.

>+			AddLine(points[i]);
>+	}
>+
>+	void AddQuadraticBezier(D2D1_QUADRATIC_BEZIER_SEGMENT &bezier)
>+	{
>+		assert(false);
>+	}
>+	
>+	void AddQuadraticBezier(D2D1_QUADRATIC_BEZIER_SEGMENT *bezier)
>+	{
>+		AddQuadraticBezier(*bezier);
>+	}
>+
>+	void AddQuadraticBeziers(const D2D1_QUADRATIC_BEZIER_SEGMENT *beziers, UINT bezierCount)
>+	{
>+		for (int i=0; i<bezierCount; i++)
See above.

>+			AddQuadraticBezier(beziers[i]);
>+	}
>+
>+private:
>+	D2DExtractObjectSink(cairo_t *cr, cairo_matrix_t *matrix) cr(cr), user_to_backend(matrix) {}
>+
>+private:	
>+	cairo_t *cr;
>+	cairo_matrix_t *user_to_backend;
>+	UINT refs;
>+};
>+
>+const void 
>+_cairo_d2d_path_object_extract_data(cairo_t *cr, const void *object, cairo_matrix_t *matrix)
>+{
>+	ID2D1PathGeometry *geo = (ID2DPathGeometry *)object;
>+    cairo_matrix_t user_to_backend;
>+	user_to_backend = *matrix;
>+	cairo_matrix_multiply (&user_to_backend,
>+				   &user_to_backend,
>+		                   &cr->gstate->target->device_transform);

Bunch of whitespace issues.

>+	D2DExtractObjectSink *sink = D2DExtractObjectSink::Create(cr, &user_to_backend);
>+	geo->Stream(sink);
>+	sink->Close();
>+	sink->Release();
>+}
>+
>+static const void
>+_cairo_d2d_free_path_object(const void *object)
>+{
>+	ID2D1Geometry *geo = (ID2D1Geometry *)object;
>+	geo->Release();
>+}
>+
>+static const void *
>+_cairo_d2d_merge_path_object(const void *object1, const void *object2)
>+{
>+	ID2D1Geometry *geo1 = (ID2DGeometry *)object1;
>+	ID2D1Geometry *geo1 = (ID2DGeometry *)object2;
>+
>+    ID2D1PathGeometry *d2dpath;
>+    D2DSurfFactory::Instance()->CreatePathGeometry(&d2dpath);
>+    ID2D1GeometrySink *sink;
>+    d2dpath->Open(&sink);

Indentation

>+
>+	geo1->Stream(sink);
>+	d2dpath->CombineWithGeometry(geo2, D2D1_COMBINE_MODE_UNION, NULL, NULL, sink);
>+
>+	sink->Close();
>+	sink->Release();
>+
>+	return d2dpath;
>+}
>+
>+static const void *
>+_cairo_d2d_copy_path_object(const void *object)
>+{
>+	ID2D1Geometry *geo = (ID2D1Geometry *)object;
>+	geo->AddRef();
>+	return geo;
>+}

Comment 17

[Matt Woodrow (:mattwoodrow)]

The comment regarding the merge operation including a CTM transformation has opened a whole new set of problems that I'm struggling with.

The simple case where a finished path is copied, and the later appended to a new (blank) context and immediately filled/stroked is simple (and also the only way used by our SVG layout code).

The corner cases where someone could draw lines using the normal API, append a retained path and then draw more lines are where I'm having problems. We need to maintain the order of these operations and the correct transforms.

The current solutions I have for this are to either keep a list of segments (either a cairo_fixed_path_t of normal operations, or a cached object and it's required transform). We can then process these all in order at drawing time.

Alternatively we can try keep the current path state so that there is at most one cached object and one set of path data, and the cached object is always prepended at drawing time. This is easier in the simple case, but will require a lot of breaking down of cached object, merging two cached objects (How do we take two objects with different required transforms and make one with a single transform that equates to the same thing?) and clearing the current cairo path data so that we can break down the cached object and then re-append the cairo path data.

A much simpler solution (though possibly an unreasonable limitation) would be to not allow modification/extension of retained paths. They could only be applied to contexts with an empty path, and drawing operations/appends after this would be denied.

Does anyone have thoughts on this? None of the above seems like an ideal solution.

As a sidenote the D2D code wasn't meant to be included in this patch. Just prototype code I was working on to take a break from a bug.

Comment 18

[Robert O'Callahan (:roc) (email my personal email if necessary)]

How about the simplest approach: allow a cairo_t to contain either cairo path data (in device coordinates), or a native path object plus a matrix to be used to transform it to device coordinates --- but never both. Any attempt to append a native path object where we already have cairo path data would just convert the native path object to cairo path data and append that. Likewise, any attempt to append cairo path data to a native path object would convert the native path object to cairo path data first.

This would make it hard to optimize stuff like extending a native path object with more path data, but frankly I don't see a use case for that.

Comment 19

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #18)
> Any attempt to append
> a native path object where we already have cairo path data would just convert
> the native path object to cairo path data and append that. Likewise, any
> attempt to append cairo path data to a native path object would convert the
> native path object to cairo path data first.

Both of these would be really easy using a backend method that just takes the native path object and replays the native path object operations using cairo methods ... you already have this method.

Comment 20

[Matt Woodrow (:mattwoodrow)]

Attachment: Fixes made - Cairo front end

Comment 21

[Matt Woodrow (:mattwoodrow)]

Attachment: Fixed made - Quartz backend

Comment 22

[Matt Woodrow (:mattwoodrow)]

Attachment: Fixed made - Thebes integration

Comment 23

[Matt Woodrow (:mattwoodrow)]

Attachment: Fixed made - SVG integration

Comment 24

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Just looking at the backend interface:

+    /*
+     * Converts the current backend specific path object into cairo path 
+     * data and prepends it to the cairo context.
+     */
+    void
+    (*path_object_extract_data) (cairo_t		    *cr);

Shouldn't this be" *appends* it to the cairo context"?

+    const void *
+    (*merge_path_object)	(const void		    *object1,
+				 const void		    *object2);

Hopefully unused.

+    /*
+     * Creates an identical copy of a backend specific path
+     * object
+     */

You might want to mention that since path objects are immutable, a backend can implement copy by simply adding a reference.

The rest looks good.

Comment 25

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+    /*
+     * Converts the current backend specific path object into cairo path 
+     * data and prepends it to the cairo context.
+     */

This needs to make it clear that path_object_extract_data clears the native path object from the context.

+    const cairo_surface_backend_t *backend = cr->gstate->target->backend;

You need to move this up --- C declarations have to be at the start of the block.

+    const void *data;

Call this something like backend_object.

+    /* Now we have only cairo line segments or nothing */

Move this comment up a line so that it's clear the previous code has established this property. And make it clear that it's 'cr' that has only cairo line segments or nothing.

+    /* If theres line data, deconstruct the object */

there's

Somewhere you need to document the invariant that we never have both cairo path data and native path data.

+    const void *path_object;

Call this backend_object to be more clear? You should document that this path object is expected to represent a path in user coordinates. (Of course, internally this could be implemented as a path in device coordinates plus a matrix, or something like that.)

+    const cairo_surface_backend_t *path_backend;

could just be 'backend'

+    cairo_matrix_t path_matrix;

could be 'backend_object_matrix'? Should document that it's the CTM at the time the path object was set.

+     * Releases the backend specific path objects memory or

object's

+     * reduces it's reference count.

its

It's possible that cairo people will object to passing cairo_t values to backend functions. Jeff, what do you think?

Comment 26

[Matt Woodrow (:mattwoodrow)]

Attachment: Cairo front end fixes

Fixed naming/spelling nits
Refactored internal API to not use cairo_t*

Comment 27

[Matt Woodrow (:mattwoodrow)]

Attachment: Quartz backend fixes

Fixed naming/spelling nits
Refactored internal API to not use cairo_t*

Comment 28

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+/* A fixed path can only contain either a backend specific object (with
+ * associated transform matrix and backend surface pointer) or standard
+ * line data

, never both.

+    if (status == CAIRO_STATUS_NO_MEMORY)
+    return (cairo_retained_path_t*) &_cairo_retained_path_nil;

fix indent?

As discussed, when _cairo_retained_path_create creates a native path object, we should first replace the current cairo path in the context with a native path object, then return a copy of that path. This will optimize the case where we grab a retained copy of the path and also use it for filling/stroking.

+	} else { 

Trailing whitespace after "{"

+cairo_clear_path_object(cairo_t *cr)
+cairo_flatten_path_object(cairo_t *cr)

Should be _cairo_clear_path_object, _cairo_flatten_path_object I guess

+	else
+	     _cairo_set_error (cr, CAIRO_STATUS_INVALID_STATUS);

Fix indent

+    if (be->build_path_object != NULL &&
+	be->path_object_extract_data != NULL &&
+	be->free_path_object != NULL &&
+	be->copy_path_object != NULL)

I think we could just check be->build_path_object and assume the others are non-null. No point in impose run-time overhead to catch a basic implementation error of not implementing all those functions. Maybe if build_path_object is non-null we should assert that the others are also non-null.

Comment 29

[Robert O'Callahan (:roc) (email my personal email if necessary)]

For the Thebes integration patch, I think we can rename gfxPath to gfxRetainedPath and have it always use cairo_retained_path_t. gfxFlattenedPath would no longer inherit and would just have a cairo_path_t inside it.

Comment 30

[Robert O'Callahan (:roc) (email my personal email if necessary)]

 				       unsigned int height);
 
+
 /* Load all extra symbols */

Lose this extra blank line

+	CGContextSaveGState(stroke->cgContext);
+	_cairo_matrix_to_quartz_context(stroke->cgContext, &path->backend_object_matrix);
+	CGContextAddPath(stroke->cgContext, (CGPathRef)path->backend_object);
+	CGContextRestoreGState(stroke->cgContext);

Instead of doing a full save/restore, maybe you can just save/restore the matrix? Not sure if that's possible in CoreGraphics.

+typedef struct _quartz_path_stroke {
+    CGMutablePathRef cgPath;
+    cairo_gstate_t *gstate;
+} quartz_path_stroke_t;

Why is this called quartz_path_stroke_t? We're not actually stroking.

Comment 31

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Side note: we discussed whether it makes sense for cairo to always buffer up its path commands from cairo_move_to etc and then convert to native paths later (at draw time, or at cairo_copy_retained_path), or whether it would be better to have backend functions for cairo_move_to etc. I suspect the latter, although we'd need to do some measurements to see. Fodder for future work.

Comment 32

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+
   if (aNameSpaceID == kNameSpaceID_None &&

Lose blank line.

+    nsSVGPathGeometryFrameBase(aContext), mCachedPath(nsnull) {}

You don't need to initialize mCachedPath, nsRefPtrs default to null.

Comment 33

[Matt Woodrow (:mattwoodrow)]

Attachment: Thebes fixes

Renamed gfxPath to gfxRetainedPath and separated gfxFlattenedPath.

Includes required changes to the canvas code.

Comment 34

[Matt Woodrow (:mattwoodrow)]

Attachment: SVG fixes

Style fixes and renaming of gfxPath -> gfxRetainedPath

Comment 35

[Matt Woodrow (:mattwoodrow)]

Attachment: Quartz backend fixes

Style/naming fixes.
Changed a context push/pop to just saving the matrix state.

Comment 36

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 439452 [details] [diff] [review]
Thebes fixes

-    gfxPoint FindPoint(gfxPoint aOffset,
+   gfxPoint FindPoint(gfxPoint aOffset,

Fix indent

Otherwise looks good.

Need additional review on the Thebes API change.

Comment 37

[Matt Woodrow (:mattwoodrow)]

Attachment: Cairo front end fixes

Style fixes.
Creating a retained path now stores this on the context as an optimization.

Comment 38

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 439456 [details] [diff] [review]
Quartz backend fixes

Getting additional review from Jeff since he's more of a cairo guy

Comment 39

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 439457 [details] [diff] [review]
Cairo front end fixes

+	    path->backend = backend;
+
+        /* Use the retained path for the context too */
+        cairo_new_path(cr);
+        cr->path->backend = backend;
+        cr->path->backend_object = backend->copy_path_object(path->backend_object);
+        cr->path->backend_object_matrix = cr->gstate->ctm;

Fix indent

Comment 40

[Joe Drew (not getting mail)]

Comment on attachment 439452 [details] [diff] [review]
Thebes fixes

> /**
>  * Specialization of a path that only contains linear pieces. Can be created
>  * from the existing path of a gfxContext.
>  */
>-class THEBES_API gfxFlattenedPath : public gfxPath {
>+class THEBES_API gfxFlattenedPath {
>+    THEBES_INLINE_DECL_REFCOUNTING(gfxFlattenedPath)
>+

My only issue with this patch is gfxFlattenedPath, which is no longer a gfxPath or gfxRetainedPath. What is it, then? Why can't it be a retained path? Don't we have users that depend on gfxFlattenedPath being a gfx(Retained)Path?

Comment 41

[Robert O'Callahan (:roc) (email my personal email if necessary)]

A retained path is not necessarily flat and does not support the APIs needed to compute distance along the path or tangents at a particular point. SVG uses those features.

Comment 42

[Joe Drew (not getting mail)]

(In reply to comment #41)
> A retained path is not necessarily flat and does not support the APIs needed to
> compute distance along the path or tangents at a particular point. SVG uses
> those features.

Is a flattened path good enough for SVG? Basically, why not have gfxPath and gfxRetainedPath?

Comment 43

[Jeff Muizelaar [:jrmuizel]]

Sorry, I'm late to this discussion but why are we doing an API that copies the retained path from the cairo_t * instead of using a style more like CGPath or ID2D1PathGeometry and constructing a cairo_retained_path_t * object directly?

You could then have something like cairo_apply_retained_path() that would associate the path with output and then you could fill() or stroke() it as necessary. Switching to the immediate mode would then discard the associated retained path.

I'm also interested in the memory overhead of retaining paths. Can we get some measurements there?

Comment 44

[Matt Woodrow (:mattwoodrow)]

At least in our code base there is nothing using gfxFlattenedPath that relies on it being a type of gfxPath.

The API was intended to be very similar to the current cairo_copy_path API, and add retained path support without widespread API changes/additions.

I'm going to work on getting some performance and memory benchmarks done early next week.

Comment 45

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Hm, the cairo side of this patch looks odd to me.  It seems like it would be cleaner and more general to:

- introduce a cairo_path_t, which can be created, modified, etc. without needing a cairo_t (which would then need a surface etc.)
- change cairo's gstate to keep a cairo_path_t around internally
- have cairo_path_t have a backend storage slot, like fonts do, for backend-specific objects
- change the backend api to work in cairo_path_t's, with doubles, and add a path_t-to-fixed_path_t method that will give back a fixed-point path for the backends that want that.  (backends that don't -- Quartz, D2D, SVG, PDF, etc. -- will then have access to actual double values)

Comment 46

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #42)
> (In reply to comment #41)
> > A retained path is not necessarily flat and does not support the APIs needed
> > to compute distance along the path or tangents at a particular point. SVG uses
> > those features.
> 
> Is a flattened path good enough for SVG? Basically, why not have gfxPath and
> gfxRetainedPath?

I assume SVG uses a flattened path because it makes computing tangents and distance along the path particularly easy.

So, use gfxFlattenedPath if you want to do specific geometry calculations, otherwise use gfxRetainedPath to remember paths for performance reasons. I can't think of any usecases for a gfxPath that simply remembers a generic cairo path.

(In reply to comment #43)
> Sorry, I'm late to this discussion but why are we doing an API that copies the
> retained path from the cairo_t * instead of using a style more like CGPath or
> ID2D1PathGeometry and constructing a cairo_retained_path_t * object directly?

What Matt said. We could do this, but it would require adding a bunch of new cairo API and then modifying our code to use that API. Look at the "SVG fixes" patch, it's a really easy change.

> You could then have something like cairo_apply_retained_path() that would
> associate the path with output and then you could fill() or stroke() it as
> necessary. Switching to the immediate mode would then discard the associated
> retained path.

That is exactly how you use cairo_retained_path_t's with the API in these patches.

> I'm also interested in the memory overhead of retaining paths. Can we get some
> measurements there?

Yeah, we'll get that and some speed measurements too before we land. But frankly, if there's a significant speed improvement I think that justifies a reasonable amount of memory overhead.

(In reply to comment #45)
> - introduce a cairo_path_t, which can be created, modified, etc. without
> needing a cairo_t (which would then need a surface etc.)

cairo_path_t is a type that already exists and can't be changed, so I think you need a different name.

Is there a real need for retained paths that are independent of a context? I don't see it. I also don't see how it would work ... how would you know which backend to use?

> - change cairo's gstate to keep a cairo_path_t around internally

The current path should not be part of the gstate; having save and restore affect the current path would be an API change.

> - have cairo_path_t have a backend storage slot, like fonts do, for
> backend-specific objects

That's basically what we've done here.

> - change the backend api to work in cairo_path_t's, with doubles, and add a
> path_t-to-fixed_path_t method that will give back a fixed-point path for the
> backends that want that.  (backends that don't -- Quartz, D2D, SVG, PDF, etc.
> -- will then have access to actual double values)

So you're suggesting introducing a new path type to store the current path with doubles for internal storage, and converting that to either a cairo_retained_path_t or a cairo_path_fixed_t as necessary. That would avoid a double -> fixed -> double round trip for Mac and other platforms whose native path operations want doubles. This would be a performance and possibly quality optimization but needn't affect the API.

Comment 47

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

(In reply to comment #46)
> (In reply to comment #45)
> > - introduce a cairo_path_t, which can be created, modified, etc. without
> > needing a cairo_t (which would then need a surface etc.)
> 
> cairo_path_t is a type that already exists and can't be changed, so I think you
> need a different name.

Sure

> Is there a real need for retained paths that are independent of a context? I
> don't see it. I also don't see how it would work ... how would you know which
> backend to use?

Same as with fonts -- the first backend that you use the retained path with gets to own the internal backend structures.  I guess for SVG it could create the path on first render, though it just seems cleaner to not have it interact with the cairo_t at at all.  I guess I'm not really against it, just from a design perspective it seems better to have it be a standalone object.

> > - change cairo's gstate to keep a cairo_path_t around internally
> 
> The current path should not be part of the gstate; having save and restore
> affect the current path would be an API change.

Sorry, meant the cairo_t itself.  Use the same data structure internally as the public retained_path_t object.

> > - have cairo_path_t have a backend storage slot, like fonts do, for
> > backend-specific objects
> 
> That's basically what we've done here.

Yep, except have it be null by default and have the first backend that uses the path take ownership of it.

> > - change the backend api to work in cairo_path_t's, with doubles, and add a
> > path_t-to-fixed_path_t method that will give back a fixed-point path for the
> > backends that want that.  (backends that don't -- Quartz, D2D, SVG, PDF, etc.
> > -- will then have access to actual double values)
> 
> So you're suggesting introducing a new path type to store the current path with
> doubles for internal storage, and converting that to either a
> cairo_retained_path_t or a cairo_path_fixed_t as necessary. That would avoid a
> double -> fixed -> double round trip for Mac and other platforms whose native
> path operations want doubles. This would be a performance and possibly quality
> optimization but needn't affect the API.

Hm, I'm suggesting having one path type that will use doubles for internal storage, which can be converted to a path_fixed_t.. not sure where the third type comes from.  I'd change the public cairo_* API to use cairo_retained_path_move_to or whatever instead of path_fixed_move_to, and have the software rasterizer convert to fixed point all at once as needed (or whatever other backends also want fixed point).

It doesn't affect the API, it would just get rid of the double->fixed->double conversions and make the backend APIs cleaner... most backends don't really want to deal with fixed point.

Comment 48

[Robert O'Callahan (:roc) (email my personal email if necessary)]

If we're going to streamline the conversion of cairo path data to backend path data, then see comment 31. I think the best way forward would be to eliminate the accumulation of temporary path data completely, by making cairo_move_to etc support specialization by backends. The path segments would be accumulated directly into backend-specific path objects. That's almost certainly faster than collecting entire paths in memory and then doing another pass to convert them to native path objects (implicitly with existing cairo APIs, or explicitly with Matt's new APIs). But if we do that, I think it should be done as a followup to this bug.

We expose font backends in cairo API because applications need to hand native font objects to cairo, and to some extent you can mix-and-match font backends with surface backends. Those issues don't apply with paths. I don't see any use-cases for path-backend-specific API; for example we have no need to import or export D2D paths or Quartz paths.

So I remain unconvinced that adding a bunch of new APIs to support creating retained path objects without referencing a cairo_t would be worth the extra API surface.

Comment 49

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

As per irc conversation -- now that I thought about it more, I'm not really strongly against the API as proposed here.  If I were writing it, I would've done it with a more generic object, but I'm not, and there's really no good reason to prefer one or the other, other than the ability to create a path without a cairo_t.  I'm willing to accept that that's not a strong use case.

However!  I would suggest running this API past cairo folks, if you haven't already, to see what their thoughts are... we'll want to get this into upstream as soon as we can, so better catch any issues there early on.

Comment 50

[Matt Woodrow (:mattwoodrow)]

I submitted the original API proposal to the cairo mailing list without any real objections. I can send a follow-up email linking to the current set of patches (in particular the internal API) if you feel this is worthwhile.

Comment 51

[Matt Woodrow (:mattwoodrow)]

Attachment: Performance test

I've been working on some basic performance and memory usage measurements.

The attached SVG tiger image includes code to rotate the image for 30 seconds (starts when you click on it) and measures the number of frames drawn during this period. I'm getting around a 5% improvement in my tests using this.

Basic profiling using Shark suggests the majority of the CPU time is being spent within the fill/stroke operations.

For memory usage, I have an auto generated SVG file containing 100 1000 point polygons. (Nigh unreadable .py file and 2.4mb .svg available upon request). Activity Monitor's reported 'Real Memory' value is exactly the same for both builds using this file.
Rendering takes around 10 seconds, so I think it's about at the limit of what we can reasonably be expected to handle.

Comment 52

[Matt Woodrow (:mattwoodrow)]

I also had a look at the disassembly for CGContextAddPath. It calls into CGPathAddPath which appears to do an O(n) copy of the contained data.

There doesn't appear to be any way we can directly insert our retained path object into the context without resorting to unreliable reverse engineered offsets (which I'd enjoy way too much).

Comment 53

[Robert O'Callahan (:roc) (email my personal email if necessary)]

It sounds like Quartz isn't really doing any optimizations with retained paths, but using retained paths gives us a small win by avoiding SVG path parsing and possible some cairo overhead.

So the interesting case will be D2D.

Comment 54

[Matt Woodrow (:mattwoodrow)]

Attachment: Bug fixed

Now adds in ctm_inverse translation to the cached path when required (stroking).

Do I need a re-review on this?

Comment 55

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Not from me.

Comment 56

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Still needs review from Jeff though.

Comment 57

[Matt Woodrow (:mattwoodrow)]

Attachment: Rebased against tip

Includes required indent fix from previous patch

Comment 58

[Matt Woodrow (:mattwoodrow)]

Attachment: Cairo front end bug fix

Fixes indent problem.

backend_object_matrix now includes the current device transform as well as the ctm. Required as gstate_backend_to_user was removing this transform during creation of the backend object.

Comment 59

[Matt Woodrow (:mattwoodrow)]

Attachment: First attempt at d2d backend

Appears to fail approximately the same reftests as without the patch. Appeared to fix one failing test and replace it with two new fails. Will investigate further tomorrow.

I ran into what appeared to be bug 558048 when trying to run the spinning tiger 'performance test'. Loading the browser in a debugger seems to have fixed this (including following runs outside the debugger).
Frame rate shows a very consistent 5% gain with retained paths enabled. Quartz was varying from nothing to 4-5%.

Also working on an updated SVG patch which includes a pref to easily enable/disable path caching.

Comment 60

[Jeff Muizelaar [:jrmuizel]]

(In reply to comment #59)
> I ran into what appeared to be bug 558048 when trying to run the spinning tiger
> 'performance test'. Loading the browser in a debugger seems to have fixed this
> (including following runs outside the debugger).
> Frame rate shows a very consistent 5% gain with retained paths enabled. Quartz
> was varying from nothing to 4-5%.

How much of this gain is from retaining the paths vs. just setting the path more efficiently. i.e. is the measured gain here just measuring the performance cost of the cairo overhead of converting to fixed point, creating the path buffer, iterating over the path buffer and converting back to floating point?

Comment 61

[Jeff Muizelaar [:jrmuizel]]

We should also try to get api review from Carl.

Comment 62

[Jeff Muizelaar [:jrmuizel]]

(In reply to comment #48)
> If we're going to streamline the conversion of cairo path data to backend path
> data, then see comment 31. I think the best way forward would be to eliminate
> the accumulation of temporary path data completely, by making cairo_move_to etc
> support specialization by backends. The path segments would be accumulated
> directly into backend-specific path objects. That's almost certainly faster
> than collecting entire paths in memory and then doing another pass to convert
> them to native path objects (implicitly with existing cairo APIs, or explicitly
> with Matt's new APIs). But if we do that, I think it should be done as a
> followup to this bug.

The API proposed here makes streamlining this more difficult. If we're in a situation where cairo_line_to() etc. redirects directly to CGContextAddLineToPoint(), I don't see a way for us to get a CGPath back from the CGContext.

Comment 63

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

There actually is a private CG API to do it, but I don't think having cairo_line_to and friends call in directly to backend-specific functions is a good idea at all; it breaks the cairo surface/backend abstraction pretty badly, and I don't think we want to go down that route.  I can /maybe/ see it being ok if we also create a cairo path at the same time, but is the perf hit of recreating the path on the backend significant?

Comment 64

[Benjamin Otte]

I think I agree with roc in that a path backend with move_to/line_to/... calls is a good idea. And that's because a fixed path is already a specialization of the path concept. There have been various complaints from people using svg/pdf that want to preserve accuracy of paths and if those backends had a separate path object that they could use, it'd make them very happy.

Also, I would make the path object have their own path backends instead of the current patch which glues them to the surface backend, so they become independant, which makes sense as you might want to retain paths for longer than the surface that was used to create them.

Comment 65

[Jeff Muizelaar [:jrmuizel]]

(In reply to comment #63)
> There actually is a private CG API to do it, but I don't think having
> cairo_line_to and friends call in directly to backend-specific functions is a
> good idea at all; it breaks the cairo surface/backend abstraction pretty badly,
> and I don't think we want to go down that route.

It does break the surface/backend abstraction, but I'm not sure that abstraction fits that well with d2d and quartz. 

> I can /maybe/ see it being ok
> if we also create a cairo path at the same time, but is the perf hit of
> recreating the path on the backend significant?

Somewhat. With:
http://people.mozilla.com/~jmuizelaar/world-map-it.html
9.5% of _cairo_quartz_surface_fill() is in _cairo_quartz_path_to_quartz_context()

and with:
http://people.mozilla.org/~jmuizelaar/tiger.svg
2% of _cairo_quartz_surface_fill() is in _cairo_quartz_path_to_quartz_context()

This does not include the time spent making the cairo path buffer. On the world-map example 5% of the total time is spent in _moz_cairo_line_to.

Comment 66

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

(In reply to comment #65)
> > I can /maybe/ see it being ok
> > if we also create a cairo path at the same time, but is the perf hit of
> > recreating the path on the backend significant?
> 
> Somewhat. With:
> http://people.mozilla.com/~jmuizelaar/world-map-it.html
> 9.5% of _cairo_quartz_surface_fill() is in
> _cairo_quartz_path_to_quartz_context()
> 
> and with:
> http://people.mozilla.org/~jmuizelaar/tiger.svg
> 2% of _cairo_quartz_surface_fill() is in _cairo_quartz_path_to_quartz_context()

Oof -- but look at the work that function has to do.  It's horribly inefficient, doing a function call again for every path operation, has to do various branches, and has to convert from fixed to double.  I bet all of that would just go away if we just iterated through the path buffers without path_fixed_interpret, and if the path was stored as doubles to begin with.

The one thing that wouldn't is the calls to transform_point when stroking; having that go away would be a good win, though can't we get a similar effect by just changing the CG matrix while we're appending the path, since CG presumably does the same multiplication?

Comment 67

[Jeff Muizelaar [:jrmuizel]]

(In reply to comment #66)
> Oof -- but look at the work that function has to do.  It's horribly
> inefficient, doing a function call again for every path operation, has to do
> various branches, and has to convert from fixed to double.  I bet all of that
> would just go away if we just iterated through the path buffers without
> path_fixed_interpret, and if the path was stored as doubles to begin with.

What's the advantage to storing the path externally at all? I suppose it makes
implementing cairo_copy_path() easier but other than that I don't see much.

Comment 68

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #60)
> How much of this gain is from retaining the paths vs. just setting the path
> more efficiently. i.e. is the measured gain here just measuring the performance
> cost of the cairo overhead of converting to fixed point, creating the path
> buffer, iterating over the path buffer and converting back to floating point?

All of it. See comment #53.

I totally agree we want to optimize cairo_move_to etc to just call backend functions of some kind and not buffer any path data if possible. Since on Quartz at least, adding a CGPath to a CGContext is O(N) in the size of the path data, the optimal implementation of cairo_move_to would be to just call CGContextMoveTo. So the path data would be hidden in the CGContext and we'd have to call CGContextCopyPath to get it for cairo_copy_retained_path, but that's OK, because we'd have to call it for cairo_copy_path anyway, so the current proposed retained_path API does not add new platform constraints here. So I still don't see any problem with the proposed API.

I also agree that we have a big problem here with the way we map cairo's surface/context abstractions into Quartz. Using multiple cairo_ts to rendering into a Quartz surface is simply going to break if we move cairo path state into the surface's CGContext. This is a much bigger problem that I'm not sure how to deal with. However we solve it, I don't see it breaking or being particularly constrained by the retained-path API we're proposing here. So I would like to treat these as separate issues. Assuming we can get the big wins that Bas posted about, I'd like to reap those wins by improving the D2D patch here, get the stuff landed, and move on to the other issues.

BTW I agree with Benjamin in the second paragraph of comment #64, internally we should have a separate path backend because it doesn't make sense to call surface backend functions when no surface is involved.

Comment 69

[Matt Woodrow (:mattwoodrow)]

Attachment: SVG changes - Pref added

Added a pref 'gfx.cached_paths' to easily enable/disable path caching.

Comment 70

[Matt Woodrow (:mattwoodrow)]

Attachment: Cairo front end - Refactored path backend

Refactored internal retained path API to have a separate backend pointer.

Comment 71

[Matt Woodrow (:mattwoodrow)]

Attachment: Quartz backend - Updated for new retained paths backed

Comment 72

[Matt Woodrow (:mattwoodrow)]

Attachment: D2D backend - Retained path backend changes

Updated D2D backend to support the new retained path internal API.
Couple of RefPtr fixes.

Comment 73

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 440938 [details] [diff] [review]
SVG changes - Pref added

I don't think we should add the pref --- this should just work for everyone.

Feel free to attach a separate patch that just adds the pref, so that anyone doing perf comparisons can take that patch and build with it.

Comment 74

[Matt Woodrow (:mattwoodrow)]

Attachment: SVG - Pref removed

Comment 75

[Matt Woodrow (:mattwoodrow)]

Attachment: Optional pref for easier testing

Comment 76

[Andrea Canciani]

(In reply to comment #66)
> The one thing that wouldn't is the calls to transform_point when stroking;
> having that go away would be a good win, though can't we get a similar effect
> by just changing the CG matrix while we're appending the path, since CG
> presumably does the same multiplication?
I have a branch that does exactly this (it removes the need for multiplication when stroking and thus simplifies the path conversion code). It's here
http://cgit.freedesktop.org/~ranma42/cairo/log/?h=wip/quartz-path
Reviewing (both for correctness and performance) would be greatly appreciated.

Comment 77

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

The quartz-path branch work looks great and is basically what I had in mind -- just wasn't 100% convinced it would work (because I'm not sure why it wasn't done that way in the first place :)  If it passes tests, looks good to me.

Comment 78

[Andrea Canciani]

(In reply to comment #77)
> The quartz-path branch work looks great and is basically what I had in mind --
> just wasn't 100% convinced it would work (because I'm not sure why it wasn't
> done that way in the first place :)  If it passes tests, looks good to me.
It passed the test even after rebasing, thus I committed it to master.
My tests (cairo-perf-trace) show no performance improvement (on ppc, Mac OS X 10.5) and I don't expect big differences on x86, anyway the code looks simpler and independent from the ctm (which might be quite interesting for the retained shape optimization).

Comment 79

[Jeff Muizelaar [:jrmuizel]]

Am I correct in assuming that this bug is on hold for now?

Comment 80

[Robert O'Callahan (:roc) (email my personal email if necessary)]

No, I'd still like to land it.

Matt is working to extend Chris Wilson's cairo_backend_t work to cover Quartz. But we don't expect that to impact the API introduced here, and it's a much bigger change. I don't want to block this bug on that work.

Comment 81

[Joe Drew (not getting mail)]

Comment on attachment 440701 [details] [diff] [review]
Rebased against tip

Note: I am not a superreviewer, but I consider roc to have delegated his superreview capacity to me.

Only change I'd like is for the comments above gfxFlattenedPath to be a little more explicit. It's not a specialization any more, it's its own thing, with different capabilities (and different limitations). Just write out what those capabilities and deficiencies are vs. gfxRetainedPath.

Comment 82

[Matt Woodrow (:mattwoodrow)]

We are no longer planning on persuing this path for improved graphics performance.

Comment 83

[Bas Schouten (:bas.schouten)]

Comment on attachment 440942 [details] [diff] [review]
D2D backend - Retained path backend changes

Review of attachment 440942 [details] [diff] [review]:
-----------------------------------------------------------------

We won't be doing this.