| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
We frequently compare neighbouring edges for their colinearity (in case
we can skip over them in the active list) so we can record the last
comparison and reuse the result next time.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
Albeit it too large for gcc to automatically inline, it is only used
from within a single function. Hopefully gcc can optimise better with
the hint.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
For the traps it is simpler if we report the status at the end, and
no-op the accumulation of the trap after hitting the error condition.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
References: https://bugs.freedesktop.org/show_bug.cgi?id=48577
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
I'm not quite sure how we end up with a pair of colinear edges both with
a deferred trap...
Fixes crash in bug-bo-ricotz
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
Having spent the last dev cycle looking at how we could specialize the
compositors for various backends, we once again look for the
commonalities in order to reduce the duplication. In part this is
motivated by the idea that spans is a good interface for both the
existent GL backend and pixman, and so they deserve a dedicated
compositor. xcb/xlib target an identical rendering system and so they
should be using the same compositor, and it should be possible to run
that same compositor locally against pixman to generate reference tests.
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
P.S. This brings massive upheaval (read breakage) I've tried delaying in
order to fix as many things as possible but now this one patch does far,
far, far too much. Apologies in advance for breaking your favourite
backend, but trust me in that the end result will be much better. :)
|
|
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
|
|
_cairo_polygon_limit() had to be called immediately after
_cairo_polygon_init() (or never at all).
Merging the two calls is a simple way to enforce this rule.
|
|
Meh. I'm going back to bed. Thanks Joonas for catching this.
|
|
|
|
I updated the Free Software Foundation address using the following script.
for i in $(git grep Temple | cut -d: -f1 )
do
sed -e 's/59 Temple Place[, -]* Suite 330, Boston, MA *02111-1307[, ]* USA/51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA/' -i "$i"
done
Fixes http://bugs.freedesktop.org/show_bug.cgi?id=21356
|
|
A pending commit will want to include some utility code from cairo and
so we need to extricate the error handling from the PLT symbol hiding.
|
|
For the simple cases where the clip is an unaligned box (or boxes), apply
the clip directly to the geometry and avoid having to use an intermediate
clip-mask.
|
|
For the frequent cases where we know in advance that we are dealing with a
rectilinear path, but can not use the simple region code, implement a
variant of the Bentley-Ottmann tessellator. The advantages here are that
edge comparison is very simple (we only have vertical edges) and there are
no intersection, though possible overlaps. The idea is the same, maintain
a y-x sorted queue of start/stop events that demarcate traps and sweep
through the active edges at each event, looking for completed traps.
The motivation for this was noticing a performance regression in
box-fill-outline with the self-intersection work:
1.9.2 to HEAD^: 3.66x slowdown
HEAD^ to HEAD: 5.38x speedup
1.9.2 to HEAD: 1.57x speedup
The cause of which was choosing to use spans instead of the region handling
code, as the complex polygon was no longer being tessellated.
|
|
The skip list was suffering from severe overhead, so though the search was
quick, the extra copies during insertion and deletion were slow.
|
|
The active edge list is typically short, and the skiplist adds significant
overhead that far outweigh the benefit of the O(n lg n) sort. Instead we
track the position of the last insertion edge, knowing that the start
events are lexicographically sorted, and begin a linear search from there.
|
|
We refactor the surface fallbacks to convert full strokes and fills to the
intermediate polygon representation (as opposed to before where we
returned the trapezoidal representation). This allow greater flexibility
to choose how then to rasterize the polygon. Where possible we use the
local spans rasteriser for its increased performance, but still have the
option to use the tessellator instead (for example, with the current
Render protocol which does not yet have a polygon image).
In order to accommodate this, the spans interface is tweaked to accept
whole polygons instead of a path and the tessellator is tweaked for speed.
Performance Impact
==================
...
Still measuring, expecting some severe regressions.
...
|
|
Ensure that no assumptions are made that a small allocation will succeed
by manually injecting faults when we may be simply allocating from an
embedded memory pool.
The main advantage in manual fault injection is improved code coverage -
from within the test suite most allocations are handled by the embedded
memory pools.
|
|
Cleanup a few compiler warnings about unused variables and mismatching
pointer types.
|
|
Since we only need to allocate elts for intersection events and edges, the
number of elts in flight at any one time is actually quite small and can
usually be accommodated from an embedded pool.
|
|
Add a missing _cairo_skip_list_fini() after failure to allocate the
events.
|
|
Use a pool allocator to preallocate a chunk from which to allocate the
skiplist elements (if we failed to reallocate from the freelists).
|
|
Use the gcc likelihood annotation to indicate that allocation failures are
extremely unlikely.
|
|
The spline decomposition code allocates and stores points in a temporary
buffer which is immediately consumed by the caller. If the caller supplies
a callback that handles each point computed along the spline, then we can
use the point immediately and avoid the allocation.
|
|
First of a simple substitution for -?-, as they are very confusing in
context with other minus signs floating around.
Carl has promised to go over these docs with me at the HackFest in order
to improve them (and verify them).
|
|
Instead of maintaining an index and comparing it to the count, just mark
the last startstop event with NULL and stop dequeuing events upon seeing
that sentinel value. (Removes an unreadable line, and cachegrind hints
that it may be a tiny bit faster.)
|
|
In my experiments using cairo-perf, the inlined combsort is ~20% quicker
than the library qsort.
|
|
First check if we can reject the intersection without having to perform
the full divides, based on analysing:
t * (ady*bdx - bdy*adx) = bdy * (ax - bx) - bdx * (ay - by)
s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
and excluding the result if by inspection we know that
(s, t) <= 0 || (s, t) => 1.
Doing so virtually eliminates all division and speeds up the strokes (when
performing self-intersection elimination using the tessellator) perf cases
by about 5%.
|
|
Use our prior knowledge of the inputs and trivial conditions to simplify
the edge equations and in many common conditions, such as vertical edges
and common points, reduce the operations down to a just returning the
non-degenerate 32 bit value. This adds an overhead of a few conditionals,
but on the fast paths we actually generate fewer branches and many fewer
arithmetic operations such that it improves performance of the fill
performance tests by around 10%.
|
|
Fixup a couple of instances of implicit down-casting to 32bits from a
64bit wide integer and add a new is_zero() predicate.
|
|
Avoid passing a 32bit integer as a cairo_int64_t in case we do not have a
64bit native integral type. As a side-effect this means we can also use a
narrower multiply.
|
|
We often use the construct:
if (_cairo_int64_lt (A, B)
return -1;
if (_cairo_int64_gt (A, B)
return 1;
return 0;
to compare two large integers (int64, or int128) which does twice the
required work on CPUs without large integer support. So replace it with a
single wideint function _cairo_int64_cmp() and therefore allow
opportunities to both shrink the code size and write a more efficient
comparison. (The primarily motivation is to simply replace each block with
a single more expressive line.)
|
|
If the sweep-line is currently on an end-point of a line,
then we know its precise x value and can use a cheaper comparator.
Considering that we often need to compare events at end-points (for
instance on a start event), this happens frequently enough to warrant
special casing.
|
|
We need to compare the x-coordinate of a line at a for a particular y,
without loss of precision.
The x-coordinate along an edge for a given y is:
X = A_x + (Y - A_y) * A_dx / A_dy
So the inequality we wish to test is:
A_x + (Y - A_y) * A_dx / A_dy -?- B_x + (Y - B_y) * B_dx / B_dy,
where -?- is our inequality operator.
By construction we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
all positive, so we can rearrange it thus without causing a sign
change:
A_dy * B_dy * (A_x - B_x) -?- (Y - B_y) * B_dx * A_dy
- (Y - A_y) * A_dx * B_dy
Given the assumption that all the deltas fit within 32 bits, we can compute
this comparison directly using 128 bit arithmetic.
|
|
More friendly when debugging, as the debug will (by default) catch the
SIGTRAP and break at the offending test.
|
|
We don't need to tessellate edges strictly above or below the
the limits of the traps.
|
|
The tessellator is well-proven now. However, the sweep-line validator
consumes around 50% of the total time required to draw the fractal
Pythagoras tree (the leaves are sub-pixel rectangles, so lots of edges
to sweep through). So disable the validator, but keep it available for
debugging.
|
|
Some tweaks to avoid stack copies and branches that save ~25% in
_cairo_traps_tessellate_convex_quad().
|
|
Reported on the cairo mailing list:
http://lists.cairographics.org/archives/cairo/2008-May/014233.html
The tessellator would sometimes produce self-intersecting trapezoids
because it would skip the last edge in the active list when deciding
whether we can continue the current trapezoid or not.
The bug never caused a problem with pixman based rasterisation
because pixman stops filling in a trapezoid once it detects a self
intersection.
|
|
|
|
|
|
|
|
|
|
|
|
In http://bugs.freedesktop.org/show_bug.cgi?id=13699, Pavel Vozenilek
reports a duplicate define for computing the appropriate length for an
on-stack array. The macro in question, and a few other places, was
performing CAIRO_STACK_BUF_SIZE/sizeof(stack[0]) so we can simplify
them slightly by using a common macro.
|
|
Every time we assign or return a hard-coded error status wrap that value
with a call to _cairo_error(). So the idiom becomes:
status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
or
return _cairo_error (CAIRO_STATUS_INVALID_DASH);
This ensures that a breakpoint placed on _cairo_error() will trigger
immediately cairo detects the error.
|
|
Blitz all allocations to ensure that they raise a
_cairo_error(CAIRO_STATUS_NO_MEMORY) on failure.
|
