This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Small performance improvement to ht_expand
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 22 Aug 2003 14:26:08 -0600 (MDT)
- Subject: [PATCH] Small performance improvement to ht_expand
The following patch optimizes ht_expand to avoid calculating hash2 when
the first probe hits an empty hash table slot. This is an almost
identical tweak to the one I recently made to ht_lookup, which I recently
discovered was one of GCC's top-ten functions by run-time profiling.
Though only called 327 times during a bootstrap, ht_expand can benefit
from the same improvement: We can guarantee during ht_expand that we
will probe atleast 12280 times, and each probe ideally has atleast a
62.5% chance of hitting an unused slot.
The following patch has been tested on i686-pc-linux-gnu with a full
"make bootstrap", all languages except treelang, and regression tested
with a top-level "make -k check" with no new failures.
Ok for mainline?
2003-08-22 Roger Sayle <roger@eyesopen.com>
* hashtable.c (ht_expand): Avoid calculating rehash for the common
case that the first probe hits an empty hash table slot.
Index: hashtable.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/hashtable.c,v
retrieving revision 1.15
diff -c -3 -p -r1.15 hashtable.c
*** hashtable.c 11 Aug 2003 21:47:36 -0000 1.15
--- hashtable.c 22 Aug 2003 13:43:50 -0000
*************** ht_expand (hash_table *table)
*** 184,202 ****
unsigned int index, hash, hash2;
hash = (*p)->hash_value;
- hash2 = ((hash * 17) & sizemask) | 1;
index = hash & sizemask;
! for (;;)
{
! if (! nentries[index])
{
! nentries[index] = *p;
! break;
}
!
! index = (index + hash2) & sizemask;
}
}
while (++p < limit);
--- 184,201 ----
unsigned int index, hash, hash2;
hash = (*p)->hash_value;
index = hash & sizemask;
! if (nentries[index])
{
! hash2 = ((hash * 17) & sizemask) | 1;
! do
{
! index = (index + hash2) & sizemask;
}
! while (nentries[index]);
}
+ nentries[index] = *p;
}
while (++p < limit);
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833