Patch to speed up window invalidation

[Sven Neumann <sven gimp org>]

Hi,

I've found that GDK spends a considerable time invalidating windows.
The function gdk_window_invalidate_region_maybe_recurse() is rather
inefficient since it has to deal with the possibility that the
invalidated region is not a simple rectangle. Some testing showed that
in by far the most cases (> 90%) a simple rectangle would be
sufficient to describe the region. Although due to the recursive
nature of the code the region is intersected with the windows' visible
region for all of the children while it would be enough to do this in
the first recursion level only.

The attached patch checks the complexity of the invalidated region
after intersecting it with the visible region and calls the new
function gdk_window_invalidate_rect_maybe_recurse() if it is a simple
rectangle. gdk_window_invalidate_rect_maybe_recurse() calls itself
recursively then. Due to the fact that it is a lot simpler than its
region counterpart the inner loop is speed up for the common case of
window invalidation. I've noticed a speedup of several percent for
almost all tests when running 'testgtk --bench ALL:20'. In interactive
use the performance gain should be even larger.

Please let me know if you like the patch.


Salut, Sven

Index: gdk/gdkwindow.c
===================================================================
RCS file: /cvs/gnome/gtk+/gdk/gdkwindow.c,v
retrieving revision 1.130
diff -u -p -r1.130 gdkwindow.c
--- gdk/gdkwindow.c	2002/01/13 20:13:34	1.130
+++ gdk/gdkwindow.c	2002/01/15 11:21:33
@@ -31,6 +31,8 @@
 #include "gdkdrawable.h"
 #include "gdkpixmap.h"
 
+#include "gdkregion-generic.h"
+
 #define USE_BACKING_STORE	/* Appears to work on Win32, too, now. */
 
 typedef struct _GdkWindowPaint GdkWindowPaint;
@@ -2086,7 +2088,8 @@ gdk_window_process_updates_internal (Gdk
 	  window_rect.width = width;
 	  window_rect.height = height;
 
-	  save_region = _gdk_windowing_window_queue_antiexpose (window, update_area);
+	  save_region = _gdk_windowing_window_queue_antiexpose (window, 
+                                                                update_area);
       
 	  event.expose.type = GDK_EXPOSE;
 	  event.expose.window = gdk_window_ref (window);
@@ -2197,48 +2200,86 @@ gdk_window_process_updates (GdkWindow *w
     }
 }
 
-/**
- * gdk_window_invalidate_rect:
- * @window: a #GdkWindow
- * @rect: rectangle to invalidate
- * @invalidate_children: whether to also invalidate child windows
- *
- * A convenience wrapper around gdk_window_invalidate_region() which
- * invalidates a rectangular region. See
- * gdk_window_invalidate_region() for details.
- * 
- **/
-void
-gdk_window_invalidate_rect   (GdkWindow    *window,
-			      GdkRectangle *rect,
-			      gboolean      invalidate_children)
+  /* Draw ugly color all over the rectangle */
+static void
+gdk_window_colorify_rect (GdkWindow    *window,
+                          GdkRectangle *rect)
 {
-  GdkRectangle window_rect;
-  GdkRegion *region;
-  GdkWindowObject *private = (GdkWindowObject *)window;
+  GdkGC *ugly_gc;
+  GdkColor ugly_color = { 0, 60000, 10000, 10000 };
+  
+  ugly_gc = gdk_gc_new (window);
 
-  g_return_if_fail (window != NULL);
-  g_return_if_fail (GDK_IS_WINDOW (window));
+  gdk_gc_set_rgb_fg_color (ugly_gc, &ugly_color);
+  
+  gdk_draw_rectangle (window,
+                      ugly_gc,
+                      TRUE,
+                      rect->x, rect->y,
+                      rect->width, rect->height);
+  
+  g_object_unref (G_OBJECT (ugly_gc));
+}
 
-  if (GDK_WINDOW_DESTROYED (window))
-    return;
+static void
+gdk_window_invalidate_rect_maybe_recurse (GdkWindow    *window,
+                                          GdkRectangle *rect,
+                                          gboolean (*child_func) (GdkWindow *, 
+                                                                  gpointer),
+                                          gpointer      user_data)
+{
+  GdkWindowObject *private = (GdkWindowObject *) window;
   
-  if (private->input_only || !GDK_WINDOW_IS_MAPPED (window))
+  if (!rect->width || !rect->height)
     return;
 
-  if (!rect)
+  if (debug_updates)
+    gdk_window_colorify_rect (window, rect);
+
+  if (private->update_area)
     {
-      window_rect.x = 0;
-      window_rect.y = 0;
-      gdk_drawable_get_size (GDK_DRAWABLE (window),
-                             &window_rect.width,
-                             &window_rect.height);
-      rect = &window_rect;
+      gdk_region_union_with_rect (private->update_area, rect);
+    }
+  else
+    {
+      update_windows = g_slist_prepend (update_windows, window);
+      private->update_area = gdk_region_rectangle (rect);
+      
+      if (!private->update_freeze_count && !update_idle)
+        update_idle = g_idle_add_full (GDK_PRIORITY_REDRAW,
+                                       gdk_window_update_idle, NULL, NULL);
     }
 
-  region = gdk_region_rectangle (rect);
-  gdk_window_invalidate_region (window, region, invalidate_children);
-  gdk_region_destroy (region);
+  if (child_func)
+    {
+      GList *tmp_list;
+      
+      tmp_list = private->children;
+      while (tmp_list)
+        {
+          GdkWindow *child = tmp_list->data;
+          tmp_list = tmp_list->next;
+          
+          if (!GDK_WINDOW_OBJECT (child)->input_only &&
+              !GDK_WINDOW_IS_MAPPED (child) &&
+              !GDK_WINDOW_DESTROYED (child) &&
+              (*child_func) (child, user_data))
+            {
+              GdkRectangle child_rect;
+              gint x, y;
+
+              child_rect = *rect;
+              
+              gdk_window_get_position (child, &x, &y);
+
+              child_rect.x += x;
+              child_rect.y += y;
+		  
+              gdk_window_invalidate_rect_maybe_recurse (child, &child_rect, 
+                                                        child_func, user_data);
+	    }
+	}
+    }
 }
 
 /**
@@ -2269,11 +2310,13 @@ gdk_window_invalidate_rect   (GdkWindow 
 void
 gdk_window_invalidate_maybe_recurse (GdkWindow *window,
 				     GdkRegion *region,
-				     gboolean (*child_func) (GdkWindow *, gpointer),
+				     gboolean (*child_func) (GdkWindow *, 
+                                                             gpointer),
 				     gpointer   user_data)
 {
   GdkWindowObject *private = (GdkWindowObject *)window;
   GdkRegion *visible_region;
+  GdkRectangle  rect;    
 
   g_return_if_fail (window != NULL);
   g_return_if_fail (GDK_IS_WINDOW (window));
@@ -2287,30 +2330,24 @@ gdk_window_invalidate_maybe_recurse (Gdk
   visible_region = gdk_drawable_get_visible_region (window);
   gdk_region_intersect (visible_region, region);
 
-  if (!gdk_region_empty (visible_region))
+  switch (visible_region->numRects)
     {
-      if (debug_updates)
-        {
-          /* Draw ugly color all over the newly-invalid region */
-          GdkRectangle ugly_rect;
-          GdkGC *ugly_gc;
-          GdkColor ugly_color = { 0, 60000, 10000, 10000 };
-          
-          ugly_gc = gdk_gc_new (window);
+    case 0:
+      break;
 
-          gdk_gc_set_rgb_fg_color (ugly_gc, &ugly_color);
-          
-	  gdk_region_get_clipbox (visible_region, &ugly_rect);
+    case 1:
+      gdk_region_get_clipbox (visible_region, &rect);
+      gdk_window_invalidate_rect_maybe_recurse (window, &rect, 
+                                                child_func, user_data);
+      break;
 
-          gdk_draw_rectangle (window,
-                              ugly_gc,
-                              TRUE,
-                              ugly_rect.x, ugly_rect.y,
-                              ugly_rect.width, ugly_rect.height);
-          
-          g_object_unref (G_OBJECT (ugly_gc));
+    default:
+      if (debug_updates)
+        {
+          gdk_region_get_clipbox (visible_region, &rect);  
+          gdk_window_colorify_rect (window, &rect);
         }
-      
+
       if (private->update_area)
 	{
 	  gdk_region_union (private->update_area, visible_region);
@@ -2332,38 +2369,86 @@ gdk_window_invalidate_maybe_recurse (Gdk
 	  tmp_list = private->children;
 	  while (tmp_list)
 	    {
-	      GdkWindowObject *child = tmp_list->data;
+	      GdkWindow *child = tmp_list->data;
 	      tmp_list = tmp_list->next;
 
-	      if (!child->input_only && (*child_func) ((GdkWindow *)child, user_data))
+	      if (!GDK_WINDOW_OBJECT (child)->input_only &&
+                  !GDK_WINDOW_IS_MAPPED (child) &&
+                  (*child_func) (child, user_data))
 		{
 		  GdkRegion *child_region;
 		  gint x, y;
 
-		  gdk_window_get_position ((GdkWindow *)child, &x, &y);
+		  gdk_window_get_position (child, &x, &y);
 
 		  /* This copy could be saved with a little more complexity */
 		  child_region = gdk_region_copy (visible_region);
 		  gdk_region_offset (child_region, -x, -y);
 		  
-		  gdk_window_invalidate_maybe_recurse ((GdkWindow *)child, child_region, child_func, user_data);
+		  gdk_window_invalidate_maybe_recurse (child, child_region, 
+                                                       child_func, user_data);
 		  
 		  gdk_region_destroy (child_region);
 		}
 	    }
 	}
     }
-  
+
   gdk_region_destroy (visible_region);
 }
 
-static gboolean
+static gboolean G_GNUC_CONST
 true_predicate (GdkWindow *window,
 		gpointer   user_data)
 {
   return TRUE;
 }
 
+
+/**
+ * gdk_window_invalidate_rect:
+ * @window: a #GdkWindow
+ * @rect: rectangle to invalidate
+ * @invalidate_children: whether to also invalidate child windows
+ *
+ * A convenience wrapper around gdk_window_invalidate_region() which
+ * invalidates a rectangular region. See
+ * gdk_window_invalidate_region() for details.
+ * 
+ **/
+void
+gdk_window_invalidate_rect (GdkWindow    *window,
+                            GdkRectangle *rect,
+                            gboolean      invalidate_children)
+{
+  GdkRectangle window_rect;
+  GdkWindowObject *private = (GdkWindowObject *)window;
+
+  g_return_if_fail (window != NULL);
+  g_return_if_fail (GDK_IS_WINDOW (window));
+
+  if (GDK_WINDOW_DESTROYED (window))
+    return;
+  
+  if (private->input_only || !GDK_WINDOW_IS_MAPPED (window))
+    return;
+
+  if (!rect)
+    {
+      window_rect.x = 0;
+      window_rect.y = 0;
+      gdk_drawable_get_size (GDK_DRAWABLE (window),
+                             &window_rect.width,
+                             &window_rect.height);
+      rect = &window_rect;
+    }
+
+  gdk_window_invalidate_rect_maybe_recurse (window, rect, 
+                                            invalidate_children ?
+                                              true_predicate : (gboolean (*) (GdkWindow *, gpointer))NULL,
+                                            NULL);
+}
+
 /**
  * gdk_window_invalidate_region:
  * @window: a #GdkWindow
@@ -2528,7 +2613,7 @@ gdk_window_thaw_updates (GdkWindow *wind
 void
 gdk_window_set_debug_updates (gboolean setting)
 {
-  debug_updates = setting;
+  debug_updates = (setting != FALSE);
 }
 
 /**