Re: FW: rTree insert optimization.

"[email protected]" <[email protected]> Fri, 2 Mar 2012 14:14:42 +0100

Newsgroups	gmane.comp.lib.cairo
Message-ID	<[email protected]>

Hello,

Please check attached pictures.
 
These pictures are cache glyph surface without patch called "glyph_surface_old.png" and "glyph_surface_new.png" with my patch.

You can see - what my patch made more accurately allocation space for glyphs in cache texture.

I tested cairo-perf-micro with "text" keyword and egl backend (based on nouveau driver + MESA OpenGLES)  (target board: PC i7 6G mem.).
Performance in both case is not differ.

Also I attached test case with my modifications (change font size for each loop), and latest version of my patch.

Best regards,
Valery Volgutov.

--
cairo mailing list
[email protected]
http://lists.cairographics.org/mailman/listinfo/cairo

glyph_texture_new.png (image/png, 22 KB) - not displayed

glyph_texture_old.png (image/png, 25.2 KB) - not displayed

0001-gl-rTree-optimization-Adds-biggest-node-to-end-of-fr.patch (text/x-patch, 4.5 KB)

From 5beed2f6a123f7e6927750d9a2633c036907db46 Mon Sep 17 00:00:00 2001
From: Valery Volgutov <[email protected]>
Date: Wed, 29 Feb 2012 18:57:36 +0400
Subject: [PATCH] gl: rTree optimization: Adds biggest node to end of free
 list. Change text performance test case (add changing font
 size for each loop)

---
 perf/micro/text.c         |    5 +++--
 src/cairo-rtree-private.h |    3 ++-
 src/cairo-rtree.c         |   37 +++++++++++++++++++++++++++++--------
 3 files changed, 34 insertions(+), 11 deletions(-)

diff --git a/perf/micro/text.c b/perf/micro/text.c
index cdb3199..7d1bcfc 100644
--- a/perf/micro/text.c
+++ b/perf/micro/text.c
@@ -29,15 +29,16 @@ static cairo_time_t
 do_text (cairo_t *cr, int width, int height, int loops)
 {
     const char text[] = "the jay, pig, fox, zebra and my wolves quack";
+    int sizes[] = { 8, 15, 7, 19, 5, 6, 23, 9, 4, 24, 13, 14, 10, 16, 18, 12, 11, 17 };
     int len = strlen (text);
+    int slen = sizeof (sizes) / sizeof (sizes[0]);
     double x, y;
     int i = 0, j = 0;
 
-    cairo_set_font_size (cr, 9);
-
     cairo_perf_timer_start ();
 
     while (loops--) {
+	cairo_set_font_size (cr, sizes[loops % slen]);
 	do {
 	    cairo_move_to (cr, 0, j++ * 10);
 	    cairo_show_text (cr, text + i);
diff --git a/src/cairo-rtree-private.h b/src/cairo-rtree-private.h
index b8db477..d2ab130 100644
--- a/src/cairo-rtree-private.h
+++ b/src/cairo-rtree-private.h
@@ -75,7 +75,8 @@ _cairo_rtree_node_create (cairo_rtree_t		 *rtree,
 			  int			  x,
 			  int			  y,
 			  int			  width,
-			  int			  height);
+			  int			  height,
+			  int			  tail);
 
 cairo_private cairo_status_t
 _cairo_rtree_node_insert (cairo_rtree_t *rtree,
diff --git a/src/cairo-rtree.c b/src/cairo-rtree.c
index dbc0409..b8f3ee3 100644
--- a/src/cairo-rtree.c
+++ b/src/cairo-rtree.c
@@ -45,7 +45,8 @@ _cairo_rtree_node_create (cairo_rtree_t		 *rtree,
 			  int			  x,
 			  int			  y,
 			  int			  width,
-			  int			  height)
+			  int			  height,
+			  int			  tail)
 {
     cairo_rtree_node_t *node;
 
@@ -64,7 +65,10 @@ _cairo_rtree_node_create (cairo_rtree_t		 *rtree,
     node->width  = width;
     node->height = height;
 
-    cairo_list_add (&node->link, &rtree->available);
+    if (!tail)
+	cairo_list_add (&node->link, &rtree->available);
+    else
+	cairo_list_add_tail (&node->link, &rtree->available);
 
     return node;
 }
@@ -128,7 +132,7 @@ _cairo_rtree_node_insert (cairo_rtree_t *rtree,
 	i = 0;
 	node->children[i] = _cairo_rtree_node_create (rtree, node,
 						      node->x, node->y,
-						      width, height);
+						      width, height, 0);
 	if (unlikely (node->children[i] == NULL))
 	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 	i++;
@@ -137,7 +141,7 @@ _cairo_rtree_node_insert (cairo_rtree_t *rtree,
 	    node->children[i] = _cairo_rtree_node_create (rtree, node,
 							  node->x + width,
 							  node->y,
-							  w, height);
+							  w, height, 0);
 	    if (unlikely (node->children[i] == NULL))
 		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 	    i++;
@@ -147,7 +151,7 @@ _cairo_rtree_node_insert (cairo_rtree_t *rtree,
 	    node->children[i] = _cairo_rtree_node_create (rtree, node,
 							  node->x,
 							  node->y + height,
-							  width, h);
+							  width, h, 0);
 	    if (unlikely (node->children[i] == NULL))
 		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 	    i++;
@@ -156,7 +160,7 @@ _cairo_rtree_node_insert (cairo_rtree_t *rtree,
 		node->children[i] = _cairo_rtree_node_create (rtree, node,
 							      node->x + width,
 							      node->y + height,
-							      w, h);
+							      w, h, 1);
 		if (unlikely (node->children[i] == NULL))
 		    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 		i++;
@@ -199,13 +203,30 @@ _cairo_rtree_insert (cairo_rtree_t	     *rtree,
 	             cairo_rtree_node_t	    **out)
 {
     cairo_rtree_node_t *node;
+    cairo_rtree_node_t *found = NULL;
+    int mind = 0x7fffffff;
+    int dw;
+    int dh;
+    int d;
 
     cairo_list_foreach_entry (node, cairo_rtree_node_t,
 			      &rtree->available, link)
     {
-	if (node->width >= width && node->height >= height)
-	    return _cairo_rtree_node_insert (rtree, node, width, height, out);
+	dw = node->width - width;
+	dh = node->height - height;
+	d = dw > dh ? dh: dw;
+
+	if (dw >= 0 && dh >= 0 && mind > d)
+	{
+	    mind = d;
+	    if (mind == 0)
+		return _cairo_rtree_node_insert (rtree, node, width, height, out);
+
+	    found = node;
+	}
     }
+    if (found)
+	return _cairo_rtree_node_insert (rtree, found, width, height, out);
 
     return CAIRO_INT_STATUS_UNSUPPORTED;
 }
-- 
1.7.6.5