Re: PATCH to hashtable.[ch]: Cache hash value

[Gabriel Dos Reis <gdr at integrable-solutions dot net>]

Daniel Jacobowitz <drow at mvista dot 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.

-- Gaby