Created attachment 161687 [details] [review]
broken patch

An example approach, this has at least one bug that breaks mainloop-test nondeterministically though. (Run mainloop-test a bunch of times and it will crash sometimes.)

There's a priority queue implementation for glib somewhere in bugzilla, which I've always thought would be the right data structure for this.

Thanks, there are two it looks like: bug 107082 and bug 575074

They may be overkill-ish; the by-far common case here is probably two priorities (default and idle), or perhaps a couple more (redraw priority or something).
However, on the other hand, my patch idea is a fair amount of manual list-manipulation ugliness (and doesn't quite work, ha).

I would expect that a fixed version of my patch is fast, since the usual case will be to find default priority as the first thing in the insertion_points list and then just replace insertion_points->data. i.e. on average for the default priority as highest priority, we're just keeping a pointer to the last-added default-priority source and the list doesn't even really matter.

Probably depends on whether you're planning to add priority queue otherwise, which isn't clear on either of those other two bugs. If adding it, using it seems like a fine approach until proven slow or whatever.

If not adding priority queue or in the meantime, I don't think there's anything inherently wrong with the attached patch in concept, there's just some bug in it. mainloop-test's nondeterminism made it sort of annoying to debug so I haven't been unlazy yet and written a usable test case ;-)

In https://bugzilla.gnome.org/show_bug.cgi?id=626702#c4 it came up that the ordering of main loop sources (they run in the order added, within a priority) is probably an important guarantee, so the patch would need to track the tail of the list to append, not prepend.

commit c5d9a46394a147c8a6c8708046e7459c55d477e4
Author: Paolo Bonzini <pbonzini@redhat.com>
Date:   Tue Jan 25 11:31:41 2011 +0100

    avoid quadratic behavior of GMainLoop when all fd's have the same priority
    
    https://bugzilla.gnome.org/show_bug.cgi?id=640518


Should address this

Isn't that patch a different problem? This bug is about the list of all GSource, not the list of poll fds.

Oh well. Would have been nice :-(

So I have a project which is basically doing the equivalent of "cp -a" on a directory.  The current code was synchronous (GNU coreutils "cp" is too), but I thought I could speed it up a lot by making it asynchronous/parallel; i.e. doing multiple copies at once.

Doing that, imagine my surprise when the async version is *slower*!  There are several reasons for this, but basically 10% of the CPU time is spent in the four lines of code mentioned in this bug.

The reason we hit this so badly is because the GIOScheduler (which is what GSimpleAsyncResult uses) creates an idle source to send the result back to the mainloop, and that calls g_source_attach().

What's worse is that we hold the mutex on the context while doing this - therefore heavily serializing all worker threads on it =(

What's even worse than that is this is all pointless - the priority of all my sources is the default 0.

Created attachment 216943 [details] [review]
GSource: initialise ->priv on construct

For efficiency, we waited until setting up child sources to allocate
->priv.  Simplify things a bit by allocating it from the start.

Created attachment 216944 [details] [review]
gmain: child sources must always have same priority as parent

A child source does not have a priority of its own; it must have the
same priority as its parent. Enforce this in
g_source_set_priority_unlocked().

Created attachment 216945 [details] [review]
GMainContext: reorganize source list to avoid O(n) behavior

Rather than having a single priority-ordered list of GSources, store a
list of queues of each priority level. This means that adding a source
is now O(n) in the number of unique priority levels currently being
used, rather than O(n) in the total number of sources.

I didn't submit this before because I was planning to rebase bug 11059 on top of this, and wasn't sure if I'd end up wanting to change things for that. But then I never got around to that...

An earlier comment mentioned using a priority queue, but that doesn't turn out to be useful, because priority queues aren't designed for iterating, only for add() and pop(). (One of the two priority list implementations linked to above does not even provide an iteration API, and the other provides a horribly inefficient one.)

Review of attachment 216943 [details] [review]:

Hm, I think it's valid to "substruct" (subclass) GSource by embedding it in your own structure.  So we need to keep the code to initialize ->priv if it isn't already.

However - we could allocate it in one malloc block in g_source_new() for the "well known" source types.

Review of attachment 216944 [details] [review]:

Makes sense.

(In reply to comment #13)
> Review of attachment 216943 [details] [review]:
> 
> Hm, I think it's valid to "substruct" (subclass) GSource by embedding it in
> your own structure.

You can do

struct MySource {
  GSource base_source;

  /* other stuff */
};

but you still have to create them by calling g_source_new() (which takes a "struct_size" argument so you can make it allocate more than sizeof(GSource) bytes).

All of the fields in struct GSource are /*< private >*/, and there's no other way to initialize them other than g_source_new().

Review of attachment 216943 [details] [review]:

Ah, sorry, yes.  Makes sense.

Review of attachment 216945 [details] [review]:

::: glib/gmain.c
@@ +200,3 @@
+struct _GSourceList
+{
+  GSource *head, *tail;

I understand when you're saying a priority queue isn't appropriate, but there already exists GQueue, which is exactly this pair.

@@ +863,3 @@
+    context->source_lists = g_list_append (NULL, source_list);
+  else
+    last = g_list_append (last, source_list);

Could use a comment like /* Avoid iterating over list again */

@@ +903,2 @@
   else
+    source_list->head = source;

With GQueue, this mess would just be:

g_queue_push_tail (source_list->queue, source);

@@ +910,1 @@
 g_source_list_remove (GSource      *source,

The g_source_list_*() internal functions really need new names now that they're not operating on a list, but a list of lists (or if you adopt my GQueue suggestion, a list of queues).  How about context_sources_*().  Then this would be:

context_sources_remove (GMainContext *context, GSource *source)

@@ +928,2 @@
   source->prev = NULL;
   source->next = NULL;

source_list = find_source_list_for_priority (context, source->priority, FALSE);
g_queue_remove (source_list->queue, source);

@@ +933,3 @@
+      context->source_lists = g_list_remove (context->source_lists, source_list);
+      g_slice_free (GSourceList, source_list);
+    }

Kind of an open question whether we should delete empty queues immediately.  It's an extra pair of slice alloc/free for the (I assume common) case where you have a list of G_PRIORITY_DEFAULT sources, then you use g_idle_add().

@@ +1858,2 @@
+	      if (callback_data == user_data)
+		break;

Now this only breaks out of the inner while loop.  You need to do add a separate "gboolean found", set it to true here.

@@ +1862,1 @@
 	}

...then if (!found) break;

@@ +1908,1 @@
+	      if (callback_data == user_data)

Ditto here.

@@ +2687,3 @@
+    iter = context->source_lists;
+
+  if (!iter)

if source is NULL, iter is uninitialized here.  I'd just add if (source == NULL) return NULL; at the top.

@@ +2692,3 @@
+  source_list = iter->data;
+  return source_list->head;
+}

Seems like you could move this function up and use it for g_main_context_find_source_by_user_data() and such too.  Though you'd need to add a boolean for whether or not to check SOURCE_DESTROYED().  Or is not doing so a bug in next_valid_source()?

(In reply to comment #17)
> Review of attachment 216945 [details] [review]:
> 
> ::: glib/gmain.c
> @@ +200,3 @@
> +struct _GSourceList
> +{
> +  GSource *head, *tail;
> 
> I understand when you're saying a priority queue isn't appropriate, but there
> already exists GQueue, which is exactly this pair.

Oh blah except I forgot GSource has the next/prev pointers internally, I was thinking of it like GList.  I guess it probably makes sense to keep a local queue implementation here too =/

(In reply to comment #17)
> Kind of an open question whether we should delete empty queues immediately. 
> It's an extra pair of slice alloc/free for the (I assume common) case where you
> have a list of G_PRIORITY_DEFAULT sources, then you use g_idle_add().

So, if we don't delete them immediately, then we either

  a) never delete them, causing slowdowns if the app uses lots of
     different priority values (which is probably rare though)

  b) delete them "eventually", which implies some sort of aging /
     garbage-collecting stuff.

My theory was that gslice is supposed to be optimized for lots of allocs and frees, so I should just do the easy thing...

> @@ +2687,3 @@
> +    iter = context->source_lists;
> +
> +  if (!iter)
> 
> if source is NULL, iter is uninitialized here.  I'd just add if (source ==
> NULL) return NULL; at the top.

no, if source is NULL, then iter = context->source_lists, and the function returns the context's first source. (This extends/preserves the existing behavior of next_valid_source().)

> Seems like you could move this function up and use it for
> g_main_context_find_source_by_user_data() and such too.

Indeed.

> Though you'd need to
> add a boolean for whether or not to check SOURCE_DESTROYED().  Or is not doing
> so a bug in next_valid_source()?

Not sure what you mean. Checking SOURCE_DESTROYED is specific to next_valid_source(), and it can keep doing it on its own.

here are the predefined priorities in gmain:
#define G_PRIORITY_HIGH            -100
#define G_PRIORITY_DEFAULT          0
#define G_PRIORITY_HIGH_IDLE        100
#define G_PRIORITY_DEFAULT_IDLE     200
#define G_PRIORITY_LOW              300

and these are priorities that are used in gtk:
#define GDK_PRIORITY_EVENTS        (G_PRIORITY_DEFAULT)
#define GDK_PRIORITY_REDRAW        (G_PRIORITY_HIGH_IDLE + 20)
#define GTK_PRIORITY_RESIZE        (G_PRIORITY_HIGH_IDLE + 10)
#define GTK_TEXT_VIEW_PRIORITY_VALIDATE (GDK_PRIORITY_REDRAW + 5)
#define GTK_TREE_VIEW_PRIORITY_VALIDATE (GDK_PRIORITY_REDRAW + 5)
#define GTK_TREE_VIEW_PRIORITY_SCROLL_SYNC (GTK_TREE_VIEW_PRIORITY_VALIDATE + 2)
GTK_PRIORITY_RESIZE - 2
G_PRIORITY_DEFAULT_IDLE + 10
G_PRIORITY_HIGH_IDLE + 30
GTK_TEXT_VIEW_PRIORITY_VALIDATE - 1

Review of attachment 216945 [details] [review]:

::: glib/gmain.c
@@ +863,3 @@
+    context->source_lists = g_list_append (NULL, source_list);
+  else
+    last = g_list_append (last, source_list);

If you make sure source_lists is never empty, eg by never removing the G_PRIORITY_DEFAULT list, then you could just move this into the loop with if (iter->next == NULL) { ... }

@@ +1805,3 @@
+	    break;
+	  source = source->next;
+	}

You could break this iterate-over-all-sources as a helper and reuse it for all the find_source_by... functions

@@ +2679,3 @@
+	  source_list = iter->data;
+	  if (source_list->priority == source->priority)
+	    break;

I assume there is no early exit for source_list->priority > source->priority here because this function is only ever called with sources that are in one of the lists ?

@@ +2699,3 @@
 		   GSource      *source)
 {
+  GSource *new_source = next_source_no_ref (context, source);

There is some extra effort here if you have sources of many different priorities, because you are repeatedly iterating the source_lists in next_source_no_ref.
Probably not worth worrying about.

One thing that's missing here is tests that show the performance impact of this change.

(In reply to comment #21)
> I assume there is no early exit for source_list->priority > source->priority
> here because this function is only ever called with sources that are in one of
> the lists ?

Hm... I guess this code doesn't deal with the case where the source is the only source at its priority level, and it gets removed from the list while the list is being walked.

Created attachment 217117 [details] [review]
an attempt at performance tests

I tried to come up with some measurements that would show the benefits of this patch, but my attempts so far were not very conclusive (see patch).

(In reply to comment #21)
> If you make sure source_lists is never empty, eg by never removing the
> G_PRIORITY_DEFAULT list, then you could just move this into the loop with if
> (iter->next == NULL) { ... }

It turns out that just moves the special-casing around, since now
the iterating code has to deal with the possibility of a
GSourceList that doesn't contain any sources. So I kept it as-is.

> You could break this iterate-over-all-sources as a helper and reuse it for all
> the find_source_by... functions

> There is some extra effort here if you have sources of many different
> priorities, because you are repeatedly iterating the source_lists in
> next_source_no_ref.
> Probably not worth worrying about.

I addressed both of these points by adding iterator functions
that use a GSourceIter struct to keep track of the current
position so they don't have to keep re-walking
source_lists. (This also addresses the "source gets destroyed
while we're walking the list" problem mentioned above, because
GSourceIter keeps the current source reffed, which will keep it
from being removed from its GSourceList.)

(In reply to comment #22)
> One thing that's missing here is tests that show the performance impact of this
> change.

I added a small test program to the toplevel tests/ dir (since
that's where all the other performancey tests are). Results (with
-O0):

original code:
Add same-priority sources: 16175
Remove in random order: 8
Add different-priority sources: 11762
Remove in random order: 10
Add sources from threads: 260175
Remove sources from threads: 285

new code:
Add same-priority sources: 21
Remove in random order: 9
Add different-priority sources: 24
Remove in random order: 11
Add sources from threads: 944
Remove sources from threads: 983

(The code also contains a test of doing
g_main_context_find_source_by_id() on each source, but that's
O(n) either way. I just wanted to make sure that the new
GSourceIter stuff didn't slow things down too much, and it
doesn't, and so that test is #ifdeffed out in this patch, to keep
the test from being too slow.)

I'm not sure why the "Remove sources from threads" test is faster
with the old code than the new...

(In reply to comment #24)
> I tried to come up with some measurements that would show the benefits of this
> patch, but my attempts so far were not very conclusive (see patch).

It's adding sources that gets slow, not running them.

Created attachment 217119 [details] [review]
gmain: rename some variables for clarity

Created attachment 217120 [details] [review]
gmain: add GSourceIter

add an explicit iterator for GMainContext sources

Created attachment 217121 [details] [review]
GMainContext: reorganize source list to avoid O(n) behavior

Rather than having a single priority-ordered list of GSources, store a
list of queues of each priority level. This means that adding a source
is now O(n) in the number of unique priority levels currently being
used, rather than O(n) in the total number of sources.

Created attachment 217122 [details] [review]
tests: add a test to make sure adding lots of GSources is fast

Review of attachment 217119 [details] [review]:

ok

Review of attachment 217120 [details] [review]:

Looks good

(In reply to comment #25)
 
> It's adding sources that gets slow, not running them.

Yeah, I was trying to measure that by the side effect of making the running slower.
Your test looks much more to the point.

It all looks great to me now. I would mark the whole series as acn, but unfortunately, make check fails with:

(/home/mclasen/Sources/glib/glib/tests/.libs/lt-protocol:15260): GLib-WARNING **: gmain.c:1793: ref_count == 0, but source was still attached to a context!

and

/maincontext/basic: 
(/home/mclasen/Sources/glib/glib/tests/.libs/lt-mainloop:15670): GLib-WARNING **: gmain.c:1793: ref_count == 0, but source was still attached to a context!
Trace/breakpoint trap (core dumped)

Looks like the problem is that g_source_iter_clear should only unref if may_modify is true. With

static void
g_source_iter_clear (GSourceIter *iter)
{
  if (iter->source && iter->may_modify)
    SOURCE_UNREF (iter->source, iter->context);
  iter->source = NULL;
}

make check succeeds.

A few more cosmetic things: 

- would be good to move the testcase to the beginning of the patch series

- please avoid tabs in the newly added code

Review of attachment 217122 [details] [review]:

Please add a license header and move this to the beginning of the patch series

turns out some gio tests are flaky with these patches, too.
I see memory corruption and crashes from gdbus-connection-flush

(In reply to comment #34)
> Looks like the problem is that g_source_iter_clear should only unref if
> may_modify is true.

ah, oops. "may_modify" was a late addition to the patches and I probably didn't do a full "make check" afterwards. (I was trying to speed up g_main_context_find_source_by_id() a bit. Although now that I think about it, the refs/unrefs aren't atomic ops, so that shouldn't have really had any effect, so maybe the speed improvement was from something else...)

(In reply to comment #36)
> turns out some gio tests are flaky with these patches, too.
> I see memory corruption and crashes from gdbus-connection-flush

ok, I'll look...

Review of attachment 217121 [details] [review]:

Since we got the test corruption tracked down to a different patch, this one looks clean and good to go. We should hold off until after todays release, though

Review of attachment 217121 [details] [review]:

release done

Pushed with suggested changes

Nice work guys! GLib is now webscale ;-)

Thank you so much!