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: lijakub at redhat dot com
- Cc: libc-alpha at sourceware dot org
- Date: Mon, 03 Jul 2006 17:36:23 +0000
- Subject: Re: DT_GNU_HASH: ~ 50% dynamic linking improvement
- Bcc:
Hello, i am writing again for porential speed improvement.the space used for
the hash table can be reduced by almost nchains words by using the least
siginificant bit of the hash value stored
in the chains a a chain terminator; this is possible because of the fact
that :
(hash1%nbuckets==hahs2%nbuckets and (hash1/2)==(hash2/2) ) => hash1==hash2
for every nbuckets>=2
this space improvement could be transformed into speed by various ways.i
suggest 3 different ways:
1-increase nbuckets by 50%: assuming almost each bucket points to a chain,
increasing the
number of buckets by 50% and deleting the length word from each chain will
result in in the same space usage.
2-use a second sparse hash table as suggested in my previous post: this
space hash table will have an average size of nsymbols bytes which will be
exactly the minimal size of the buckets array (nsymbols/4)*4 bytes. and
hence there will be a net space gain compared to the previous
impelemntation.
3-associate an additional word with each bucket; this word will avoid
accessing the chain in at least 7/8 of the time . to apply this solution the
bucket index will be obtained by :
bucket=(hash%(nbuckets*32))/32 inside the additional word a bit will be set
if and only if an element in the chain exists with the value
(hash%(nbuckets*32))%32 equal to i.
the bucket will be a struct of
{
unit32 offset;
unit32 sub_buckets;
};
we will go to the chain if and only if
(sub_buckets&(1<<(hash%(nbuckets*32))%32))==1.
the first solution seems to be the less attractive because it will most
likely give a modest improvement. the second solution avoids doing the
expensive operation of modulo nbuckets, but it seems it is unlikely that it
will be accepted because it adds a second hash table.
i hope this post will be useful.
best regards
_________________________________________________________________
MSN Messenger : discutez en direct avec vos amis !
http://www.msn.fr/msger/default.asp