This is the mail archive of the binutils@sourceware.org mailing list for the binutils 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] |
in fact this second hash table is playing a role of a filter before the original table; a searchI see absolutely no benefit at all in any of this. The second hash table with the required second memory load would kill all the performance advantage. It's sole purpose would be to not compare the chain list elements at all. But:
- it has to be pessimistic. I.e., for the first table there are also collisions and when they happen, the search must be made
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; if this bit is set we continue the search into the original table otherwise the search is stopped after only one memory access and without doing actual division.- each element in your second hash table must point to the beginning of a chain. So here the huge overhead in the hash table sizing is costing a lot. Furthermore, the division is nowadays no problem at
costing a lot. Furthermore, the division is nowadays no problem at all anymore. It's fast. If you really care, modify your linker to size the hash table with a power of two and change the dynamic linker to optimize that case. It's easy enough to do. The linker already has a function to size the table more intelligently if requested.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |