[cairo-commit] 5 commits - perf/cairo-perf.h perf/cairo-perf-micro.c perf/micro src/cairo-bentley-ottmann-rectangular.c src/cairo-path-fixed.c src/Makefile.sources
Chris Wilson
ickle at kemper.freedesktop.org
Tue Aug 9 09:09:04 PDT 2011
perf/cairo-perf-micro.c | 1
perf/cairo-perf.h | 1
perf/micro/Makefile.sources | 1
perf/micro/many-fills.c | 184 ++++++++++++
src/Makefile.sources | 1
src/cairo-bentley-ottmann-rectangular.c | 488 ++++++++++++++++----------------
src/cairo-path-fixed.c | 34 +-
7 files changed, 461 insertions(+), 249 deletions(-)
New commits:
commit a4e4e2bdd74bd686e24f95839a095e1afd280a13
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Tue Aug 9 14:32:09 2011 +0100
bo-rectangular: Use a mergesort to speedup insertion
However, this is only useful for inserting multiple boxes within the
pixel, so we maintain the cached insert cursor as this speeds up the
general case (and aides this optimisation as well).
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/cairo-bentley-ottmann-rectangular.c b/src/cairo-bentley-ottmann-rectangular.c
index 381e4ed..9adf4a5 100644
--- a/src/cairo-bentley-ottmann-rectangular.c
+++ b/src/cairo-bentley-ottmann-rectangular.c
@@ -72,12 +72,12 @@ struct _rectangle {
typedef struct _sweep_line {
rectangle_t **rectangles;
rectangle_t **stop;
- edge_t head, tail;
- edge_t *insert_left, *insert_right;
+ edge_t head, tail, *insert, *cursor;
int32_t current_y;
int32_t last_y;
int stop_size;
+ int32_t insert_x;
cairo_fill_rule_t fill_rule;
cairo_bool_t do_traps;
@@ -217,17 +217,20 @@ sweep_line_init (sweep_line_t *sweep_line,
sweep_line->stop = rectangles - 2;
sweep_line->stop_size = 0;
+ sweep_line->insert = NULL;
+ sweep_line->insert_x = INT_MAX;
+ sweep_line->cursor = &sweep_line->tail;
+
+ sweep_line->head.dir = 0;
sweep_line->head.x = INT32_MIN;
sweep_line->head.right = NULL;
- sweep_line->head.dir = 0;
+ sweep_line->head.prev = NULL;
sweep_line->head.next = &sweep_line->tail;
- sweep_line->tail.x = INT32_MAX;
+ sweep_line->tail.prev = &sweep_line->head;
+ sweep_line->tail.next = NULL;
sweep_line->tail.right = NULL;
+ sweep_line->tail.x = INT32_MAX;
sweep_line->tail.dir = 0;
- sweep_line->tail.prev = &sweep_line->head;
-
- sweep_line->insert_left = &sweep_line->tail;
- sweep_line->insert_right = &sweep_line->tail;
sweep_line->current_y = INT32_MIN;
sweep_line->last_y = INT32_MIN;
@@ -288,7 +291,7 @@ edge_start_or_continue_box (sweep_line_t *sweep_line,
return;
if (left->right != NULL) {
- if (right != NULL && left->right->x == right->x) {
+ if (left->right->x == right->x) {
/* continuation on right, so just swap edges */
left->right = right;
return;
@@ -297,11 +300,157 @@ edge_start_or_continue_box (sweep_line_t *sweep_line,
edge_end_box (sweep_line, left, top);
}
- if (right != NULL && left->x != right->x) {
+ if (left->x != right->x) {
left->top = top;
left->right = right;
}
}
+/*
+ * Merge two sorted edge lists.
+ * Input:
+ * - head_a: The head of the first list.
+ * - head_b: The head of the second list; head_b cannot be NULL.
+ * Output:
+ * Returns the head of the merged list.
+ *
+ * Implementation notes:
+ * To make it fast (in particular, to reduce to an insertion sort whenever
+ * one of the two input lists only has a single element) we iterate through
+ * a list until its head becomes greater than the head of the other list,
+ * then we switch their roles. As soon as one of the two lists is empty, we
+ * just attach the other one to the current list and exit.
+ * Writes to memory are only needed to "switch" lists (as it also requires
+ * attaching to the output list the list which we will be iterating next) and
+ * to attach the last non-empty list.
+ */
+static edge_t *
+merge_sorted_edges (edge_t *head_a, edge_t *head_b)
+{
+ edge_t *head, **next;
+ int32_t x;
+
+ if (head_a == NULL)
+ return head_b;
+
+ next = &head;
+ if (head_a->x <= head_b->x) {
+ head = head_a;
+ } else {
+ head = head_b;
+ goto start_with_b;
+ }
+
+ do {
+ x = head_b->x;
+ while (head_a != NULL && head_a->x <= x) {
+ next = &head_a->next;
+ head_a = head_a->next;
+ }
+
+ *next = head_b;
+ if (head_a == NULL)
+ return head;
+
+start_with_b:
+ x = head_a->x;
+ while (head_b != NULL && head_b->x <= x) {
+ next = &head_b->next;
+ head_b = head_b->next;
+ }
+
+ *next = head_a;
+ if (head_b == NULL)
+ return head;
+ } while (1);
+}
+
+/*
+ * Sort (part of) a list.
+ * Input:
+ * - list: The list to be sorted; list cannot be NULL.
+ * - limit: Recursion limit.
+ * Output:
+ * - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
+ * input list; if the input list has fewer elements, head_out be a sorted list
+ * containing all the elements of the input list.
+ * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
+ * all the elements of the input list).
+ *
+ * Implementation notes:
+ * Special case single element list, unroll/inline the sorting of the first two elements.
+ * Some tail recursion is used since we iterate on the bottom-up solution of the problem
+ * (we start with a small sorted list and keep merging other lists of the same size to it).
+ */
+static edge_t *
+sort_edges (edge_t *list,
+ unsigned int level,
+ edge_t **head_out)
+{
+ edge_t *head_other, *remaining;
+ unsigned int i;
+
+ head_other = list->next;
+
+ if (head_other == NULL) {
+ *head_out = list;
+ return NULL;
+ }
+
+ remaining = head_other->next;
+ if (list->x <= head_other->x) {
+ *head_out = list;
+ head_other->next = NULL;
+ } else {
+ *head_out = head_other;
+ head_other->next = list;
+ list->next = NULL;
+ }
+
+ for (i = 0; i < level && remaining; i++) {
+ /* Extract a sorted list of the same size as *head_out
+ * (2^(i+1) elements) from the list of remaining elements. */
+ remaining = sort_edges (remaining, i, &head_other);
+ *head_out = merge_sorted_edges (*head_out, head_other);
+ }
+
+ /* *head_out now contains (at most) 2^(level+1) elements. */
+
+ return remaining;
+}
+
+static edge_t *
+merge_unsorted_edges (edge_t *head, edge_t *unsorted)
+{
+ sort_edges (unsorted, UINT_MAX, &unsorted);
+ return merge_sorted_edges (head, unsorted);
+}
+
+static void
+active_edges_insert (sweep_line_t *sweep)
+{
+ edge_t *edge, *prev;
+ int x;
+
+ x = sweep->insert_x;
+ prev = sweep->cursor;
+ if (prev->x > x) {
+ do {
+ prev = prev->prev;
+ } while (prev->x > x);
+ } else {
+ while (prev->next->x < x)
+ prev = prev->next;
+ }
+
+ prev->next = merge_unsorted_edges (prev->next, sweep->insert);
+ sweep->cursor = sweep->insert;
+ sweep->insert = NULL;
+ sweep->insert_x = INT_MAX;
+
+ /* update links within sort? */
+ for (edge = prev->next; edge; prev = edge, edge = edge->next)
+ edge->prev = prev;
+}
static inline void
active_edges_to_traps (sweep_line_t *sweep)
@@ -312,6 +461,9 @@ active_edges_to_traps (sweep_line_t *sweep)
if (sweep->last_y == sweep->current_y)
return;
+ if (sweep->insert)
+ active_edges_insert (sweep);
+
pos = sweep->head.next;
if (pos == &sweep->tail)
return;
@@ -395,7 +547,7 @@ active_edges_to_traps (sweep_line_t *sweep)
}
static inline void
-sweep_line_delete_edge (sweep_line_t *sweep_line, edge_t *edge)
+sweep_line_delete_edge (sweep_line_t *sweep, edge_t *edge)
{
if (edge->right != NULL) {
edge_t *next = edge->next;
@@ -403,13 +555,11 @@ sweep_line_delete_edge (sweep_line_t *sweep_line, edge_t *edge)
next->top = edge->top;
next->right = edge->right;
} else
- edge_end_box (sweep_line, edge, sweep_line->current_y);
+ edge_end_box (sweep, edge, sweep->current_y);
}
- if (sweep_line->insert_left == edge)
- sweep_line->insert_left = edge->next;
- if (sweep_line->insert_right == edge)
- sweep_line->insert_right = edge->next;
+ if (sweep->cursor == edge)
+ sweep->cursor = edge->prev;
edge->prev->next = edge->next;
edge->next->prev = edge->prev;
@@ -435,57 +585,15 @@ sweep_line_delete (sweep_line_t *sweep, rectangle_t *rectangle)
}
static inline void
-insert_edge (edge_t *edge, edge_t *pos)
+sweep_line_insert (sweep_line_t *sweep, rectangle_t *rectangle)
{
- if (pos->x != edge->x) {
- if (pos->x > edge->x) {
- do {
- if (pos->prev->x <= edge->x)
- break;
- pos = pos->prev;
- } while (TRUE);
- } else {
- do {
- pos = pos->next;
- if (pos->x >= edge->x)
- break;
- } while (TRUE);
- }
- }
-
- pos->prev->next = edge;
- edge->prev = pos->prev;
- edge->next = pos;
- pos->prev = edge;
-}
-
-static inline cairo_bool_t
-sweep_line_insert (sweep_line_t *sweep,
- rectangle_t *rectangle)
-{
- edge_t *pos;
-
- /* right edge */
- pos = sweep->insert_right;
- insert_edge (&rectangle->right, pos);
- sweep->insert_right = &rectangle->right;
-
- /* left edge */
- pos = sweep->insert_left;
- if (pos->x > sweep->insert_right->x)
- pos = sweep->insert_right->prev;
- insert_edge (&rectangle->left, pos);
- sweep->insert_left = &rectangle->left;
+ rectangle->right.next = sweep->insert;
+ rectangle->left.next = &rectangle->right;
+ sweep->insert = &rectangle->left;
+ if (rectangle->left.x < sweep->insert_x)
+ sweep->insert_x = rectangle->left.x;
pqueue_push (sweep, rectangle);
-
- if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
- rectangle->left.prev->dir == rectangle->left.dir)
- {
- return rectangle->left.next != &rectangle->right;
- }
-
- return TRUE;
}
static cairo_status_t
@@ -535,8 +643,12 @@ _cairo_bentley_ottmann_tessellate_rectangular (rectangle_t **rectangles,
sweep_line.current_y = rectangle->top;
}
- update |= sweep_line_insert (&sweep_line, rectangle);
- } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL);
+ do {
+ sweep_line_insert (&sweep_line, rectangle);
+ } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL &&
+ sweep_line.current_y == rectangle->top);
+ update = TRUE;
+ } while (rectangle);
while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
if (rectangle->bottom != sweep_line.current_y) {
commit 014e5e5ec19d1a315e279a6d618ed832f2bd1346
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Tue Aug 9 13:47:50 2011 +0100
bo-rectangular: Eliminate allocation for pqueue
Since we only allocate a pointer to the rectangle after it is started
and so decoupled from the start queue, we reuse the memory allocated for
the start queue for the stop binary heap.
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/cairo-bentley-ottmann-rectangular.c b/src/cairo-bentley-ottmann-rectangular.c
index a7506a9..381e4ed 100644
--- a/src/cairo-bentley-ottmann-rectangular.c
+++ b/src/cairo-bentley-ottmann-rectangular.c
@@ -69,23 +69,20 @@ struct _rectangle {
/* left and right children are index * 2 and (index * 2) +1 respectively */
#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
-typedef struct _pqueue {
- int size, max_size;
-
- rectangle_t **elements;
- rectangle_t *elements_embedded[1024];
-} pqueue_t;
-
typedef struct _sweep_line {
rectangle_t **rectangles;
- pqueue_t pq;
+ rectangle_t **stop;
edge_t head, tail;
edge_t *insert_left, *insert_right;
int32_t current_y;
int32_t last_y;
+ int stop_size;
cairo_fill_rule_t fill_rule;
+ cairo_bool_t do_traps;
+ void *container;
+
jmp_buf unwind;
} sweep_line_t;
@@ -139,63 +136,13 @@ rectangle_compare_stop (const rectangle_t *a,
}
static inline void
-pqueue_init (pqueue_t *pq)
-{
- pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
- pq->size = 0;
-
- pq->elements = pq->elements_embedded;
- pq->elements[PQ_FIRST_ENTRY] = NULL;
-}
-
-static inline void
-pqueue_fini (pqueue_t *pq)
-{
- if (pq->elements != pq->elements_embedded)
- free (pq->elements);
-}
-
-static cairo_bool_t
-pqueue_grow (pqueue_t *pq)
-{
- rectangle_t **new_elements;
- pq->max_size *= 2;
-
- if (pq->elements == pq->elements_embedded) {
- new_elements = _cairo_malloc_ab (pq->max_size,
- sizeof (rectangle_t *));
- if (unlikely (new_elements == NULL))
- return FALSE;
-
- memcpy (new_elements, pq->elements_embedded,
- sizeof (pq->elements_embedded));
- } else {
- new_elements = _cairo_realloc_ab (pq->elements,
- pq->max_size,
- sizeof (rectangle_t *));
- if (unlikely (new_elements == NULL))
- return FALSE;
- }
-
- pq->elements = new_elements;
- return TRUE;
-}
-
-static inline void
pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
{
rectangle_t **elements;
int i, parent;
- if (unlikely (sweep->pq.size + 1 == sweep->pq.max_size)) {
- if (unlikely (! pqueue_grow (&sweep->pq))) {
- longjmp (sweep->unwind,
- _cairo_error (CAIRO_STATUS_NO_MEMORY));
- }
- }
-
- elements = sweep->pq.elements;
- for (i = ++sweep->pq.size;
+ elements = sweep->stop;
+ for (i = ++sweep->stop_size;
i != PQ_FIRST_ENTRY &&
rectangle_compare_stop (rectangle,
elements[parent = PQ_PARENT_INDEX (i)]) < 0;
@@ -208,23 +155,23 @@ pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
}
static inline void
-pqueue_pop (pqueue_t *pq)
+rectangle_pop_stop (sweep_line_t *sweep)
{
- rectangle_t **elements = pq->elements;
+ rectangle_t **elements = sweep->stop;
rectangle_t *tail;
int child, i;
- tail = elements[pq->size--];
- if (pq->size == 0) {
+ tail = elements[sweep->stop_size--];
+ if (sweep->stop_size == 0) {
elements[PQ_FIRST_ENTRY] = NULL;
return;
}
for (i = PQ_FIRST_ENTRY;
- (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
+ (child = PQ_LEFT_CHILD_INDEX (i)) <= sweep->stop_size;
i = child)
{
- if (child != pq->size &&
+ if (child != sweep->stop_size &&
rectangle_compare_stop (elements[child+1],
elements[child]) < 0)
{
@@ -248,7 +195,7 @@ rectangle_pop_start (sweep_line_t *sweep_line)
static inline rectangle_t *
rectangle_peek_stop (sweep_line_t *sweep_line)
{
- return sweep_line->pq.elements[PQ_FIRST_ENTRY];
+ return sweep_line->stop[PQ_FIRST_ENTRY];
}
CAIRO_COMBSORT_DECLARE (_rectangle_sort,
@@ -259,10 +206,16 @@ static void
sweep_line_init (sweep_line_t *sweep_line,
rectangle_t **rectangles,
int num_rectangles,
- cairo_fill_rule_t fill_rule)
+ cairo_fill_rule_t fill_rule,
+ cairo_bool_t do_traps,
+ void *container)
{
+ rectangles[-2] = NULL;
+ rectangles[-1] = NULL;
rectangles[num_rectangles] = NULL;
sweep_line->rectangles = rectangles;
+ sweep_line->stop = rectangles - 2;
+ sweep_line->stop_size = 0;
sweep_line->head.x = INT32_MIN;
sweep_line->head.right = NULL;
@@ -280,28 +233,18 @@ sweep_line_init (sweep_line_t *sweep_line,
sweep_line->last_y = INT32_MIN;
sweep_line->fill_rule = fill_rule;
-
- pqueue_init (&sweep_line->pq);
-}
-
-static void
-sweep_line_fini (sweep_line_t *sweep_line)
-{
- pqueue_fini (&sweep_line->pq);
+ sweep_line->container = container;
+ sweep_line->do_traps = do_traps;
}
static void
-edge_end_box (sweep_line_t *sweep_line,
- edge_t *left,
- int32_t bot,
- cairo_bool_t do_traps,
- void *container)
+edge_end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot)
{
cairo_status_t status = CAIRO_STATUS_SUCCESS;
/* Only emit (trivial) non-degenerate trapezoids with positive height. */
if (likely (left->top < bot)) {
- if (do_traps) {
+ if (sweep_line->do_traps) {
cairo_line_t _left = {
{ left->x, left->top },
{ left->x, bot },
@@ -309,8 +252,8 @@ edge_end_box (sweep_line_t *sweep_line,
{ left->right->x, left->top },
{ left->right->x, bot },
};
- _cairo_traps_add_trap (container, left->top, bot, &_left, &_right);
- status = _cairo_traps_status ((cairo_traps_t *) container);
+ _cairo_traps_add_trap (sweep_line->container, left->top, bot, &_left, &_right);
+ status = _cairo_traps_status ((cairo_traps_t *) sweep_line->container);
} else {
cairo_box_t box;
@@ -319,7 +262,9 @@ edge_end_box (sweep_line_t *sweep_line,
box.p2.x = left->right->x;
box.p2.y = bot;
- status = _cairo_boxes_add (container, CAIRO_ANTIALIAS_DEFAULT, &box);
+ status = _cairo_boxes_add (sweep_line->container,
+ CAIRO_ANTIALIAS_DEFAULT,
+ &box);
}
}
if (unlikely (status))
@@ -337,9 +282,7 @@ static inline void
edge_start_or_continue_box (sweep_line_t *sweep_line,
edge_t *left,
edge_t *right,
- int top,
- cairo_bool_t do_traps,
- void *container)
+ int top)
{
if (left->right == right)
return;
@@ -351,8 +294,7 @@ edge_start_or_continue_box (sweep_line_t *sweep_line,
return;
}
- edge_end_box (sweep_line,
- left, top, do_traps, container);
+ edge_end_box (sweep_line, left, top);
}
if (right != NULL && left->x != right->x) {
@@ -362,9 +304,7 @@ edge_start_or_continue_box (sweep_line_t *sweep_line,
}
static inline void
-active_edges_to_traps (sweep_line_t *sweep,
- cairo_bool_t do_traps,
- void *container)
+active_edges_to_traps (sweep_line_t *sweep)
{
int top = sweep->current_y;
edge_t *pos;
@@ -414,24 +354,17 @@ active_edges_to_traps (sweep_line_t *sweep,
do {
/* End all subsumed traps */
- if (unlikely (right->right != NULL)) {
- edge_end_box (sweep,
- right, top, do_traps, container);
- }
+ if (unlikely (right->right != NULL))
+ edge_end_box (sweep, right, top);
winding += right->dir;
- if (winding == 0) {
- /* skip co-linear edges */
- if (likely (right->x != right->next->x))
- break;
- }
+ if (winding == 0 && right->x != right->next->x)
+ break;
right = right->next;
} while (TRUE);
- edge_start_or_continue_box (sweep,
- left, right, top,
- do_traps, container);
+ edge_start_or_continue_box (sweep, left, right, top);
pos = right->next;
} while (pos != &sweep->tail);
@@ -442,23 +375,17 @@ active_edges_to_traps (sweep_line_t *sweep,
do {
/* End all subsumed traps */
- if (unlikely (right->right != NULL)) {
- edge_end_box (sweep,
- right, top, do_traps, container);
- }
+ if (unlikely (right->right != NULL))
+ edge_end_box (sweep, right, top);
- if (++count & 1) {
/* skip co-linear edges */
- if (likely (right->x != right->next->x))
- break;
- }
+ if (++count & 1 && right->x != right->next->x)
+ break;
right = right->next;
} while (TRUE);
- edge_start_or_continue_box (sweep,
- pos, right, top,
- do_traps, container);
+ edge_start_or_continue_box (sweep, pos, right, top);
pos = right->next;
} while (pos != &sweep->tail);
@@ -468,22 +395,15 @@ active_edges_to_traps (sweep_line_t *sweep,
}
static inline void
-sweep_line_delete_edge (sweep_line_t *sweep_line,
- edge_t *edge,
- cairo_bool_t do_traps,
- void *container)
+sweep_line_delete_edge (sweep_line_t *sweep_line, edge_t *edge)
{
if (edge->right != NULL) {
edge_t *next = edge->next;
if (next->x == edge->x) {
next->top = edge->top;
next->right = edge->right;
- } else {
- edge_end_box (sweep_line,
- edge,
- sweep_line->current_y,
- do_traps, container);
- }
+ } else
+ edge_end_box (sweep_line, edge, sweep_line->current_y);
}
if (sweep_line->insert_left == edge)
@@ -496,10 +416,7 @@ sweep_line_delete_edge (sweep_line_t *sweep_line,
}
static inline cairo_bool_t
-sweep_line_delete (sweep_line_t *sweep,
- rectangle_t *rectangle,
- cairo_bool_t do_traps,
- void *container)
+sweep_line_delete (sweep_line_t *sweep, rectangle_t *rectangle)
{
cairo_bool_t update;
@@ -510,15 +427,10 @@ sweep_line_delete (sweep_line_t *sweep,
update = rectangle->left.next != &rectangle->right;
}
- sweep_line_delete_edge (sweep,
- &rectangle->left,
- do_traps, container);
-
- sweep_line_delete_edge (sweep,
- &rectangle->right,
- do_traps, container);
+ sweep_line_delete_edge (sweep, &rectangle->left);
+ sweep_line_delete_edge (sweep, &rectangle->right);
- pqueue_pop (&sweep->pq);
+ rectangle_pop_stop (sweep);
return update;
}
@@ -528,19 +440,15 @@ insert_edge (edge_t *edge, edge_t *pos)
if (pos->x != edge->x) {
if (pos->x > edge->x) {
do {
- UNROLL3({
- if (pos->prev->x <= edge->x)
- break;
- pos = pos->prev;
- })
+ if (pos->prev->x <= edge->x)
+ break;
+ pos = pos->prev;
} while (TRUE);
} else {
do {
- UNROLL3({
- pos = pos->next;
- if (pos->x >= edge->x)
- break;
- })
+ pos = pos->next;
+ if (pos->x >= edge->x)
+ break;
} while (TRUE);
}
}
@@ -592,9 +500,12 @@ _cairo_bentley_ottmann_tessellate_rectangular (rectangle_t **rectangles,
cairo_status_t status;
cairo_bool_t update = FALSE;
- sweep_line_init (&sweep_line, rectangles, num_rectangles, fill_rule);
+ sweep_line_init (&sweep_line,
+ rectangles, num_rectangles,
+ fill_rule,
+ do_traps, container);
if ((status = setjmp (sweep_line.unwind)))
- goto unwind;
+ return status;
rectangle = rectangle_pop_start (&sweep_line);
do {
@@ -605,21 +516,19 @@ _cairo_bentley_ottmann_tessellate_rectangular (rectangle_t **rectangles,
while (stop != NULL && stop->bottom < rectangle->top) {
if (stop->bottom != sweep_line.current_y) {
if (update) {
- active_edges_to_traps (&sweep_line,
- do_traps, container);
+ active_edges_to_traps (&sweep_line);
update = FALSE;
}
sweep_line.current_y = stop->bottom;
}
- update |= sweep_line_delete (&sweep_line, stop, do_traps, container);
-
+ update |= sweep_line_delete (&sweep_line, stop);
stop = rectangle_peek_stop (&sweep_line);
}
if (update) {
- active_edges_to_traps (&sweep_line, do_traps, container);
+ active_edges_to_traps (&sweep_line);
update = FALSE;
}
@@ -632,19 +541,17 @@ _cairo_bentley_ottmann_tessellate_rectangular (rectangle_t **rectangles,
while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
if (rectangle->bottom != sweep_line.current_y) {
if (update) {
- active_edges_to_traps (&sweep_line, do_traps, container);
+ active_edges_to_traps (&sweep_line);
update = FALSE;
}
sweep_line.current_y = rectangle->bottom;
}
- update |= sweep_line_delete (&sweep_line, rectangle, do_traps, container);
+ update |= sweep_line_delete (&sweep_line, rectangle);
}
-unwind:
- sweep_line_fini (&sweep_line);
- return status;
+ return CAIRO_STATUS_SUCCESS;
}
cairo_status_t
@@ -652,9 +559,8 @@ _cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
cairo_fill_rule_t fill_rule)
{
rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
- rectangle_t *rectangles;
- rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1];
- rectangle_t **rectangles_ptrs;
+ rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
+ rectangle_t *rectangles, **rectangles_ptrs;
cairo_status_t status;
int i;
@@ -669,9 +575,9 @@ _cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
rectangles_ptrs = stack_rectangles_ptrs;
if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
- sizeof (rectangle_t) +
- sizeof (rectangle_t *),
- sizeof (rectangle_t *));
+ sizeof (rectangle_t) +
+ sizeof (rectangle_t *),
+ 3*sizeof (rectangle_t *));
if (unlikely (rectangles == NULL))
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
@@ -699,13 +605,13 @@ _cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
rectangles[i].top = traps->traps[i].top;
rectangles[i].bottom = traps->traps[i].bottom;
- rectangles_ptrs[i] = &rectangles[i];
+ rectangles_ptrs[i+2] = &rectangles[i];
}
/* XXX incremental sort */
- _rectangle_sort (rectangles_ptrs, i);
+ _rectangle_sort (rectangles_ptrs+2, i);
_cairo_traps_clear (traps);
- status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs, i,
+ status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, i,
fill_rule,
TRUE, traps);
traps->is_rectilinear = TRUE;
@@ -725,9 +631,8 @@ _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
cairo_boxes_t *out)
{
rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
- rectangle_t *rectangles;
- rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1];
- rectangle_t **rectangles_ptrs;
+ rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
+ rectangle_t *rectangles, **rectangles_ptrs;
rectangle_t *stack_rectangles_chain[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *) ];
rectangle_t **rectangles_chain;
const struct _cairo_boxes_chunk *chunk;
@@ -790,9 +695,9 @@ _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
rectangles_ptrs = stack_rectangles_ptrs;
if (in->num_boxes > ARRAY_LENGTH (stack_rectangles)) {
rectangles = _cairo_malloc_ab_plus_c (in->num_boxes,
- sizeof (rectangle_t) +
- sizeof (rectangle_t *),
- sizeof (rectangle_t *));
+ sizeof (rectangle_t) +
+ sizeof (rectangle_t *),
+ 3*sizeof (rectangle_t *));
if (unlikely (rectangles == NULL)) {
if (rectangles_chain != stack_rectangles_chain)
free (rectangles_chain);
@@ -835,7 +740,7 @@ _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
}
}
- j = 0;
+ j = 2;
for (y_min = 0; y_min < y_max; y_min++) {
rectangle_t *r;
int start = j;
@@ -844,13 +749,12 @@ _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
if (j > start + 1)
_rectangle_sort (rectangles_ptrs + start, j - start);
}
- assert (j == in->num_boxes);
if (rectangles_chain != stack_rectangles_chain)
free (rectangles_chain);
_cairo_boxes_clear (out);
- status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs, j,
+ status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, j-2,
fill_rule,
FALSE, out);
if (rectangles != stack_rectangles)
commit 323e48f8ec2b6de467971d4e4a7fb45f56416e1e
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Tue Aug 9 15:15:41 2011 +0100
fill: A horizontal/vertical line is also a degenerate fill box
Since we discard empty fill boxes whilst filling, we can also treat
horizontal/vertical lines as a filled box and so proceed with the
rectangular fast path in the presence of
cairo_rectangle (x, y, w, h)
with w == 0 || h == 0.
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
index 58d4f4b..7af45f8 100644
--- a/src/cairo-path-fixed.c
+++ b/src/cairo-path-fixed.c
@@ -1338,11 +1338,8 @@ _cairo_path_fixed_iter_is_fill_box (cairo_path_fixed_iter_t *_iter,
iter = *_iter;
- if (iter.n_op == iter.buf->num_ops &&
- ! _cairo_path_fixed_iter_next_op (&iter))
- {
+ if (iter.n_op == iter.buf->num_ops && ! _cairo_path_fixed_iter_next_op (&iter))
return FALSE;
- }
/* Check whether the ops are those that would be used for a rectangle */
if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_MOVE_TO)
@@ -1357,8 +1354,20 @@ _cairo_path_fixed_iter_is_fill_box (cairo_path_fixed_iter_t *_iter,
if (! _cairo_path_fixed_iter_next_op (&iter))
return FALSE;
- if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_LINE_TO)
+ /* a horizontal/vertical closed line is also a degenerate rectangle */
+ switch (iter.buf->op[iter.n_op]) {
+ case CAIRO_PATH_OP_CLOSE_PATH:
+ _cairo_path_fixed_iter_next_op (&iter);
+ case CAIRO_PATH_OP_MOVE_TO: /* implicit close */
+ box->p1 = box->p2 = points[0];
+ *_iter = iter;
+ return TRUE;
+ default:
return FALSE;
+ case CAIRO_PATH_OP_LINE_TO:
+ break;
+ }
+
points[2] = iter.buf->points[iter.n_point++];
if (! _cairo_path_fixed_iter_next_op (&iter))
return FALSE;
@@ -1372,19 +1381,18 @@ _cairo_path_fixed_iter_is_fill_box (cairo_path_fixed_iter_t *_iter,
/* Now, there are choices. The rectangle might end with a LINE_TO
* (to the original point), but this isn't required. If it
* doesn't, then it must end with a CLOSE_PATH (which may be implicit). */
- if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_LINE_TO)
- {
+ if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_LINE_TO) {
points[4] = iter.buf->points[iter.n_point++];
if (points[4].x != points[0].x || points[4].y != points[0].y)
return FALSE;
- }
- else if (! (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_CLOSE_PATH ||
- iter.buf->op[iter.n_op] == CAIRO_PATH_OP_MOVE_TO))
- {
+ _cairo_path_fixed_iter_next_op (&iter);
+ } else if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_CLOSE_PATH) {
+ _cairo_path_fixed_iter_next_op (&iter);
+ } else if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_MOVE_TO) {
+ /* implicit close-path */
+ } else {
return FALSE;
}
- if (! _cairo_path_fixed_iter_next_op (&iter))
- return FALSE;
/* Ok, we may have a box, if the points line up */
if (points[0].y == points[1].y &&
commit 786d4b2a2af53efc6121fd4be04038f2262adf39
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Tue Aug 9 11:10:52 2011 +0100
perf: Add many-fills
A variant of many-strokes tries to answer the question of how much
overhead is there in stroking, i.e. if we fill an equivalent path to a
set of strokes, do we see an equivalence in performance?
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/perf/cairo-perf-micro.c b/perf/cairo-perf-micro.c
index b62a2ce..6719489 100644
--- a/perf/cairo-perf-micro.c
+++ b/perf/cairo-perf-micro.c
@@ -565,6 +565,7 @@ const cairo_perf_case_t perf_cases[] = {
{ pythagoras_tree, 768, 768 },
{ intersections, 512, 512 },
{ many_strokes, 64, 512 },
+ { many_fills, 64, 512 },
{ spiral, 512, 512 },
{ wave, 500, 500 },
{ NULL }
diff --git a/perf/cairo-perf.h b/perf/cairo-perf.h
index a1ce17e..8e8f0ff 100644
--- a/perf/cairo-perf.h
+++ b/perf/cairo-perf.h
@@ -212,5 +212,6 @@ CAIRO_PERF_DECL (intersections);
CAIRO_PERF_DECL (spiral);
CAIRO_PERF_DECL (wave);
CAIRO_PERF_DECL (many_strokes);
+CAIRO_PERF_DECL (many_fills);
#endif
diff --git a/perf/micro/Makefile.sources b/perf/micro/Makefile.sources
index ee8cc57..b6ee119 100644
--- a/perf/micro/Makefile.sources
+++ b/perf/micro/Makefile.sources
@@ -29,6 +29,7 @@ libcairo_perf_micro_sources = \
pythagoras-tree.c \
intersections.c \
many-strokes.c \
+ many-fills.c \
spiral.c \
$(NULL)
diff --git a/perf/micro/many-fills.c b/perf/micro/many-fills.c
new file mode 100644
index 0000000..8c012aa
--- /dev/null
+++ b/perf/micro/many-fills.c
@@ -0,0 +1,184 @@
+/*
+ * Copyright © 2011 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use, copy,
+ * modify, merge, publish, distribute, sublicense, and/or sell copies
+ * of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Author: Chris Wilson <chris at chris-wilson.co.uk>
+ */
+
+
+/* This is a variant on many strokes where we precompute
+ * a simplified stroke-to-path.
+ * When we have a real stroke-to-path, it would useful to compare the cost
+ * of stroking vs filling the "identical" paths.
+ */
+
+#include "cairo-perf.h"
+
+static uint32_t state;
+
+static double
+uniform_random (double minval, double maxval)
+{
+ static uint32_t const poly = 0x9a795537U;
+ uint32_t n = 32;
+ while (n-->0)
+ state = 2*state < state ? (2*state ^ poly) : 2*state;
+ return minval + state * (maxval - minval) / 4294967296.0;
+}
+
+static cairo_perf_ticks_t
+do_many_fills_ha (cairo_t *cr, int width, int height, int loops)
+{
+ int count;
+
+ state = 0xc0ffee;
+ for (count = 0; count < 1000; count++) {
+ double y = floor (uniform_random (0, height));
+ double x = floor (uniform_random (0, width));
+ cairo_rectangle (cr, x, y, ceil (uniform_random (0, width)) - x, 2);
+ }
+
+ cairo_perf_timer_start ();
+
+ while (loops--)
+ cairo_fill_preserve (cr);
+
+ cairo_perf_timer_stop ();
+
+ cairo_new_path (cr);
+
+ return cairo_perf_timer_elapsed ();
+}
+
+static cairo_perf_ticks_t
+do_many_fills_h (cairo_t *cr, int width, int height, int loops)
+{
+ int count;
+
+ state = 0xc0ffee;
+ for (count = 0; count < 1000; count++) {
+ double y = uniform_random (0, height);
+ double x = uniform_random (0, width);
+ cairo_rectangle (cr, x, y, uniform_random (0, width) - x, 2);
+ }
+
+ cairo_perf_timer_start ();
+
+ while (loops--)
+ cairo_fill_preserve (cr);
+
+ cairo_perf_timer_stop ();
+
+ cairo_new_path (cr);
+
+ return cairo_perf_timer_elapsed ();
+}
+
+static cairo_perf_ticks_t
+do_many_fills_va (cairo_t *cr, int width, int height, int loops)
+{
+ int count;
+
+ state = 0xc0ffee;
+ for (count = 0; count < 1000; count++) {
+ double x = floor (uniform_random (0, width));
+ double y = floor (uniform_random (0, height));
+ cairo_rectangle (cr, x, y, 2, ceil (uniform_random (0, height) - y));
+ }
+
+ cairo_perf_timer_start ();
+
+ while (loops--)
+ cairo_fill_preserve (cr);
+
+ cairo_perf_timer_stop ();
+
+ cairo_new_path (cr);
+
+ return cairo_perf_timer_elapsed ();
+}
+
+static cairo_perf_ticks_t
+do_many_fills_v (cairo_t *cr, int width, int height, int loops)
+{
+ int count;
+
+ state = 0xc0ffee;
+ for (count = 0; count < 1000; count++) {
+ double x = uniform_random (0, width);
+ double y = uniform_random (0, height);
+ cairo_rectangle (cr, x, y, 2, uniform_random (0, height) - y);
+ }
+
+ cairo_perf_timer_start ();
+
+ while (loops--)
+ cairo_fill_preserve (cr);
+
+ cairo_perf_timer_stop ();
+
+ cairo_new_path (cr);
+
+ return cairo_perf_timer_elapsed ();
+}
+
+static cairo_perf_ticks_t
+do_many_fills (cairo_t *cr, int width, int height, int loops)
+{
+ int count;
+
+ /* lots and lots of overlapping stroke-like fills */
+ state = 0xc0ffee;
+ for (count = 0; count < 1000; count++) {
+ cairo_save (cr);
+ cairo_translate (cr,
+ uniform_random (0, width),
+ uniform_random (0, height));
+ cairo_rotate (cr, uniform_random (-M_PI,M_PI));
+ cairo_rectangle (cr, 0, 0, uniform_random (0, width), 2);
+ cairo_restore (cr);
+ }
+
+ cairo_perf_timer_start ();
+
+ while (loops--)
+ cairo_fill_preserve (cr);
+
+ cairo_perf_timer_stop ();
+
+ cairo_new_path (cr);
+
+ return cairo_perf_timer_elapsed ();
+}
+
+void
+many_fills (cairo_perf_t *perf, cairo_t *cr, int width, int height)
+{
+ if (! cairo_perf_can_run (perf, "many-fills", NULL))
+ return;
+
+ cairo_perf_run (perf, "many-fills-halign", do_many_fills_ha, NULL);
+ cairo_perf_run (perf, "many-fills-valign", do_many_fills_va, NULL);
+ cairo_perf_run (perf, "many-fills-horizontal", do_many_fills_h, NULL);
+ cairo_perf_run (perf, "many-fills-vertical", do_many_fills_v, NULL);
+ cairo_perf_run (perf, "many-fills-random", do_many_fills, NULL);
+}
commit 2d8c63671a5eeca2703cab7506ad59144fe74219
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Tue Aug 9 16:06:02 2011 +0100
build: Add a missing cairo-backend-private.h
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/Makefile.sources b/src/Makefile.sources
index 97f452a..b5e4805 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -55,6 +55,7 @@ cairo_private = \
cairo-analysis-surface-private.h \
cairo-arc-private.h \
cairo-atomic-private.h \
+ cairo-backend-private.h \
cairo-box-private.h \
cairo-boxes-private.h \
cairo-cache-private.h \
More information about the cairo-commit
mailing list