Speeding up g_param_spec_pool_lookup()

[Soeren Sandmann <sandmann daimi au dk>]

On some profiles, eg. opaque resizing of Gnumeric,
gtk_widget_style_get() shows up fairly high with most of the time spent
in g_param_spec_pool_lookup().

The way g_param_spec_pool_lookup() works currently is

	- There is a hash table that maps from (type, name) tuples to
          ParamSpecs.

	- A lookup with walk_parents==TRUE means do a hash table lookup
          for each parent type until a match is found.

	- The name in the (type, name) tuple is stored in its
	  canonicalized form, ie. with dashes between words. Eg.
          "shadow-type".

When a style property is looked up by its underscored name, and it
happens to be defined in a proper supertype, this is what will
happen: 

	- For each parent type, the underscored name will be looked up.
	  This will fail, because the hash table contains dashed names

	- A copy will be made of the name. This copy will be
          canonicalized.

	- For each parent type up until the right type is found, the 
          canonicalized name will be looked up in the hash table.

So quite often, several hash table lookups, a string copy and a
canonicalization is needed to do a single lookup of a style property.

The patch I'm attaching works by observing:

	- Using the same name for more than one type is fairly rare.

	- When you lookup by name you always use either 
          name_on_this_form or name-on-this-form. Other forms are
          basically unused.

Instead of hashing from (type, name) to ParamSpecs, the patch hashes
from names to lists of ParamSpecs. To make sure both 
names_with_underscores and names-with-dashes are found quickly, the hash
table maps both forms of the name to the same list of ParamSpecs.

This means that in the common case where the name is unique, the hash
table lookup will succeed immediately and the list will only contain a
single entry. If the type for this entry is a supertype of the looked up
type, this entry can be returned immediately.

In the rarer cases where the is more than one ParamSpec with the same
name, the list is searched for the ParamSpec whose owner type is deepest
in the type hierarchy, but still a supertype of the looked-up type. The
data below shows that even in this case the list will generally not
contain more than five elements.

The patch also handles the case where the name is something_like-this
(or weirder), but that doesn't happen in practice.

Soeren 




Data:

These numbers were generated by starting the application and showing a
few dialogs,
then shutting the application down. 

Gnumeric:

	    428 names used in 1 different types
	     72 names used in 2 different types
	     22 names used in 3 different types
	      6 names used in 4 different types
	      1 names used in 5 different types

The Gimp:

	   1064 names used in 1 different types
	     97 names used in 2 different types
	     27 names used in 3 different types
	      7 names used in 4 different types
	      1 names used in 5 different types

Nautilus:
	
	    316 names used in 1 different types
	     35 names used in 2 different types
	      9 names used in 3 different types
	      1 names used in 4 different types
	

Index: gparam.c
===================================================================
RCS file: /cvs/gnome/glib/gobject/gparam.c,v
retrieving revision 1.27
diff -u -p -u -r1.27 gparam.c
--- gparam.c	7 Feb 2003 22:04:24 -0000	1.27
+++ gparam.c	9 Jul 2003 14:06:59 -0000
@@ -27,8 +27,6 @@
 #include	"gvaluecollector.h"
 #include	<string.h>
 
-
-
 /* --- defines --- */
 #define	G_PARAM_USER_MASK			(~0 << G_PARAM_USER_SHIFT)
 #define PSPEC_APPLIES_TO_VALUE(pspec, value)	(G_TYPE_CHECK_VALUE_TYPE ((value), G_PARAM_SPEC_VALUE_TYPE (pspec)))
@@ -548,41 +546,82 @@ struct _GParamSpecPool
   GHashTable  *hash_table;
 };
 
-static guint
-param_spec_pool_hash (gconstpointer key_spec)
+GParamSpecPool*
+g_param_spec_pool_new (gboolean type_prefixing)
 {
-  const GParamSpec *key = key_spec;
-  const gchar *p;
-  guint h = key->owner_type;
+  static GStaticMutex init_smutex = G_STATIC_MUTEX_INIT;
+  GParamSpecPool *pool = g_new (GParamSpecPool, 1);
+
+  memcpy (&pool->smutex, &init_smutex, sizeof (init_smutex));
+  pool->type_prefixing = type_prefixing != FALSE;
+  pool->hash_table = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
+  
+  return pool;
+}
 
-  for (p = key->name; *p; p++)
-    h = (h << 5) - h + *p;
+static GSList *
+do_canonicalized_lookup (GHashTable  *ht,
+			 const gchar *name)
+{
+  GSList *result;
+  gchar *canonicalized = g_strdup (name);
+  
+  canonicalize_key (canonicalized);
+  result = g_hash_table_lookup (ht, canonicalized);
+  g_free (canonicalized);
 
-  return h;
+  return result;
 }
 
-static gboolean
-param_spec_pool_equals (gconstpointer key_spec_1,
-			gconstpointer key_spec_2)
+static inline GSList *
+do_lookup (GHashTable  *ht,
+	   const gchar *name)
 {
-  const GParamSpec *key1 = key_spec_1;
-  const GParamSpec *key2 = key_spec_2;
+  GSList *result;
 
-  return (key1->owner_type == key2->owner_type &&
-	  strcmp (key1->name, key2->name) == 0);
+  if (G_LIKELY ((result = g_hash_table_lookup (ht, name))))
+    return result;
+  else
+    return do_canonicalized_lookup (ht, name);
 }
 
-GParamSpecPool*
-g_param_spec_pool_new (gboolean type_prefixing)
+static gchar *
+dashes_to_underscores (const gchar *name)
 {
-  static GStaticMutex init_smutex = G_STATIC_MUTEX_INIT;
-  GParamSpecPool *pool = g_new (GParamSpecPool, 1);
+  gint i;
+  gchar *result = g_strdup (name);
 
-  memcpy (&pool->smutex, &init_smutex, sizeof (init_smutex));
-  pool->type_prefixing = type_prefixing != FALSE;
-  pool->hash_table = g_hash_table_new (param_spec_pool_hash, param_spec_pool_equals);
+  for (i = 0; name[i] != '\0'; i++)
+    if (name[i] == '-')
+      result[i] = '_';
 
-  return pool;
+  return result;
+}
+
+static void
+do_insert (GHashTable *ht, const gchar *name, GSList *pspecs)
+{
+  gchar *name_with_dashes = g_strdup (name);
+  gchar *name_with_underscores;
+
+  canonicalize_key (name_with_dashes);
+  if (strchr (name_with_dashes, '-'))
+    name_with_underscores = dashes_to_underscores (name_with_dashes);
+  else
+    name_with_underscores = NULL;
+
+  if (pspecs)
+    {
+      g_hash_table_replace (ht, name_with_dashes, pspecs);
+      if (name_with_underscores)
+	g_hash_table_replace (ht, name_with_underscores, pspecs);
+    }
+  else
+    {
+      g_hash_table_remove (ht, name_with_dashes);
+      if (name_with_underscores)
+	g_hash_table_remove (ht, name_with_underscores);
+    }
 }
 
 void
@@ -591,10 +630,14 @@ g_param_spec_pool_insert (GParamSpecPool
 			  GType           owner_type)
 {
   gchar *p;
-  
+  GSList *list;
+
   if (pool && pspec && owner_type > 0 && pspec->owner_type == 0)
     {
+      GSList *pspecs;
+      
       G_SLOCK (&pool->smutex);
+
       for (p = pspec->name; *p; p++)
 	{
 	  if (!strchr (G_CSET_A_2_Z G_CSET_a_2_z G_CSET_DIGITS "-_", *p))
@@ -604,10 +647,22 @@ g_param_spec_pool_insert (GParamSpecPool
 	      return;
 	    }
 	}
-      
+      pspecs = do_lookup (pool->hash_table, pspec->name);
+      for (list = pspecs; list != NULL; list = list->next)
+	{
+	  GParamSpec *ps = list->data;
+	  
+	  if (ps->owner_type == owner_type)
+	    {
+	      g_warning (G_STRLOC ": inserting the same pspec (%s) twice", pspec->name);
+	      return;
+	    }
+	}
       pspec->owner_type = owner_type;
       g_param_spec_ref (pspec);
-      g_hash_table_insert (pool->hash_table, pspec, pspec);
+      pspecs = g_slist_prepend (pspecs, pspec);
+      do_insert (pool->hash_table, pspec->name, pspecs);
+      
       G_SUNLOCK (&pool->smutex);
     }
   else
@@ -625,11 +680,27 @@ g_param_spec_pool_remove (GParamSpecPool
 {
   if (pool && pspec)
     {
+      GSList *pspecs, *list;
+
       G_SLOCK (&pool->smutex);
-      if (g_hash_table_remove (pool->hash_table, pspec))
-	g_param_spec_unref (pspec);
-      else
+      pspecs = do_lookup (pool->hash_table, pspec->name);
+      for (list = pspecs; list; list = list->next)
+	{
+	  GParamSpec *ps = list->data;
+	  
+	  if (ps->owner_type == pspec->owner_type)
+	    {
+	      g_param_spec_unref (ps);
+	      pspecs = g_slist_delete_link (pspecs, list);
+	      break;
+	    }
+	}
+
+      if (!list)
 	g_warning (G_STRLOC ": attempt to remove unknown pspec `%s' from pool", pspec->name);
+
+      do_insert (pool->hash_table, ((GParamSpec *)pspecs->data)->name, pspecs);
+
       G_SUNLOCK (&pool->smutex);
     }
   else
@@ -639,63 +710,15 @@ g_param_spec_pool_remove (GParamSpecPool
     }
 }
 
-static inline GParamSpec*
-param_spec_ht_lookup (GHashTable  *hash_table,
-		      const gchar *param_name,
-		      GType        owner_type,
-		      gboolean     walk_ancestors)
-{
-  GParamSpec key, *pspec;
-
-  key.owner_type = owner_type;
-  key.name = (gchar*) param_name;
-  if (walk_ancestors)
-    do
-      {
-	pspec = g_hash_table_lookup (hash_table, &key);
-	if (pspec)
-	  return pspec;
-	key.owner_type = g_type_parent (key.owner_type);
-      }
-    while (key.owner_type);
-  else
-    pspec = g_hash_table_lookup (hash_table, &key);
-
-  if (!pspec)
-    {
-      /* try canonicalized form */
-      key.name = g_strdup (param_name);
-      key.owner_type = owner_type;
-      
-      canonicalize_key (key.name);
-      if (walk_ancestors)
-	do
-	  {
-	    pspec = g_hash_table_lookup (hash_table, &key);
-	    if (pspec)
-	      {
-		g_free (key.name);
-		return pspec;
-	      }
-	    key.owner_type = g_type_parent (key.owner_type);
-	  }
-	while (key.owner_type);
-      else
-	pspec = g_hash_table_lookup (hash_table, &key);
-      g_free (key.name);
-    }
-
-  return pspec;
-}
-
 GParamSpec*
 g_param_spec_pool_lookup (GParamSpecPool *pool,
 			  const gchar    *param_name,
 			  GType           owner_type,
 			  gboolean        walk_ancestors)
 {
-  GParamSpec *pspec;
   gchar *delim;
+  GSList *pspecs = NULL;
+  GSList *list;
 
   if (!pool || !param_name)
     {
@@ -704,25 +727,16 @@ g_param_spec_pool_lookup (GParamSpecPool
     }
 
   G_SLOCK (&pool->smutex);
-
   delim = pool->type_prefixing ? strchr (param_name, ':') : NULL;
-
-  /* try quick and away, i.e. without prefix */
   if (!delim)
     {
-      pspec = param_spec_ht_lookup (pool->hash_table, param_name, owner_type, walk_ancestors);
-      G_SUNLOCK (&pool->smutex);
-
-      return pspec;
+      pspecs = do_lookup (pool->hash_table, param_name);
     }
-
-  /* strip type prefix */
-  if (pool->type_prefixing && delim[1] == ':')
+  else if (pool->type_prefixing && delim[1] == ':')
     {
       guint l = delim - param_name;
       gchar stack_buffer[32], *buffer = l < 32 ? stack_buffer : g_new (gchar, l + 1);
       GType type;
-      
       strncpy (buffer, param_name, delim - param_name);
       buffer[l] = 0;
       type = g_type_from_name (buffer);
@@ -738,17 +752,38 @@ g_param_spec_pool_lookup (GParamSpecPool
 	      return NULL;
 	    }
 	  owner_type = type;
-	  param_name += l + 2;
-	  pspec = param_spec_ht_lookup (pool->hash_table, param_name, owner_type, walk_ancestors);
-	  G_SUNLOCK (&pool->smutex);
+	}
+      pspecs = do_lookup (pool->hash_table, delim + 2);
+    }
 
-	  return pspec;
+  if (walk_ancestors)
+    {
+      GParamSpec *pspec = NULL;
+      for (list = pspecs; list != NULL; list = list->next)
+	{
+	  GParamSpec *ps = list->data;
+	  
+	  if (g_type_is_a (owner_type, ps->owner_type))
+	    {
+	      if (!pspec || g_type_depth (ps->owner_type) > g_type_depth (pspec->owner_type))
+		pspec = ps;
+	    }
+	}
+      G_SUNLOCK (&pool->smutex);
+      return pspec;
+    }
+  
+  for (list = pspecs; list != NULL; list = list->next)
+    {
+      GParamSpec *ps = list->data;
+      if (ps->owner_type == owner_type)
+	{
+	  G_SUNLOCK (&pool->smutex);
+	  return ps;
 	}
     }
-  /* malformed param_name */
 
   G_SUNLOCK (&pool->smutex);
-
   return NULL;
 }
 
@@ -757,12 +792,21 @@ pool_list (gpointer key,
 	   gpointer value,
 	   gpointer user_data)
 {
-  GParamSpec *pspec = value;
   gpointer *data = user_data;
   GType owner_type = (GType) data[1];
+  GSList *pspecs = value, *list;
 
-  if (owner_type == pspec->owner_type)
-    data[0] = g_list_prepend (data[0], pspec);
+  /* only look at keys in canonical form, ie., "name-on-this-form" */
+  if (strchr (key, '_'))
+    return;
+  
+  for (list = pspecs; list != NULL; list = list->next)
+    {
+      GParamSpec *pspec = list->data;
+
+      if (owner_type == pspec->owner_type)
+	data[0] = g_list_prepend (data[0], pspec);
+    }
 }
 
 GList*
@@ -784,56 +828,47 @@ g_param_spec_pool_list_owned (GParamSpec
 }
 
 static gint
-pspec_compare_id (gconstpointer a,
-		  gconstpointer b)
+pspec_compare (gconstpointer a,
+	       gconstpointer b)
 {
   const GParamSpec *pspec1 = a, *pspec2 = b;
+  guint d1 = g_type_depth (pspec1->owner_type);
+  guint d2 = g_type_depth (pspec2->owner_type);
 
-  return pspec1->param_id < pspec2->param_id ? -1 : pspec1->param_id > pspec2->param_id;
-}
-
-static inline GSList*
-pspec_list_remove_overridden (GSList     *plist,
-			      GHashTable *ht,
-			      GType       owner_type,
-			      guint      *n_p)
-{
-  GSList *rlist = NULL;
-
-  while (plist)
-    {
-      GSList *tmp = plist->next;
-      GParamSpec *pspec = plist->data;
-
-      if (param_spec_ht_lookup (ht, pspec->name, owner_type, TRUE) != pspec)
-	g_slist_free_1 (plist);
-      else
-	{
-	  plist->next = rlist;
-	  rlist = plist;
-	  *n_p += 1;
-	}
-      plist = tmp;
-    }
-  return rlist;
+  if (d1 < d2)
+    return -1;
+  else if (d2 > d1)
+    return 1;
+  else 
+    return pspec1->param_id < pspec2->param_id ? -1 : pspec1->param_id > pspec2->param_id;
 }
 
 static void
-pool_depth_list (gpointer key,
-		 gpointer value,
-		 gpointer user_data)
+list_non_overridden (gpointer key,
+		     gpointer value,
+		     gpointer user_data)
 {
-  GParamSpec *pspec = value;
+  GSList *pspecs = value, *list;
   gpointer *data = user_data;
-  GSList **slists = data[0];
-  GType owner_type = (GType) data[1];
+  GType owner_type = (GType)data[1];
+  GParamSpec *best_pspec = NULL;
 
-  if (g_type_is_a (owner_type, pspec->owner_type))
+  /* only look at keys in canonical form, ie., "name-on-this-form" */
+  if (strchr (key, '_'))
+    return;
+  
+  for (list = pspecs; list != NULL; list = list->next)
     {
-      guint d = g_type_depth (pspec->owner_type);
-
-      slists[d - 1] = g_slist_prepend (slists[d - 1], pspec);
+      GParamSpec *pspec = list->data;
+      if (g_type_is_a (owner_type, pspec->owner_type))
+	{
+	  if (!best_pspec ||
+	      g_type_depth (pspec->owner_type) > g_type_depth (best_pspec->owner_type))
+	    best_pspec = pspec;
+	}
     }
+  if (best_pspec)
+    data[0] = g_slist_prepend (data[0], best_pspec);
 }
 
 GParamSpec** /* free result */
@@ -841,38 +876,27 @@ g_param_spec_pool_list (GParamSpecPool *
 			GType           owner_type,
 			guint          *n_pspecs_p)
 {
-  GParamSpec **pspecs, **p;
-  GSList **slists, *node;
+  GParamSpec **pspecs;
   gpointer data[2];
-  guint d, i;
+  guint n_pspecs;
+  guint i;
+  GSList *list;
 
-  g_return_val_if_fail (pool != NULL, NULL);
-  g_return_val_if_fail (owner_type > 0, NULL);
-  g_return_val_if_fail (n_pspecs_p != NULL, NULL);
-  
   G_SLOCK (&pool->smutex);
-  *n_pspecs_p = 0;
-  d = g_type_depth (owner_type);
-  slists = g_new0 (GSList*, d);
-  data[0] = slists;
-  data[1] = (gpointer) owner_type;
-  g_hash_table_foreach (pool->hash_table, pool_depth_list, &data);
-  for (i = 0; i < d - 1; i++)
-    slists[i] = pspec_list_remove_overridden (slists[i], pool->hash_table, owner_type, n_pspecs_p);
-  *n_pspecs_p += g_slist_length (slists[i]);
-  pspecs = g_new (GParamSpec*, *n_pspecs_p + 1);
-  p = pspecs;
-  for (i = 0; i < d; i++)
-    {
-      slists[i] = g_slist_sort (slists[i], pspec_compare_id);
-      for (node = slists[i]; node; node = node->next)
-	*p++ = node->data;
-      g_slist_free (slists[i]);
-    }
-  *p++ = NULL;
-  g_free (slists);
+  data[0] = NULL;
+  data[1] = (gpointer)owner_type;
+  g_hash_table_foreach (pool->hash_table, list_non_overridden, &data);
+  n_pspecs = g_slist_length (data[0]);
+  pspecs = g_new (GParamSpec*, n_pspecs + 1);
+  i = 0;
+  data[0] = g_slist_sort (data[0], pspec_compare);
+  for (list = data[0]; list != NULL; list = list->next)
+    pspecs[i++] = list->data;
+  pspecs[i] = NULL;
+  if (n_pspecs_p)
+    *n_pspecs_p = n_pspecs;
+  g_slist_free (data[0]);
   G_SUNLOCK (&pool->smutex);
-
   return pspecs;
 }