This is the mail archive of the
`binutils@sourceware.org`
mailing list for the binutils project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: "djamel anonymous" <djam8193ah at hotmail dot com>*To*: drepper at redhat dot com, michael dot meeks at novell dot com*Cc*: jakub at redhat dot com, binutils at sources dot redhat dot com, libc-alpha at sources dot redhat dot com*Date*: Fri, 30 Jun 2006 23:55:11 +0000*Subject*: Re: DT_GNU_HASH: ~ 50% dynamic linking improvement*Bcc*:

of things about dynamic linking. i have understood that this thread is about static hashing of strings.

my suggestion is about using sparse hashing which would improve further the speed in case of

unsuccesfull search.one possibility of adding such a thing is to add a second hash table of size

nbuckets*8 which will occupy nbuckets bytes where nbuckets is the size of the first hash table.

this second table which will have quarter the size of the first one, will be a simple array of bits: a set bit means that the bucket corresponds to a symbol, a zero bit means that the bucket doesn't correspond to a symbol. if nbuckets is equal to the number of symbols, an unsuccesfull search will access the first hashtable with probability at most 1/8.to apply this addition, the formulae for computing bucket num

for the first hash table will be (hash_value%(nbuckets*8))/8 and the bucket in the second hash table

will be computed with the formulae hash_value%(nbuckets*8). by using this additional hash table which

will have a marginal size compared to thr first hash table the cost of unsuccessful search will probably

decrease further.if the search have high probability to be successfull(for example when looking for a symbol that we know is present) the second table could be simply ignored and the search could begin directly with the first hash table.

best regards

MSN Hotmail sur i-mode? : envoyez et recevez des e-mails depuis votre téléphone portable ! http://www.msn.fr/hotmailimode/

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |