Re: DT_GNU_HASH: ~ 50% dynamic linking improvement

["djamel anonymous" <djam8193ah at hotmail dot com>]

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/