Massive speed improvement in GObject type checking code

[Erik Walthinsen <omega temple-baptist com>]

Parapraxis (author, paranormal.sourceforge.net) has converted his
visualization plugin over to GObject, and has been hanging out in
#gstreamer, since I'm just now wrapping up a conversion of GStreamer
itself to GObject (more on that in another mail), and he's porting his
plugin to GStreamer.

He did some profiling of his code, and found that 26% of the CPU time was
in g_type_instance_is_a().  Since that's a pretty complex function, I had
no idea how to optimize it.  But then I looked at the code that calls it,
the _G_TYPE_CIT macro, which is the core of G_TYPE_CHECK_INSTANCE_TYPE.
I turns out that a really obvious optimization was ignored:

#define _G_TYPE_CIT(ip, gt)  (g_type_instance_is_a ((GTypeInstance*) ip, gt))

The goal is to determine if the object instance *ip is of type gt.
g_type_instance_is_a() goes through a really long list of things to
determine if the object is really an interface, or a derived object, or
any of the other myriad of possibilities that make the type system
actually *useful*.

The optimization that was missed is that in many/most cases, the code will
be checking a object against its own type.  That means that the GType gt
will be equal to the 'immediate' type of the object, not a parent type, or
any of that.

The 'immediate' type of the object is accessible via the g_class pointer
that is the first 4 bytes of *every* instance of any type (GTypeInstance).
The g_class pointer goes to a structure that has the GType of that object.
Therefore we can simply compare the 'immediate' type of the object
directly against the type in question:

#define _G_TYPE_CIT(ip, gt) \
( (((GTypeInstance*)ip)->g_class->g_type == (gt)) ? TRUE : \
  g_type_instance_is_a ((GTypeInstance*)ip, gt))

That way the only time g_type_instance_is_a() is called is when the
comparison is between an object and its parent class, or some similar
case.  All other cases are two indirections and a compare.

Parapraxis found that this reduced the number of calls in his code from
10489576 to 1391, or a 99.987% reduction.  The total CPU time taken by
g_type_instance_is_a went from 26% to *not measurable*.  This won't be
quite as dramatic in something like a Gtk+ application, where more checks
will be done between an object and one of its parent classes, but I would
still expect *at least* a 50% reduction.

I'm convinced that similar optimizations could be made to several of the
other macros in this file, potentially reducing object type checking time
to almost nothing.

Parapraxis wondered if multithreading has any impact on this, and I
believe it does not.  The object is not capable of changing its type,
ever, afaik.  The GType being compared will almost always come from a
_get_type() function that also cannot ever change the GType value.  The
only reason for the READER_LOCK in g_type_instance_is_a() is to avoid
someone else mangling the GLists that are walked through to find the
TypeNode in question, afaict.

Anyway, if no one can find any other problems with this code, I would
like to see it make its way into glib CVS.  I have GNOME CVS write access,
so if whoever wants me to, I can commit it myself, after posting a full
unidiff on the list for confirmation that I'm doing it right.

      Erik Walthinsen <omega temple-baptist com> - System Administrator
        __
       /  \                GStreamer - The only way to stream!
      |    | M E G A        ***** http://gstreamer.net/ *****
      _\  /_