[skiplist] Avoid repeated calls to compare on the same element when inserting.

During insertion we must traverse the skiplist in order to find the
insertion point for the new element. As we descend each level, the next
element in the chain for this level is sometimes the same as the one we
just compared against (and know that the new element is greater than).
Hence we can skip the search on that level and descend to the next. During
world_map this reduces the number of calls into _sweep_line_elt_compare()
by ~2.5% (and when performing trapezoidation on strokes gives a similar
speed up of about 2% - not bad for the addition of a single line.)

1 files changed, 10 insertions, 6 deletions

diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index ebeb52c8..e2b793e1 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -322,16 +322,20 @@ _cairo_skip_list_insert (cairo_skip_list_t *list, void *data, int unique)
     /*
      * Find links along each chain
      */
+    elt = NULL;
     next = list->chains;
     for (i = list->max_level; --i >= 0; )
     {
-	for (; (elt = next[i]); next = elt->next)
+	if (elt != next[i])
 	{
-	    int cmp = list->compare (list, ELT_DATA(elt), data);
-	    if (unique && 0 == cmp)
-		return ELT_DATA(elt);
-	    if (cmp > 0)
-		break;
+	    for (; (elt = next[i]); next = elt->next)
+	    {
+		int cmp = list->compare (list, ELT_DATA(elt), data);
+		if (unique && 0 == cmp)
+		    return ELT_DATA(elt);
+		if (cmp > 0)
+		    break;
+	    }
 	}
         update[i] = next;
 	if (next != list->chains)