PATCH to hashtable.[ch]: Cache hash value

[Daniel Jacobowitz]

On Sat, Mar 15, 2003 at 06:59:39PM +0100, Gabriel Dos Reis wrote:
> Daniel Jacobowitz <drow@mvista.com> writes:
> 
> | On Sat, Mar 15, 2003 at 06:38:21PM +0100, Gabriel Dos Reis wrote:
> | > 
> | > Hi,
> | > 
> | >   This patch makes us cache the hash values we compute for identifiers
> | > in hashtable.c:calc_hash().
> | > 
> | > It is motivated by the work on reducing time spent in name-lookup.
> | > For that purpose I'm implementing associations of names to
> | > declarations as a hash table.  There is no reason we should be
> | > computing hash values for identifiers over and over.
> | > 
> | > As a side effect, this patch improves the existing hash table
> | > implementation in at least two ways (spotted by Neil in private mails):
> | > 
> | >   1) in ht_lookup():  We first compare hash_values, then lenghts and
> | >      finally characters.  The idea being that the first two
> | >      comparaisons will discriminate most of the identifiers.
> | > 
> | >   2) in ht_expand():  We don't need to re-compute the hash values when
> | >      expanding the table.
> | > 
> | > Bootstrapped and tested on an i686-pc-linux-gnu.
> | > OK for gcc-3_3-branch and mainline?
> | 
> | What effect does this have on our memory usage?  It's an extra word per
> | hashtable entry.
> 
> On an IA64, it is for free.
> 
> On an IA32, this is effectively an extra word, but on the sources I'm
> using to mesure compile-time performance (qt-3.1.1) I didn't see any
> noticeable memory usage degradation.
> 
> Without hash value caching we're forced to use extremely
> time-inefficient algorithms to implement name lookup.  On the balance,
> we can pay for the extra word.

Thanks.  I'm just instinctively nervous about performance patches which
have neither memory nor time performance data with them.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer