Speeding up method searches

Mon Apr 10 06:33:00 GMT 2000

Per Bothner wrote:
> There is a tradeoff here: A binary search will use fewer comparisons
> than a linear search on interned strings, but the cost of each
> comparison is much cheaper in the latter case, since you don't need
> to look at a single character.

Especially when you consider cache behavior. The binary search is far
more likely to generate cache misses. Linear searches can perform
remarkably well on today's >500MHz processors.
Some benchmarks might be worthwhile. I have some Java wrapper code for
the x86 counter (rdtsc) lying somewhere around here if anybody is
interested...
-- 
Jeff Sturm
jsturm@sigma6.com