Re: Massive speed improvement in GObject type checking code

[Tim Janik <timj gtk org>]

On Sat, 16 Jun 2001, Erik Walthinsen wrote:

> 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.

there's one problem with the above macro, that is, (ip) is evaluated
twice, if its anything else than a constant (say a function call, returning
an object), this macro implementation is potentially harmfull.

> 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*.

ok, that is quite alarming indeed.

>  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'd second that.

> 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.

feel free to post more suggestions liek this to gtk-devel-list gnome org 

> 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.

mostly right. though, using g_type_instance_is_a() has another advantage,
e.g. consider:

#define ID_NOT_IN_TYPE_SYSTEM	(255)
static guint  id = ID_NOT_IN_TYPE_SYSTEM;
static guint *id_p = &id;
{
  /*your version*/_G_TYPE_CIT (&ip_p, ID_NOT_IN_TYPE_SYSTEM); /* succeeds */
  g_type_instance_is_a (&ip_p, ID_NOT_IN_TYPE_SYSTEM); /* fails,
                                                   ID_NOT_IN_TYPE_SYSTEM is not
                                                   registered */
}

however, considering the speed advatage you report, it might be worth
lessening the guarantees that G_TYPE_CHECK_INSTANCE_TYPE() makes, so that,
for the supposedly pathological case that the instance is broken in that
its class contains a non-registered type-id, _and_ this non-registered
type id is being checked for, it returns a false TRUE.

we still need to get around the double evaluation of the (ip) arg of
_G_TYPE_CIT() though, so we'd have to implement it via an auxillary
static inline function.
the same kind of optimization can be implemented for the class
type-checking macro btw.

> 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

---
ciaoTJ