This is the mail archive of the
gdb-patches@sources.redhat.com
mailing list for the GDB project.
Re: [RFC] Symbol table hashing patch
- To: Daniel Jacobowitz <drow at mvista dot com>
- Subject: Re: [RFC] Symbol table hashing patch
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Mon, 1 Oct 2001 20:39:56 -0400
- Cc: Elena Zannoni <ezannoni at cygnus dot com>, gdb-patches at sources dot redhat 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