This is the mail archive of the 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]

Re: DT_GNU_HASH: ~ 50% dynamic linking improvement

Hello, first excuse my poor english.i am wrting this message despite tha fact that i don'y know much
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 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/ 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 !

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]