[PATCH] [tessellator] Use a combsort for sorting the event queue.
Chris Wilson
chris at chris-wilson.co.uk
Tue Oct 7 14:09:37 PDT 2008
In my experiments using cairo-perf, the inlined combsort is ~20% quicker
than the library qsort.
---
src/Makefile.am | 3 ++
src/cairo-bentley-ottmann.c | 42 +++++++++++++-----------
src/cairo-combsort-fragment.c | 72 +++++++++++++++++++++++++++++++++++++=
++++
3 files changed, 98 insertions(+), 19 deletions(-)
create mode 100644 src/cairo-combsort-fragment.c
diff --git a/src/Makefile.am b/src/Makefile.am
index bf87efb..5d1065d 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -41,6 +41,9 @@ BUILT_SOURCES +=3D cairo-features.h cairo-supported-feat=
ures.h
cairo-features.h cairo-supported-features.h:
cd $(top_builddir) && ./config.status src/$@
=20
+# Fragments
+EXTRA_DIST +=3D cairo-combsort-fragment.c
+
pkgconfigdir =3D $(libdir)/pkgconfig
pkgconfig_DATA =3D $(enabled_cairo_pkgconf)
=20
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 2d8e324..17b3599 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -630,21 +630,18 @@ cairo_bo_event_compare_abstract (void *list,
}
=20
static int
-cairo_bo_event_compare_pointers (void const *voida,
- void const *voidb)
+cairo_bo_event_compare_pointers (const cairo_bo_event_t *a,
+ const cairo_bo_event_t *b)
{
- cairo_bo_event_t const * const *a =3D voida;
- cairo_bo_event_t const * const *b =3D voidb;
- if (*a !=3D *b) {
- int cmp =3D cairo_bo_event_compare (*a, *b);
- if (cmp)
- return cmp;
- if (*a < *b)
- return -1;
- if (*a > *b)
- return +1;
- }
- return 0;
+ int cmp;
+
+ if (a =3D=3D b)
+ return 0;
+ cmp =3D cairo_bo_event_compare (a, b);
+ if (cmp)
+ return cmp;
+
+ return a - b;
}
=20
static inline cairo_int64_t
@@ -957,6 +954,14 @@ _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event=
_queue)
return intersection;
}
=20
+#define _CAIRO_QS_NAME _cairo_bo_event_queue_sort
+#define _CAIRO_QS_TYPE cairo_bo_event_t *
+#define _CAIRO_QS_COMPARE cairo_bo_event_compare_pointers
+#include "cairo-combsort-fragment.c"
+#undef _CAIRO_QS_NAME
+#undef _CAIRO_QS_TYPE
+#undef _CAIRO_QS_COMPARE
+
static cairo_status_t
_cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
cairo_bo_edge_t *edges,
@@ -989,8 +994,8 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t *eve=
nt_queue,
event_queue->next_startstop_event_index =3D 0;
=20
for (i =3D 0; i < num_edges; i++) {
- sorted_event_ptrs[2*i] =3D &events[2*i];
- sorted_event_ptrs[2*i+1] =3D &events[2*i+1];
+ sorted_event_ptrs[i] =3D &events[2*i];
+ sorted_event_ptrs[i+num_edges] =3D &events[2*i+1];
=20
/* Initialize "middle" to top */
edges[i].middle =3D edges[i].top;
@@ -1006,9 +1011,8 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t *e=
vent_queue,
edges[i].bottom);
}
=20
- qsort (sorted_event_ptrs, num_events,
- sizeof(cairo_bo_event_t *),
- cairo_bo_event_compare_pointers);
+ _cairo_bo_event_queue_sort (sorted_event_ptrs, num_events);
+
return CAIRO_STATUS_SUCCESS;
}
=20
diff --git a/src/cairo-combsort-fragment.c b/src/cairo-combsort-fragment.c
new file mode 100644
index 0000000..10b63c1
--- /dev/null
+++ b/src/cairo-combsort-fragment.c
@@ -0,0 +1,72 @@
+/*
+ * Copyright =C2=A9 2008 Chris Wilson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Chris Wilson
+ *
+ * Contributor(s):
+ * Chris Wilson <chris at chris-wilson.co.uk>
+ */
+
+/* This fragment implements a comb sort (specifically combsort11) */
+
+#ifndef _HAVE_CAIRO_COMBSORT_NEWGAP
+#define _HAVE_CAIRO_COMBSORT_NEWGAP
+static inline unsigned int
+_cairo_combsort_newgap (unsigned int gap)
+{
+ gap =3D 10 * gap / 13;
+ if (gap =3D=3D 9 || gap =3D=3D 10)
+ gap =3D 11;
+ if (gap < 1)
+ gap =3D 1;
+ return gap;
+}
+#endif
+
+static void
+_CAIRO_QS_NAME (_CAIRO_QS_TYPE *base, unsigned int nmemb)
+{
+ unsigned int gap =3D nmemb;
+ unsigned int i, j;
+ int swapped;
+
+ do {
+ gap =3D _cairo_combsort_newgap (gap);
+ swapped =3D 0;
+ for (i =3D 0; i < nmemb-gap ; i++) {
+ j =3D i + gap;
+ if (_CAIRO_QS_COMPARE (base[i], base[j]) > 0 ) {
+ _CAIRO_QS_TYPE tmp;
+ tmp =3D base[i];
+ base[i] =3D base[j];
+ base[j] =3D tmp;
+ swapped =3D 1;
+ }
+ }
+ } while (gap > 1 || swapped);
+}
--=20
1.5.6.3
--=-ZiiESaLDo1Qm+q2D8ALU
Content-Description:
Content-Disposition: inline; filename*0=0006--tessellator-Simplify-dequeuing-by-using-a-sentinel.patc; filename*1=h
Content-Type: text/x-patch; charset="UTF-8"
Content-Transfer-Encoding: 7bit
More information about the cairo
mailing list