Dynamic linking optimizations

[John Moser]

On Tue, 2009-03-03 at 10:22 -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.
> 

Umm... branch as in branch of a data structure.  But yeah, following a
branch of a data structure is done by a branching operator in a piece of
code.

Trees branch, tries branch.  Code also branches.  This makes discussions
like this hard because people start trying to apply "branch" to the
wrong definition... except that it's sort of overlapping in how it's
actually going to occur anyway.  Following a branch of a trie is
analogous to selecting a bucket in a hash table:  both of these involve
following a specific branch off a data structure, and both are
implemented with a branch in code logic (if the bucket's empty don't go
anywhere from there!).

> Ian