g_hash_table_resize (#59026)

[Owen Taylor <otaylor redhat com>]

Bug #59026 points out that we do floating point arithmetic
to decide whether to resize a hash table while inserting
and removing keys. While I'm not sure the task switching
overhead is a big concern, people do use GLib on machines
and the floating point certainly seems a bit extraneous.

The following patch fixes that, and also refactors things
a bit to try to reduce function call overhead in the
common case.

In rough testing using the following benchmark:

====
  GHashTable *ht = g_hash_table_new (g_direct_hash, NULL);
  int i, j;

  for (i=0; i < 1000; i++)
    {
      for (j = 0; j < 1000; j++)
        g_hash_table_insert (ht, GUINT_TO_POINTER(j), GUINT_TO_POINTER(j));
      for (j = 0; j < 1000; j++)
        g_hash_table_remove (ht, GUINT_TO_POINTER(j));
    }
=====

The removal of the floating point seemed to give about a 25%
improvement (on a Celeron) and the refactoring about 10%.
I was suprised by the size of the difference for the
removal of the floating point ops, in this test.

Regards,
                                        Owen

Index: glib/ghash.c
===================================================================
RCS file: /cvs/gnome/glib/glib/ghash.c,v
retrieving revision 1.26
diff -u -r1.26 ghash.c
--- glib/ghash.c	2001/05/04 17:01:53	1.26
+++ glib/ghash.c	2001/08/19 05:00:32
@@ -59,6 +59,23 @@
   GDestroyNotify   value_destroy_func;
 };
 
+#define G_HASH_TABLE_RESIZE(hash_table)				\
+   G_STMT_START {						\
+     if (hash_table->nnodes < hash_table->size)			\
+       {							\
+	 if (hash_table->size < 3 * hash_table->nnodes ||	\
+	     hash_table->size <= HASH_TABLE_MIN_SIZE)		\
+	   goto __ok;						\
+       }							\
+     else							\
+       {							\
+	 if (3 * hash_table->size > hash_table->nnodes ||	\
+	     hash_table->size >= HASH_TABLE_MAX_SIZE)		\
+	   goto __ok;						\
+       }							\
+     g_hash_table_resize (hash_table);				\
+     __ok:							\
+   } G_STMT_END
 
 static void		g_hash_table_resize	  (GHashTable	  *hash_table);
 static GHashNode**	g_hash_table_lookup_node  (GHashTable     *hash_table,
@@ -304,7 +321,7 @@
     {
       *node = g_hash_node_new (key, value);
       hash_table->nnodes++;
-      g_hash_table_resize (hash_table);
+      G_HASH_TABLE_RESIZE (hash_table);
     }
 }
 
@@ -347,7 +364,7 @@
     {
       *node = g_hash_node_new (key, value);
       hash_table->nnodes++;
-      g_hash_table_resize (hash_table);
+      G_HASH_TABLE_RESIZE (hash_table);
     }
 }
 
@@ -383,7 +400,7 @@
 			   hash_table->value_destroy_func);
       hash_table->nnodes--;
   
-      g_hash_table_resize (hash_table);
+      G_HASH_TABLE_RESIZE (hash_table);
 
       return TRUE;
     }
@@ -417,7 +434,7 @@
       g_hash_node_destroy (dest, NULL, NULL);
       hash_table->nnodes--;
   
-      g_hash_table_resize (hash_table);
+      G_HASH_TABLE_RESIZE (hash_table);
 
       return TRUE;
     }
@@ -517,7 +534,7 @@
 	}
     }
   
-  g_hash_table_resize (hash_table);
+  G_HASH_TABLE_RESIZE (hash_table);
   
   return deleted;
 }
@@ -570,17 +587,10 @@
   GHashNode **new_nodes;
   GHashNode *node;
   GHashNode *next;
-  gfloat nodes_per_list;
   guint hash_val;
   gint new_size;
   gint i;
-  
-  nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
-  
-  if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
-      (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
-    return;
-  
+
   new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes),
 		   HASH_TABLE_MIN_SIZE,
 		   HASH_TABLE_MAX_SIZE);