hashtab.c: minor optimization [resend]

Zack Weinberg zack@wolery.cumb.org
Tue Mar 28 13:53:00 GMT 2000


About half of my previous patch was superseded by Bernd's changes.
This just changes htab_find_with_hash so it doesn't calculate the
secondary hash unless it needs it, and tunes the loop a bit.  Good for
about 5%.

Also adds a static prototype for higher_prime_number.

zw

	* hashtab.c (htab_find_with_hash): Avoid calculating hash2
	unless it will be used.  Rearrange loop for better
	optimization.
	(higher_prime_number): Add static prototype.

===================================================================
Index: libiberty/hashtab.c
--- libiberty/hashtab.c	2000/03/14 18:28:45	1.8
+++ libiberty/hashtab.c	2000/03/28 21:50:28
@@ -55,8 +55,10 @@ Boston, MA 02111-1307, USA.  */
 
 #define DELETED_ENTRY  ((void *) 1)
 
+static unsigned long higher_prime_number PARAMS ((unsigned long));
+
 /* The following function returns the nearest prime number which is
-   greater than given source number. */
+   greater than a given source number. */
 
 static unsigned long
 higher_prime_number (n)
@@ -223,24 +225,30 @@ htab_find_with_hash (htab, element, hash
 {
   unsigned int index, hash2;
   size_t size;
+  void *entry;
 
   htab->searches++;
   size = htab->size;
-  hash2 = 1 + hash % (size - 2);
   index = hash % size;
 
+  entry = htab->entries[index];
+  if (entry == EMPTY_ENTRY
+      || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
+    return entry;
+
+  hash2 = 1 + hash % (size - 2);
+
   for (;;)
     {
-      void *entry = htab->entries[index];
-      if (entry == EMPTY_ENTRY)
-	return NULL;
-      else if (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))
-	return entry;
-
       htab->collisions++;
       index += hash2;
       if (index >= size)
 	index -= size;
+
+      entry = htab->entries[index];
+      if (entry == EMPTY_ENTRY
+	  || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
+	return entry;
     }
 }
 


More information about the Gcc-patches mailing list