[cairo] Some performance investigations

[M Joonas Pihlaja]

Hi cairo-list,

I was looking into the new tessellator, inspired by Chris
Nuernberger's post re: 128 bit arithmetic, and would appreciate
some feedback on the plan below regarding integrating the
optimisation[1] into cairo.  I also have some questions about the
current implementation.

I realise that with the move to 24.8 from 16.16 fixed point
coordinates, this might not really be a high priority anymore,
though.

First the questions:

1. It seems to me that the new tessellator code only works for
x/y coordinates in the range [-2^29+1, 2^29-1] (when viewing the
fixed point coordinates as integers) due to the two additional
guard bits introduced in the new tessellator.  May I assume that
this restriction is a hard one that isn't going to change in the
near future?

2.  Similarly, are the

    /* XXX: We're assuming here that dx and dy will still fit in 32
     * bits. That's not true in general as there could be overflow. We
     * should prevent that before the tessellation algorithm
     * begins. */

comments in the code going to be valid for the moment?  These
comments apply to computing the offset vector from the start of a
polygon edge to its end.

3. In _cairo_quorem128_32_compare(), the function always compares
a > b if the integer parts are equal and the remainder part of a
is non-zero.  But couldn't _cairo_int128_divrem()  return a
negative remainder if the numerator is < 0?  I think that the
division operation should be normalised so that the remainder is
always non-negative, and that rounding to integer coordinates
should do round-to-negative-infinity throughout the new
tessellator code.  I'm not sure, but it seems to me that the
current rounding might have symmetry issues around the axes.

So if the answer to the first or second questions is "no, those
are temporary assumptions", then the plan below for removing the
128/128 bit divisions won't work.

The way I read _cairo_bo_edge_intersect(), and specifically the
way the cairo_bo_point_quorem128_t results from intersect_lines()
are used, it looks like:

  a) The only place where the high 96 bits of the intersection
point's integer part is used is in
_cairo_bo_edge_contains_point_quorem128() to make sure that the
intersect is within the edges.

  b) The only place where any bits of the remainder are used is
in _cairo_quorem128_32_compare(), and even there only the
zero/nonzeroness of the remainder is relevant.

So really, couldn't the cairo_quorem128_t types that represent an
intersection point's coordinates be changed to something like:

typedef struct _cairo_intersect_ordinate {
	uint32_t ordinate;		/* includes guard bits. */

	/* A status code to indicate the result of the
	 * division in intersect_lines() that produced this
	 * ordinate :*/
	enum {
		EXACT,			/* no remainder. */
		INEXACT,		/* positive remainder. */
		OVERFLOW		/* quotient doesn't fit in 32 bits. */
	} exactness;
} cairo_intersect_ordinate_t

As _cairo_bo_edge_contains_point_quorem128() can currently never
return true for intersection points that overflow 32 bits, thanks
to the range of the edges' coordinates, I believe this would be
safe.

Finally, the 128/128 bit divisions in intersect_lines() look like
they're only ever being called[2] for a < 95+1 bit signed
numerator and a 63+1 bit signed denominator, so they could be
placed with a more specialised division that returns a
cairo_intersect_ordinate_t instead.

Does that sound like a reasonable plan?  I'm not 100% sure I
caught all the corner cases in the current implementation.

Cheers,

Joonas


[1] So far, I'm assuming it's going to be an optimisation, but it
does need thorough testing for correctness before any integration
into cairo.

[2] In intersect_lines(), dx1, dx2, dy1, dy2 are assumed to fit
into 31+1 bit signed integers, so den_det, a_det, b_det all fit
into < 63+1 bits.  Then the 128/128 bit divisions take a
numerator of the form

	det64_128(a_det, dx1,
		  b_det, dy1);

which fits into < 95+1 bits afaict, and denominator den_det.