This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
hashtab.c: minor optimization [resend]
- To: gcc-patches at gcc dot gnu dot org
- Subject: hashtab.c: minor optimization [resend]
- From: Zack Weinberg <zack at wolery dot cumb dot org>
- Date: Tue, 28 Mar 2000 13:53:34 -0800
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;
}
}