This is the mail archive of the
java-discuss@sourceware.cygnus.com
mailing list for the Java project.
Re: Speeding up method searches
- To: Per Bothner <per at bothner dot com>
- Subject: Re: Speeding up method searches
- From: Jeff Sturm <jsturm at sigma6 dot com>
- Date: Mon, 10 Apr 2000 09:47:13 -0400
- CC: Bryce McKinlay <bryce at albatross dot co dot nz>, java-discuss at sourceware dot cygnus dot com
- Organization: AppNet
- References: <38F14C1E.CBA3055D@albatross.co.nz> <m2d7nysira.fsf@kelso.bothner.com>
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