This is the mail archive of the
mailing list for the glibc project.
Re: DT_GNU_HASH: ~ 50% dynamic linking improvement
- From: "djamel anonymous" <djam8193ah at hotmail dot com>
- To: drepper at redhat dot com, michael dot meeks at novell dot com
- Cc: jakub at redhat dot com, binutils at sources dot redhat dot com, libc-alpha at sources dot redhat dot com
- Date: Mon, 03 Jul 2006 11:33:21 +0000
- Subject: 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 :
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
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
3-a chain of length 3 that occupied previously 20 bytes will occupy 24
4-a chain of length 4 that occupied previously 24 bytes will occupy 24
5-a chain of length 4 that occupied previously 28 bytes will occupy 32
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
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.
Testez Windows Llive Mail Beta !