PATCH to hashtable.[ch]: Cache hash value

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

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?

-- Gaby

? cp/name-lookup.c
Index: ChangeLog
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ChangeLog,v
retrieving revision 1.16114.2.304
diff -p -r1.16114.2.304 ChangeLog
*** ChangeLog	15 Mar 2003 16:59:59 -0000	1.16114.2.304
--- ChangeLog	15 Mar 2003 17:23:59 -0000
***************
*** 1,3 ****
--- 1,10 ----
+ 2003-03-15  Gabriel Dos Reis  <gdr at integrable-solutions dot net>
+ 
+ 	* hashtable.c (ht_lookup): Use HASH_VALUE as first probe when
+ 	looking up an identifier.  Cache hash value.
+ 	(ht_expand): Don't recompute hash value.  Use cached value.
+ 	* hashtable.h (struct ht_identifier): Add new field "hash_value".
+ 
  2003-03-15  Jason Merrill  <jason at redhat dot com>
  
  	PR debug/6387
Index: hashtable.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/hashtable.c,v
retrieving revision 1.5
diff -p -r1.5 hashtable.c
*** hashtable.c	14 Sep 2002 15:51:42 -0000	1.5
--- hashtable.c	15 Mar 2003 17:23:59 -0000
*************** ht_lookup (table, str, len, insert)
*** 141,147 ****
        if (node == NULL)
  	break;
  
!       if (HT_LEN (node) == len && !memcmp (HT_STR (node), str, len))
  	{
  	  if (insert == HT_ALLOCED)
  	    /* The string we search for was placed at the end of the
--- 141,148 ----
        if (node == NULL)
  	break;
  
!       if (node->hash_value == hash && HT_LEN (node) == len
!           && !memcmp (HT_STR (node), str, len))
  	{
  	  if (insert == HT_ALLOCED)
  	    /* The string we search for was placed at the end of the
*************** ht_lookup (table, str, len, insert)
*** 160,165 ****
--- 161,167 ----
    node = (*table->alloc_node) (table);
    table->entries[index] = node;
  
+   node->hash_value = hash;
    HT_LEN (node) = len;
    if (insert == HT_ALLOC)
      HT_STR (node) = obstack_copy0 (&table->stack, str, len);
*************** ht_expand (table)
*** 193,199 ****
        {
  	unsigned int index, hash, hash2;
  
! 	hash = calc_hash (HT_STR (*p), HT_LEN (*p));
  	hash2 = ((hash * 17) & sizemask) | 1;
  	index = hash & sizemask;
  
--- 195,201 ----
        {
  	unsigned int index, hash, hash2;
  
! 	hash = (*p)->hash_value;
  	hash2 = ((hash * 17) & sizemask) | 1;
  	index = hash & sizemask;
  
Index: hashtable.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/hashtable.h,v
retrieving revision 1.4
diff -p -r1.4 hashtable.h
*** hashtable.h	14 Sep 2002 15:51:42 -0000	1.4
--- hashtable.h	15 Mar 2003 17:23:59 -0000
*************** Foundation, 59 Temple Place - Suite 330,
*** 25,30 ****
--- 25,31 ----
  typedef struct ht_identifier ht_identifier;
  struct ht_identifier GTY(())
  {
+   unsigned int hash_value;
    unsigned int len;
    const unsigned char *str;
  };