[glib/wip/async-io-perf: 1/3] gmain: Optimize insertion of matching or higher priority sources

[Colin Walters <walters src gnome org>]

commit 11ba8eb445e0c0404f2231ea397849c523c9d925
Author: Colin Walters <walters verbum org>
Date:   Thu Jun 21 10:16:21 2012 -0400

    gmain: Optimize insertion of matching or higher priority sources
    
    Calling g_source_attach() does an O(n) iteration over all current
    sources until it found the insertion point, while holding the context
    mutex.  This is a serious performance hit for heavy asynchronous I/O,
    because GIOScheduler sends results back to the source context via
    g_source_attach().
    
    A more correct fix for this would be a priority queue, but this patch
    is quite simple - we just walk the source list in reverse instead of
    forwards.  For applications where most sources are the same priority
    (or they have just a few lower-priority sources), this patch is a
    large speedup.
    
    However, this patch will degrade performance in the case of inserting
    a high-priority source for applications which have many lower-priority
    sources.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=619329

 glib/gmain.c |   18 ++++++++++++------
 1 files changed, 12 insertions(+), 6 deletions(-)
---
diff --git a/glib/gmain.c b/glib/gmain.c
index 760f179..fdf8dc7 100644
--- a/glib/gmain.c
+++ b/glib/gmain.c
@@ -233,6 +233,7 @@ struct _GMainContext
 
   guint next_id;
   GSource *source_list;
+  GSource *source_list_last;
   gint in_check_or_prepare;
 
   GPollRec *poll_records, *poll_records_tail;
@@ -819,13 +820,13 @@ g_source_list_add (GSource      *source,
       last_source = source->priv->parent_source->prev;
     }
   else
-    {
-      last_source = NULL;
-      tmp_source = context->source_list;
-      while (tmp_source && tmp_source->priority <= source->priority)
+    { 
+      tmp_source = NULL;
+      last_source = context->source_list_last;
+      while (last_source && last_source->priority > source->priority)
 	{
-	  last_source = tmp_source;
-	  tmp_source = tmp_source->next;
+	  tmp_source = last_source;
+	  last_source = last_source->prev;
 	}
     }
 
@@ -838,6 +839,9 @@ g_source_list_add (GSource      *source,
     last_source->next = source;
   else
     context->source_list = source;
+
+  if (source->next == NULL)
+    context->source_list_last = source;
 }
 
 /* Holds context's lock
@@ -853,6 +857,8 @@ g_source_list_remove (GSource      *source,
 
   if (source->next)
     source->next->prev = source->prev;
+  else
+    context->source_list_last = context->source_list_last->prev;
 
   source->prev = NULL;
   source->next = NULL;