DT_GNU_HASH: ~ 50% dynamic linking improvement

[Ulrich Drepper]

djamel anonymous wrote:
> this new additional hash table will occupy on average nsymbols*8 bits
> which is nsymbols bytes; this is because we need only 1 bit per bucket;

It doesn't matter that the second table is small.  The CPU has to read
the entire cache line.  And if he have a conflict (which is likely) we
have to read the second hash table.  That's what's killing the
performance.  L2 access is about 5 times slower than L1.  And since it's
unlikely you hit L2 in the cases where it really counts (i.e., big
programs with many DSOs and many symbols) you more likely hit the main
memory.  And here the factor is something like 80 (in ideal conditions).
 So, the most important optimization is to reduce the number of cache
lines needed.

Prefiltering is only of advantage if using the second table is more
expensive.  It isn't here, as I explained.  All the entries of the hash
chain are most likely in one cache line and therefore, unless we have a
full hash value match, we have to read one cache line.  With your method
you can get by with reading only one cache line only if there is no hash
collision.  I.e., no collision for any of the symbols used, defined or
undefined in the specific DSO.  That's not likely for any reasonable
hash table size.

-- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 251 bytes
Desc: OpenPGP digital signature
URL: <https://sourceware.org/pipermail/binutils/attachments/20060703/9a360959/attachment.sig>