Re: DT_GNU_HASH: ~ 50% dynamic linking improvement

[Jakub Jelinek <jakub at redhat dot com>]

On Wed, Jul 05, 2006 at 10:07:15AM +0000, djamel anonymous wrote:
> Hello, first i thank you for your reply.the current hash function is 
> defined as:
> 
> static uint_fast32_t
> dl_new_hash (const char *s)
> {
>  uint_fast32_t h = 5381;
>  for (unsigned char c = *s; c != '\0'; c = *++s)
>    h = h * 33 + c;
>  return h & 0xffffffff;
> }
> 
> with this hash function we have strings of length 1 affect only the first 8 
> bits, strings of length 2 affect only the first 13 bits... strings of 
> length 4 effect only the first 23 bits.so the full 32 bits of the hash 
> value are affected beginning with strings of length 6 and above.

Does that matter?  Short symbol names are very rare:

N	number of symbols with length N
1 7
2 77
3 130
4 381
5 681
6 1153
7 1716
8 2373
9 3037
10 3552
11 4369
12 5481
13 6603
14 7183
15 7050
16 8848
17 9813
18 8906
19 10743
20 11301
21 11118
22 11143
23 11306
24 11629
25 11770
26 11533
27 12118
28 12159
29 11912
30 12025
31 12033
32 12111
33 11824
34 11481
35 12070
36 11506
37 10890
38 10953
39 10386
40 10005
...

i.e. there are just 0.23% symbols with strlen (symname) < 6.
Using low bits is a bad idea, but perhaps using some middle bits...
More than 32K buckets is extremely uncommon, so e.g. using
(hash >> 16) & 0x1f could work.

	Jakub