Pango: slight performance tweak.

["Patrick Hallinan" <patrick j hallinan gmail com>]

I've made a change to pango-layout.c.  When fitting text in a line, the current algorithm does a linear search to find the break.   I thought that performance would be further increased by storing character width cumulatively (rather than differentially) so that a binary search could be performed.  I made the change and I think I see a 35% reduction in search time for the ONE use case I tried.  I ran this:

 ./pango-view --wrap=word --width=800 test-long-paragraph.txt

and counted the number of loops to find the "width" breakpoint, then counted the number of loops to find the line break.

The way this works is once the character width is stored cummulatively you can get the width for however many characters like this:

  width = state->width[state->log_widths_offset + num_characters] -  state->width[state->log_widths_offset];

The routine does a binary search for the number of characters that will fit on the line then does a linear search backwards for a proper line break.


Index: pango-glyph.h
===================================================================
--- pango-glyph.h	(revision 2271)
+++ pango-glyph.h	(working copy)
@@ -100,6 +100,12 @@
 						     PangoRectangle   *ink_rect,
 						     PangoRectangle   *logical_rect);
 
+void pango_glyph_string_get_cummulative_widths (PangoGlyphString *glyphs,
+					        const char       *text,
+					        int               length,
+					        int               embedding_level,
+					        int              *cummulative_width);
+
 void pango_glyph_string_get_logical_widths (PangoGlyphString *glyphs,
 					    const char       *text,
 					    int               length,
Index: glyphstring.c
===================================================================
--- glyphstring.c	(revision 2271)
+++ glyphstring.c	(working copy)
@@ -297,6 +297,79 @@
  * @text: the text corresponding to the glyphs
  * @length: the length of @text, in bytes
  * @embedding_level: the embedding level of the string
+ * @cummulative_width: an array whose length is g_utf8_strlen (text, length) + 1
+ *                  to be filled with the cummulative character widths. The first
+ *                  entry is always 0.
+ *
+ * Given a #PangoGlyphString resulting from pango_shape() and the corresponding
+ * text, determine the screen width corresponding to each character. When
+ * multiple characters compose a single cluster, the width of the entire
+ * cluster is divided equally among the characters.
+ **/
+void
+pango_glyph_string_get_cummulative_widths (PangoGlyphString *glyphs,
+				          const char       *text,
+				          int               length,
+				          int               embedding_level,
+				          int              *cummulative_width)
+{
+  int i, j;
+  int last_cluster = 0;
+  int width = 0;
+  int last_cluster_width = 0;
+  const char *p = text;		/* Points to start of current cluster */
+  int cummulative = 0;
+
+  if (cummulative_width) cummulative_width[0] = 0;
+
+  for (i=0; i<=glyphs->num_glyphs; i++)
+    {
+      int glyph_index = (embedding_level % 2 == 0) ? i : glyphs->num_glyphs - i - 1;
+
+      /* If this glyph belongs to a new cluster, or we're at the end, find
+       * the start of the next cluster, and assign the widths for this cluster.
+       */
+      if (i == glyphs->num_glyphs || p != text + glyphs->log_clusters[glyph_index])
+	{
+	  int next_cluster = last_cluster;
+
+	  if (i < glyphs->num_glyphs)
+	    {
+	      while (p < text + glyphs->log_clusters[glyph_index])
+		{
+		  next_cluster++;
+		  p = g_utf8_next_char (p);
+		}
+	    }
+	  else
+	    {
+	      while (p < text + length)
+		{
+		  next_cluster++;
+		  p = g_utf8_next_char (p);
+		}
+	    }
+
+	  for (j = last_cluster; j < next_cluster; j++)
+	    cummulative = cummulative_width[j+1] = 
+              (width - last_cluster_width) / (next_cluster - last_cluster) + 
+               cummulative;
+
+	  last_cluster = next_cluster;
+	  last_cluster_width = width;
+	}
+
+      if (i < glyphs->num_glyphs)
+	width += glyphs->glyphs[glyph_index].geometry.width;
+    }
+}
+
+/**
+ * pango_glyph_string_get_logical_widths:
+ * @glyphs: a #PangoGlyphString
+ * @text: the text corresponding to the glyphs
+ * @length: the length of @text, in bytes
+ * @embedding_level: the embedding level of the string
  * @logical_widths: an array whose length is g_utf8_strlen (text, length)
  *                  to be filled in with the resulting character widths.
  *
Index: pango-layout.c
===================================================================
--- pango-layout.c	(revision 2271)
+++ pango-layout.c	(working copy)
@@ -30,6 +30,9 @@
 
 #include "pango-layout-private.h"
 
+#define GET_WIDTH(num_characters)  \
+  (state->width[state->log_widths_offset + num_characters] -  \
+   state->width[state->log_widths_offset])
 
 typedef struct _Extents Extents;
 typedef struct _ItemProperties ItemProperties;
@@ -3014,7 +3017,7 @@
   int start_offset;		/* Character offset of first item in state->items in layout->text */
   PangoGlyphString *glyphs;	/* Glyphs for the first item in state->items */
   ItemProperties properties;	/* Properties for the first item in state->items */
-  PangoGlyphUnit *log_widths;	/* Logical widths for first item in state->items.. */
+  PangoGlyphUnit *width;	/* Logical widths for first item in state->items.. */
   int log_widths_offset;        /* Offset into log_widths to the point corresponding
 				 * to the remaining portion of the first item */
 };
@@ -3082,7 +3085,7 @@
       if (state->log_widths_offset > 0)
 	pango_glyph_string_free (state->glyphs);
       state->glyphs = NULL;
-      g_free (state->log_widths);
+      g_free (state->width);
     }
 
   line->runs = g_slist_prepend (line->runs, run);
@@ -3160,7 +3163,7 @@
       pango_layout_get_item_properties (item, &state->properties);
       state->glyphs = shape_run (line, state, item);
 
-      state->log_widths = NULL;
+      state->width = NULL;
       state->log_widths_offset = 0;
 
       processing_new_item = TRUE;
@@ -3188,8 +3191,7 @@
     }
   else
     {
-      for (i = 0; i < item->num_chars; i++)
-	width += state->log_widths[state->log_widths_offset + i];
+      width = GET_WIDTH(item->num_chars);
     }
 
   if ((width <= state->remaining_width || (item->num_chars == 1 && !line->runs)) &&
@@ -3211,33 +3213,66 @@
 
       if (processing_new_item)
 	{
-	  state->log_widths = g_new (PangoGlyphUnit, item->num_chars);
-	  pango_glyph_string_get_logical_widths (state->glyphs,
-						 layout->text + item->offset, item->length, item->analysis.level,
-						 state->log_widths);
+	  state->width = g_new (PangoGlyphUnit, item->num_chars+1);
+	  pango_glyph_string_get_cummulative_widths (state->glyphs,
+					             layout->text + item->offset, item->length, item->analysis.level,
+						     state->width);
 	}
 
     retry_break:
 
       /* See how much of the item we can stuff in the line
        */
-      width = 0;
-      for (num_chars = 0; num_chars < item->num_chars; num_chars++)
-	{
-	  if (width > state->remaining_width)
-	    break;
 
-	  /* If there are no previous runs we have to take care to grab at least one char. */
-	  if (can_break_at (layout, state->start_offset + num_chars, retrying_with_char_breaks) &&
-	      (num_chars > 0 || line->runs))
-	    {
-	      break_num_chars = num_chars;
-	      break_width = width;
-	    }
+      width = GET_WIDTH(item->num_chars);
 
-	  width += state->log_widths[state->log_widths_offset + num_chars];
-	}
+      if (width <= state->remaining_width)
+        {
+          num_chars = item->num_chars;
+        }
+      else /* Search for boundary */
+        {
+          int lo = 1, hi = item->num_chars;
+          /* Binary Search for width boundary */
+          while (1)
+            {
+              if (lo>hi)
+                  break;
+              num_chars = lo+(hi-lo)/2;               
+              width = GET_WIDTH(num_chars);
+              if (lo == hi || width == state->remaining_width)
+                break;
+              else if (width > state->remaining_width)
+                hi = num_chars-1;
+              else
+                lo = num_chars+1;
+            }
 
+          /* Tune num_chars to bottom side of boundary */
+          if ( (num_chars) < item->num_chars && 
+                GET_WIDTH (num_chars+1) < state->remaining_width )
+            { 
+              num_chars++;
+            }
+          else if ( (num_chars) > 0 && 
+                GET_WIDTH (num_chars) > state->remaining_width )
+            { 
+              num_chars--;
+            }
+        }
+
+      /* Linear search for break point */
+      for ( ; num_chars >= 0 ; num_chars--)
+        {
+          if (can_break_at (layout, state->start_offset + num_chars, retrying_with_char_breaks) &&
+             (num_chars > 0 || line->runs))
+              {
+                break_num_chars = num_chars;
+                break_width     = GET_WIDTH(num_chars);
+                break;
+              }
+        }
+
       if (layout->wrap == PANGO_WRAP_WORD_CHAR && force_fit && break_width > state->remaining_width && !retrying_with_char_breaks)
 	{
 	  retrying_with_char_breaks = TRUE;
@@ -3299,7 +3334,7 @@
 	{
 	  pango_glyph_string_free (state->glyphs);
 	  state->glyphs = NULL;
-	  g_free (state->log_widths);
+	  g_free (state->width);
 
 	  return BREAK_NONE_FIT;
 	}
@@ -3705,7 +3740,7 @@
 	  state.line_start_index = start - layout->text;
 
 	  state.glyphs = NULL;
-	  state.log_widths = NULL;
+	  state.width = NULL;
 
 	  while (state.items)
 	    process_line (layout, &state);