This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc 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 a small suggestion that may reduce the space occupied by the hash
table and reduce cache fills probability.
my suggestion is to align bucket chains to 8 bytes boundaries and to suppress the length field when the chain is of length 1.this is simply done by changing the signification of the buckets array values to :
offset=(bucket[hash%nbuckets]&)0xfffffffe
which will correspond to the offset: ((2 + nbuckets + N )&(-2)) * 4 which is aligned on 8 bytes boundary.the signification of the chain will depend on the lowest bit of bucket[hash%nbuckets]:
if ((bucket[hash%nbuckets]&0x1)==1) then the chain is of length 1 and contains :
symindx hash
if ((bucket[hash%nbuckets]&0x1)==0) then the chain is of variable length larger than 1 and contains :
symindx0 n hash0 hash1 .... hashn
so the chains space usage will be as follows :
1-a chain of length 1 that occupied previously 12 bytes will occupy 8 bytes.
2-a chain of length 2 that occupied previously 16 bytes will occupy 16 bytes.
3-a chain of length 3 that occupied previously 20 bytes will occupy 24 bytes.
4-a chain of length 4 that occupied previously 24 bytes will occupy 24 bytes.
5-a chain of length 4 that occupied previously 28 bytes will occupy 32 bytes.
.
.
if there is much more chains of length 1 than of size 3 or 5 then there will be a significant reduction in space usage.


for a chain of length one there will never be more than one cache fill while there was
previously a probability of 12.5% to do a second cache fill (assuming a cache of 64 bytes );the chain will cause a second cache fill if it begins at position 56 or 60 inside the cache line, and it has 16 possible positions. and hence the probability to do a second cache fill is of 2/16.
for a chain of length 2 similarly the probability of doing a second cache fill is reduced from
18.75% to 12.5%.


in conclusion if nbuckets is of the same order as nsymbols, the space usage will be reduced by
something near 4 bytes per symbol and the cache behavior will be better.
i hope my posting is useful.
best regards.


_________________________________________________________________
Testez Windows Llive Mail Beta ! http://www.msn.fr/newhotmail/Default.asp?Ath=f



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