Re: DT_GNU_HASH: ~ 50% dynamic linking improvement

[Ulrich Drepper <drepper at redhat dot com>]

djamel anonymous wrote:
> Hello, i am writing again for a small suggestion that may reduce the
> space occupied by the hash
> table and reduce cache fills probability.

I 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

- we limit the hash chain to a single cache line whenever possible and
  this is as I showed before almost always the case.  The operations
  all work on L1 cache and even 8 or 10 memory loads are cheaper
  than loading another cache line.  And that number of loads is just a
  worst case behavior, usually there are fewer.

- 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
  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.

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

Attachment: signature.asc
Description: OpenPGP digital signature