This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
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 â
Attachment:
signature.asc
Description: OpenPGP digital signature
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |