Re: pending/975: [RFA] Use hash to speed up BINCL/INCL processing.

[Daniel Jacobowitz <drow at mvista dot com>]

The following reply was made to PR symtab/975; it has been noted by GNATS.

From: Daniel Jacobowitz <drow@mvista.com>
To: Klee Dienes <klee@apple.com>
Cc: gdb-gnats@sources.redhat.com
Subject: Re: pending/975: [RFA] Use hash to speed up BINCL/INCL processing.
Date: Sat, 15 Feb 2003 23:17:21 -0500

 On Sun, Dec 08, 2002 at 04:42:03AM -0500, Klee Dienes wrote:
 > 
 > >Number:         975
 > >Category:       pending
 > >Synopsis:       [RFA] Use hash to speed up BINCL/INCL processing.
 > >Confidential:   yes
 > >Severity:       serious
 > >Priority:       medium
 > >Responsible:    unassigned
 > >State:          open
 > >Class:          sw-bug
 > >Submitter-Id:   unknown
 > >Arrival-Date:   Thu Jan 30 04:48:00 UTC 2003
 > >Closed-Date:
 > >Last-Modified:
 > >Originator:     
 > >Release:        
 > >Organization:
 > >Environment:
 > >Description:
 >  --Apple-Mail-2-903781636
 >  Content-Transfer-Encoding: 7bit
 >  Content-Type: text/plain;
 >  	charset=US-ASCII;
 >  	format=flowed
 >  
 >  This increases the size of the temporary space used by BINCL/INCL 
 >  processing by 4 bytes per BINCL.  The benefit is that it removes a huge 
 >  number of string compares when processing large numbers of BINCLs and 
 >  EXCLS.
 >  
 >  
 >  2002-12-06  Klee Dienes  <kdienes@apple.com>
 >  
 >  	* dbxread.c (header_file_location): New field 'hash'.
 >  	(add_bincl_to_list): Set the 'hash' field.
 >  	(find_corresponding_bincl_psymtab): Compute the hash of 'name'
 >  	and use that to pre-check the comparison.
 
 Klee,
 
 Noticed this in my gdb-gnats folder today... I just wanted to comment
 that I'd rather we use an actual hash table - there's one in libiberty
 all set up and waiting for us to use - instead of another half-finished
 open-coded hash.  It may use a hash function, but the code below is
 still a linear scan of the BINCLs.  I've seen BINCL processing get up
 to a ridiculous percentage (20%?) of symbol reading time; if we're
 going to fix it, we should fix it so it never comes back.
 
 >  
 >  
 >  --Apple-Mail-2-903781636
 >  Content-Disposition: attachment;
 >  	filename=bincl-hash.txt
 >  Content-Transfer-Encoding: quoted-printable
 >  Content-Type: text/plain;
 >  	x-unix-mode=0644;
 >  	name="bincl-hash.txt"
 >  
 >  2002-12-06  Klee Dienes  <kdienes@apple.com>
 >  
 >  	* dbxread.c (header_file_location): New field 'hash'.
 >  	(add_bincl_to_list): Set the 'hash' field.
 >  	(find_corresponding_bincl_psymtab): Compute the hash of 'name'
 >  	and use that to pre-check the comparison.
 >  
 >  Index: dbxread.c
 >  =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
 >  =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
 >  =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
 >  RCS file: =
 >  /Volumes/Storage/Users/kdienes/source/cvs/cygnus/src/gdb/dbxread.c,v
 >  retrieving revision 1.43
 >  diff -u -r1.43 dbxread.c
 >  --- dbxread.c	2002/12/01 22:22:03	1.43
 >  +++ dbxread.c	2002/12/07 18:19:16
 >  @@ -285,6 +285,7 @@
 >   struct header_file_location
 >   {
 >     char *name;			/* Name of header file */
 >  +  unsigned long hash;		/* Hashed value of 'name' */
 >     int instance;			/* See above */
 >     struct partial_symtab *pst;	/* Partial symtab that has the
 >   				   BINCL/EINCL defs for this file */
 >  @@ -1058,6 +1059,11 @@
 >     return (nlist1.n_strx + stringtab_global + file_string_table_offset);
 >   }
 >   =0C
 >  +
 >  +/* Compute a hash value for a BINCL/EINCL filename string. */
 >  +
 >  +#define bincl_hash msymbol_hash
 >  +
 >   /* Initialize the list of bincls to contain none and have some
 >      allocated.  */
 >  =20
 >  @@ -1084,6 +1090,7 @@
 >         next_bincl =3D bincl_list + offset;
 >       }
 >     next_bincl->pst =3D pst;
 >  +  next_bincl->hash =3D bincl_hash (name);
 >     next_bincl->instance =3D instance;
 >     next_bincl++->name =3D name;
 >   }
 >  @@ -1096,9 +1103,11 @@
 >   find_corresponding_bincl_psymtab (char *name, int instance)
 >   {
 >     struct header_file_location *bincl;
 >  +  unsigned long hash =3D bincl_hash (name);
 >  =20
 >     for (bincl =3D bincl_list; bincl < next_bincl; bincl++)
 >  -    if (bincl->instance =3D=3D instance
 >  +    if ((bincl->hash =3D=3D hash)
 >  +	&& (bincl->instance =3D=3D instance)
 >   	&& STREQ (name, bincl->name))
 >         return bincl->pst;
 >  =20
 >  
 >  --Apple-Mail-2-903781636--
 >  
 >  
 > >How-To-Repeat:
 > >Fix:
 > >Release-Note:
 > >Audit-Trail:
 > >Unformatted:
 > 
 
 -- 
 Daniel Jacobowitz
 MontaVista Software                         Debian GNU/Linux Developer