[cairo] [PATCH] Performance patch for bo intersections

[Carl Worth]

On Tue, 12 Dec 2006 18:00:22 +0000, Baz wrote:
> Ok, here's a tidied up patch.

Thanks. That's much better.

> xlib-rgba    paint_solid_rgba_source-256    0.48 5.60% ->   0.22
> 5.30%:  2.20x speedup

And that's a lovely result! This is a _really_ common operation, (for
example, erasing a window to a solid background color), so it should
help a lot to have it be twice as fast.

> I can't explain those regressions - they don't seem to hit the changed
> code? Running text_similar_rgb_over with 10x more iterations seems to
> show less of a slowdown.

Yes, this is likely just noise. I designed cairo-perf-diff  so that
you can incrementally run it to add more samples for a single test to
try to get things that you think are noise to just disappear. So that
should be as easy as:

	./cairo-perf-diff -f HEAD -- text

or so. That should be nice and quick to run and after a time or two
should clean up the reports nicely.

> Prevent full intersection checks being done when the bounding boxes
> of line segments do not overlap; also prevent the intersection check
> when the intersection would be at a segment endpoint.

Thanks for the commit message.

By the way, the word "also" is a red flag for me in a commit
message. It says you're doing two logically independent things, so the
patch really should be split into two separate commits. This will help
for things like bisecting later, or if one half of the patch needs to
be cherry-picked or reverted or what have you.

I definitely like the patch overall, and just have a couple of style
things to nitpick:

> +    /* Sort the points left-to-right. This simplifies the
> +     * horizontal overlap and coincident endpoint tests.
> +     */
> +    if (left->top.x < left->bottom.x) {
> +      l1 = &(left->top);
> +      r1 = &(left->bottom);
> +    } else {
> +      l1 = &(left->bottom);
> +      r1 = &(left->top);
> +    }

I really can't accept the way the l1,r1,l2,r2 naming convention
here. We're taking edges named "left" and "right" and then assigning
to these names, but "left" and "right" do not correlate with "l" and
"r", (instead "left" and "right" correlate to "1" and "2"). That's
really confusing.

You could use l1 and l2 for the two extremal points (in x) of the left
edge, (and r1 and r2 for the right edge). That would be a lot less
confusing.

But you might also go one more step and make the names even more
descriptive. Something like:

	if (left->top->x < left->bottom.x) {
	    left_min_in_x = &(left->top);
	    left_max_in_x = &(left->bottom);
	} else {
	    left_min_in_x = &(left->bottom);
	    left_max_in_x = &(left->top);
	}

Or something like that to avoid the reader having to figure out that 1
and 2 are mapped to a left-to-right sort across the X axis.

> +    /* Test for horizontal overlap */
> +    if (r1->x < l2->x || r2->x < l1->x) {
> +      return;
> +    }

I don't like that comment as the test is actually for the _absence_ of
horizontal overlap. Better might be something like:

	/* Trivially reject edges with no horizontal overlap of
	 * bounding boxes--no intersection is possible. */

> +    /* End points cannot be intersections. However, coincident
> +     * endpoints are common in polygonal drawings.
> +     */

I'd say:

	/* By definition, endpoints are not intersections, (see the
	 * infinitesimal shortening rule). Coincident endpoints are common, so
	 * detect them and trivially reject without needing to execute
	 * the full intersection calculation.
	*/

And as I said above, this piece should be separated into a new commit.

Very nice work, thanks Brian.

-Carl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20061212/e836dc5c/attachment.pgp