This is the mail archive of the
libc-alpha@sourceware.org
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
- Cc: libc-alpha at sources dot redhat dot com
- Date: Mon, 03 Jul 2006 19:50:19 +0000
- Subject: Re: DT_GNU_HASH: ~ 50% dynamic linking improvement
- Bcc:
Hello, first thank you for your reply.here is an explanation of my scheme:
for an unsuccessfull search with the probability to go to the next step
between parenthesis:
hash_table1 (around 0.125) -> hash_table2(between 0.5 and 1 ) -> hash
chains(nearly 0 ) -> symbols strings
(here hash_table1 is the new hash table that is used to filter the queries
before accessing to hahs_table2 which is the hash table currently
implemented )
we will have between 1.1875 and 1.25 memory accesses per unsuccesfull query.
the original scheme was
hash_table2(between 0.5 and 1 ) -> hash chains(approx 0 ) -> symbols strings
which gives between 1.5 and 2 memory accesses per unsuccesfull query.
in fact the probability to go to hash chains is very close to 1 because the
number of buckets in hash2_table is quite low; hence the new number of
memory accesses is nearly 1.125 while the old is nearly 2 accesses.
the fact that the hash_table1 needs only 1 bit per bucket permits us to
have nsymbols*8
buckets for a space usage of only nsymbols bytes.this size permits to filter
out 87.5% of the unsuccesfull queries without continuing the search.
for the relative sizes of each structure :
hash_table1-> approx nsymbols bytes
hash_table2->between nsymbols bytes and nsymbols*8 bytes according to the
file elflink.c
chains->nsymbols*4 bytes
so (hash_table1/(hash_table1+hash_table2+chains)) will be betweeen 1/13 and
1/6; so the working set will be increased between 8.33333% and 20% .
as the hash_table1 size is in between 7.692% and 16.66% of the working set
and is accessed much more often than the other structures it is most likely
to fit into the l2 cache.
best regards.
_________________________________________________________________
MSN Hotmail sur i-mode? : envoyez et recevez des e-mails depuis votre
téléphone portable ! http://www.msn.fr/hotmailimode/