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).

Reply via email to