Tiny, tiny speedup for g_hash_table

[Michael Slade <mslade cit nepean uws edu au>]

The patch attached effectively eliminates the need for g_hash_freeze(). 
Each table update requires two compares, instead of the one check for
table->frozen.:)

cons:
-	One extra int in the GHashTable structure
-	g_hash_freeze() gets terminated with extreme prejudice :)

I did a quick profile with "time" - I increased the hash table size to
1000000 in tests/hash-test.c, ran it 20 times and summed up the
results.  According to the numbers there was a 1% speed improvement.
Maybe I should use a better profiling method...

Yes, this is pretty trivial, but I'm obsessed with speed. :)

The patch also tweaks tests/hash-test.c to add an ARRAYSIZE define.

Mick.
Index: ghash.c
===================================================================
RCS file: /cvs/gnome/glib/ghash.c,v
retrieving revision 1.14
diff -U3 -r1.14 ghash.c
--- ghash.c	1999/01/24 06:18:42	1.14
+++ ghash.c	1999/01/31 06:59:40
@@ -27,7 +27,6 @@
 #define HASH_TABLE_MIN_SIZE 11
 #define HASH_TABLE_MAX_SIZE 13845163
 
-
 typedef struct _GHashNode      GHashNode;
 
 struct _GHashNode
@@ -40,8 +39,8 @@
 struct _GHashTable
 {
   gint size;
+  gint minsize, maxsize; /* boundaries that size stays in before resizing */
   gint nnodes;
-  guint frozen;
   GHashNode **nodes;
   GHashFunc hash_func;
   GCompareFunc key_compare_func;
@@ -57,6 +56,10 @@
 static void		g_hash_nodes_destroy	 (GHashNode	*hash_node);
 
 
+#define HASH_TABLE_CHECK_RESIZE(table) \
+  if((table->nnodes<table->minsize) || (table->nnodes>table->maxsize)) \
+    g_hash_table_resize(table);
+
 G_LOCK_DECLARE_STATIC (g_hash_global);
 
 static GMemChunk *node_mem_chunk = NULL;
@@ -73,10 +76,11 @@
   hash_table = g_new (GHashTable, 1);
   hash_table->size = HASH_TABLE_MIN_SIZE;
   hash_table->nnodes = 0;
-  hash_table->frozen = FALSE;
   hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
   hash_table->key_compare_func = key_compare_func;
   hash_table->nodes = g_new (GHashNode*, hash_table->size);
+  hash_table->minsize=-1;
+  hash_table->maxsize=hash_table->size*3;
   
   for (i = 0; i < hash_table->size; i++)
     hash_table->nodes[i] = NULL;
@@ -160,8 +164,7 @@
     {
       *node = g_hash_node_new (key, value);
       hash_table->nnodes++;
-      if (!hash_table->frozen)
-	g_hash_table_resize (hash_table);
+      HASH_TABLE_CHECK_RESIZE(hash_table);
     }
 }
 
@@ -182,8 +185,7 @@
       g_hash_node_destroy (dest);
       hash_table->nnodes--;
   
-      if (!hash_table->frozen)
-        g_hash_table_resize (hash_table);
+      HASH_TABLE_CHECK_RESIZE(hash_table);
     }
 }
 
@@ -214,19 +216,11 @@
 void
 g_hash_table_freeze (GHashTable *hash_table)
 {
-  g_return_if_fail (hash_table != NULL);
-  
-  hash_table->frozen++;
 }
 
 void
 g_hash_table_thaw (GHashTable *hash_table)
 {
-  g_return_if_fail (hash_table != NULL);
-  
-  if (hash_table->frozen)
-    if (!(--hash_table->frozen))
-      g_hash_table_resize (hash_table);
 }
 
 gint
@@ -271,8 +265,7 @@
 	}
     }
   
-  if (!hash_table->frozen)
-    g_hash_table_resize (hash_table);
+    HASH_TABLE_CHECK_RESIZE(hash_table);
   
   return deleted;
 }
@@ -308,17 +301,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);
@@ -338,6 +324,13 @@
   g_free (hash_table->nodes);
   hash_table->nodes = new_nodes;
   hash_table->size = new_size;
+
+  hash_table->minsize=hash_table->size/3;
+  if(hash_table->minsize<HASH_TABLE_MIN_SIZE)
+    hash_table->minsize = -1;
+  hash_table->maxsize=hash_table->size*3;
+  if(hash_table->maxsize>HASH_TABLE_MAX_SIZE)
+    hash_table->maxsize = G_MAXINT;
 }
 
 static GHashNode*
Index: tests/hash-test.c
===================================================================
RCS file: /cvs/gnome/glib/tests/hash-test.c,v
retrieving revision 1.4
diff -U3 -r1.4 hash-test.c
--- tests/hash-test.c	1999/01/24 06:18:43	1.4
+++ tests/hash-test.c	1999/01/31 06:59:41
@@ -31,12 +31,12 @@
 
 #include <glib.h>
 
+#define ARRAYSIZE 10000
 
+int array[ARRAYSIZE];
 
-int array[10000];
 
 
-
 static gboolean
 my_hash_callback_remove (gpointer key,
 			 gpointer value,
@@ -329,28 +329,28 @@
   gint i;
 
   hash_table = g_hash_table_new (my_hash, my_hash_compare);
-  for (i = 0; i < 10000; i++)
+  for (i = 0; i < ARRAYSIZE; i++)
     {
       array[i] = i;
       g_hash_table_insert (hash_table, &array[i], &array[i]);
     }
   g_hash_table_foreach (hash_table, my_hash_callback, NULL);
 
-  for (i = 0; i < 10000; i++)
+  for (i = 0; i < ARRAYSIZE; i++)
     if (array[i] == 0)
       g_assert_not_reached();
 
-  for (i = 0; i < 10000; i++)
+  for (i = 0; i < ARRAYSIZE; i++)
     g_hash_table_remove (hash_table, &array[i]);
 
-  for (i = 0; i < 10000; i++)
+  for (i = 0; i < ARRAYSIZE; i++)
     {
       array[i] = i;
       g_hash_table_insert (hash_table, &array[i], &array[i]);
     }
 
-  if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 ||
-      g_hash_table_size (hash_table) != 5000)
+  if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != (ARRAYSIZE-1)/2 ||
+      g_hash_table_size (hash_table) != (ARRAYSIZE+1)/2)
     g_assert_not_reached();
 
   g_hash_table_foreach (hash_table, my_hash_callback_remove_test, NULL);