One against binary searches

[Sean Cavanaugh]

On 7/30/2012 12:28 PM, Don Clugston wrote:
> On 30/07/12 17:40, bearophile wrote:
>> This author writes very detailed analyses of low-level computational
>> matters, that appear on Reddit. This blog post he suggests to introduce
>> "offseted binary" or "quaternary search" instead of binary search in
>> Phobos:
>>
>> http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/
>>
>>
>>
>> Bye,
>> bearophile
>
> Fantastic article, thanks!
> The fact that physical addressing can influence L2 cache misses was
> completely new to me.

Binary searches also confuse hardware branch prediction by the code flow 
being wrong 50% of the time.   Small linear lists are actually faster to 
test because of this (and the added bonus of cache coherency).