PATCH: Minor performance improvements to Bentley-Ottman algorithm

From b2768f5561a63b1867b58a660c6f6c0f1062d792 Mon Sep 17 00:00:00 2001
From: Marko Kuukkanen <[email protected]>
Date: Thu, 21 Feb 2013 13:30:22 +0200
Subject: [PATCH] [perf] Small optimizations to bentley-ottman implementation

---
 src/cairo-bentley-ottmann.c |   85 ++++++++++++++++++++++++++++++++++++-------
 src/cairo-combsort-inline.h |    2 +-
 2 files changed, 72 insertions(+), 15 deletions(-)

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 0e1a3f5..b2d7015 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -569,15 +569,17 @@ _cairo_bo_sweep_line_compare_edges (const cairo_bo_sweep_line_t	*sweep_line,
 {
     int cmp;
 
+    /* Most of the time the edges are not identical and we fall into
+     * either of these cases. */
+    if (MAX (a->edge.line.p1.x, a->edge.line.p2.x) <
+	MIN (b->edge.line.p1.x, b->edge.line.p2.x))
+	return -1;
+    else if (MIN (a->edge.line.p1.x, a->edge.line.p2.x) >
+	     MAX (b->edge.line.p1.x, b->edge.line.p2.x))
+	return 1;
+
     /* compare the edges if not identical */
     if (! _line_equal (&a->edge.line, &b->edge.line)) {
-	if (MAX (a->edge.line.p1.x, a->edge.line.p2.x) <
-	    MIN (b->edge.line.p1.x, b->edge.line.p2.x))
-	    return -1;
-	else if (MIN (a->edge.line.p1.x, a->edge.line.p2.x) >
-		 MAX (b->edge.line.p1.x, b->edge.line.p2.x))
-	    return 1;
-
 	cmp = edges_compare_x_for_y (a, b, sweep_line->current_y);
 	if (cmp)
 	    return cmp;
@@ -876,7 +878,13 @@ cairo_bo_event_compare (const cairo_bo_event_t *a,
 {
     int cmp;
 
-    cmp = _cairo_bo_point32_compare (&a->point, &b->point);
+    /* At least in gcc ARM compiler this is faster than calling
+     * inlined _cairo_bo_point32_compare */
+    cmp = a->point.y - b->point.y;
+    if (cmp)
+	return cmp;
+
+    cmp = a->point.x - b->point.x;
     if (cmp)
 	return cmp;
 
@@ -1040,11 +1048,59 @@ _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
     return event;
 }
 
-CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
+CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_comb_sort,
 			cairo_bo_event_t *,
 			cairo_bo_event_compare)
 
 static void
+_cairo_bo_event_queue_sort (cairo_bo_event_t **base,
+			    unsigned int nmemb)
+{
+#define SWAP(x,y) if (cairo_bo_event_compare (base[x], base[y]) > 0) { \
+  tmp = base[x]; \
+  base[x] = base[y]; \
+  base[y] = tmp; \
+}
+    cairo_bo_event_t *tmp;
+    /* For small lists, use optimal sorting networks (Bose-Nelson) */
+    switch (nmemb) {
+	case 2:
+	    SWAP (0, 1);
+	    break;
+	case 3:
+	    SWAP (1, 2); SWAP (0, 2); SWAP (0, 1);
+	    break;
+	case 4:
+	    SWAP (0, 1); SWAP (2, 3); SWAP (0, 2); SWAP (1, 3); SWAP (1, 2);
+	    break;
+	case 5:
+	    SWAP (0, 1); SWAP (3, 4); SWAP (2, 4); SWAP (2, 3); SWAP(0, 3);
+	    SWAP (0, 2); SWAP (1, 4); SWAP (1, 3); SWAP (1, 2);
+	    break;
+	case 6:
+	    SWAP (1, 2); SWAP (0, 2); SWAP (0, 1); SWAP (4, 5); SWAP (3, 5);
+	    SWAP (3, 4); SWAP (0, 3); SWAP (1, 4); SWAP (2, 5); SWAP (2, 4);
+	    SWAP (1, 3); SWAP (2, 3);
+	    break;
+	case 7:
+	    SWAP (1, 2); SWAP (0, 2); SWAP (0, 1); SWAP (3, 4); SWAP (5, 6);
+	    SWAP (3, 5); SWAP (4, 6); SWAP (4, 5); SWAP (0, 4); SWAP (0, 3);
+	    SWAP (1, 5); SWAP (2, 6); SWAP (2, 5); SWAP (1, 3); SWAP (2, 4);
+	    SWAP(2, 3);
+	    break;
+	case 8:
+	    SWAP (0, 1); SWAP (2, 3); SWAP (0, 2); SWAP (1, 3); SWAP (1, 2);
+	    SWAP (4, 5); SWAP (6, 7); SWAP (4, 6); SWAP (5, 7); SWAP (5, 6);
+	    SWAP (0, 4); SWAP (1, 5); SWAP (1, 4); SWAP (2, 6); SWAP (3, 7);
+	    SWAP (3, 6); SWAP (2, 4); SWAP (3, 5); SWAP (3, 4);
+	    break;
+	default:
+	    _cairo_bo_event_queue_comb_sort (base, nmemb);
+    }
+#undef SWAP
+}
+
+static void
 _cairo_bo_event_queue_init (cairo_bo_event_queue_t	 *event_queue,
 			    cairo_bo_event_t		**start_events,
 			    int				  num_events)
@@ -1327,6 +1383,12 @@ edges_colinear (cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
 	return p;
     }
 
+    /* Most of the time slopes are not identical, so check this first */
+    if (_slope_compare (a, b)) {
+	a->colinear = MARK_COLINEAR(b, 0);
+	return FALSE;
+    }
+
     p = 0;
     p |= (a->edge.line.p1.x == b->edge.line.p1.x) << 0;
     p |= (a->edge.line.p1.y == b->edge.line.p1.y) << 1;
@@ -1337,11 +1399,6 @@ edges_colinear (cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
 	return TRUE;
     }
 
-    if (_slope_compare (a, b)) {
-	a->colinear = MARK_COLINEAR(b, 0);
-	return FALSE;
-    }
-
     /* The choice of y is not truly arbitrary since we must guarantee that it
      * is greater than the start of either line.
      */
diff --git a/src/cairo-combsort-inline.h b/src/cairo-combsort-inline.h
index d359fae..1d9456b 100644
--- a/src/cairo-combsort-inline.h
+++ b/src/cairo-combsort-inline.h
@@ -41,7 +41,7 @@ _cairo_combsort_newgap (unsigned int gap)
   gap = 10 * gap / 13;
   if (gap == 9 || gap == 10)
     gap = 11;
-  if (gap < 1)
+  else if (gap < 1)
     gap = 1;
   return gap;
 }
-- 
1.7.9.5