Re: [RFC] Symbol table hashing patch

[Daniel Berlin <dan at cgsoftware dot com>]

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