How about a Hash template?

[Sean Cavanaugh]

On 4/29/2011 6:19 PM, Alexander wrote:
> On 29.04.2011 21:58, Andrei Alexandrescu wrote:
>
>> You need to replace the assert and compile with -O -release -inline. My results:
>
> [snip]
>
> Still, straight comparison wins - 2x faster ;)
>
> /Alexander


When understanding the CPU platform you are on, one of the benchmarks 
you can do is to measure how many linear integer comparions you can do 
vs a binary search of the same size, and graph it out.

There is a crossover point where the binary search will be faster, but 
with modern CPUs the number of linear items you can search increases 
every year.

The linear search also makes extremely good use of the cache and 
hardware prefetching, and the branches (as well as the loop itself) will 
be predicted correctly until the terminating condition is found, where 
the binary search is mispredicted 50% of the time.  The last time I 
measured the crossover point around 60 integer values, and it wouldn't 
surprise me at all that its over 100 on newer chipsets (Sandy Bridge, 
Bulldozer etc).