DT_GNU_HASH: ~ 50% dynamic linking improvement

[djamel anonymous]

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