Re: DT_GNU_HASH: ~ 50% dynamic linking improvement

["djamel anonymous" <djam8193ah at hotmail dot com>]

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 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: appels gratuits de PC à PC ! 
http://www.msn.fr/msger/default.asp