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]

Re: DT_GNU_HASH: ~ 50% dynamic linking improvement


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



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