This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: DT_GNU_HASH: ~ 50% dynamic linking improvement
- 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:
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 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/