Re: Dynamic linking optimizations

[Jakub Jelinek <jakub at redhat dot com>]

On Tue, Mar 03, 2009 at 10:22:39AM -0800, Ian Lance Taylor wrote:
> John Moser <nigelenki@comcast.net> writes:
> 
> >> Character comparisons are fast.  It doesn't help to minimize them if it
> >> makes each operation cost more on average.
> >
> > Well, the "operations" would  be following a branch, which involves
> > jumping by a computed offset and reading in a byte (to use as an index).
> 
> Yes.  On a modern processor, a character comparison is much faster than
> a mispredicted branch (I would guess that the memory cache will hit
> about as often for both algorithms).  The branches in your algorithm
> would be difficult for the processor to predict correctly, so I think
> one must assume that half of them will be mispredicted.

Also, for symbol lookup speed the most important thing is how many
cache lines you need to read, and, as in typical programs these days there are
dozens to hundreds of shared libraries, not finding a symbol you're looking
for is more probable than that you find it.  So you really want to optimize
for as few cache lines touched as possible for the case a symbol isn't found
in a shared library.  DT_GNU_HASH section layout is quite good in this.

	Jakub