From mboxrd@z Thu Jan 1 00:00:00 1970 From: Daniel Berlin To: Daniel Jacobowitz Cc: Elena Zannoni , gdb-patches@sources.redhat.com Subject: Re: [RFC] Symbol table hashing patch Date: Mon, 01 Oct 2001 17:40:00 -0000 Message-id: <00B40344-B6CE-11D5-A80B-0030657B5340@cgsoftware.com> References: <20011001193830.A11559@nevyn.them.org> X-SW-Source: 2001-10/msg00027.html On Monday, October 1, 2001, at 07:38 PM, Daniel Jacobowitz wrote: > On Mon, Oct 01, 2001 at 07:12:41PM -0400, Elena Zannoni wrote: >> >> >> As a first comment,, I would strongly reccommend that you break the >> ALL_BLOCK_SYMBOLS changes into a separate patch. That way the >> significant changes to the symtab algorithms will become easier to >> review. It seems from you comments that the MINIMAL_SYMBOL_HASH_SIZE >> is also an independent fix. How about the bug in msymtab_hash_iw, can >> that be separated out as well? >> >> What is 113? >> > > Yes, msymtab_hash_iw is also independent. > > I'll start breaking it up. On the other hand, I can't do all of it > until I > get a little feedback - particularly, the sorting issues. So I would > appreciate any comments on the questions asked in the original message. > > As for 113, the exact value is up for debate, but it shows a bit of a > problem with the current hash functions: the values of *string are not > evenly distributed. Multiplying by 31 and then adding an ASCII value > of (usually) ~100 doesn't seem very effective. The thing to do would > probably be to take advantage of Zack Weinberg's recent research; he > spent some time finding a good hash function for the set of > identifiers GCC deals with. It's the same one that this patch > introduces: > > #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); > Yes, that's where i got it. It's actually in hashtab.c, named htab_hash_string It beats the FNV-1 hash (in terms of good distributions) by a small amount on strings, but not on other things. > For reference, the post is: > http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html > > -- > Daniel Jacobowitz Carnegie Mellon University > MontaVista Software Debian GNU/Linux Developer