On 7/30/12 1: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.
BTW we have alternative searches in sorted ranges that are
cache-friendly in Phobos, trot and gallop (backwards and forwards):
http://dlang.org/phobos/std_range.html. They work well if there's a good
assumption that the searched item is toward the beginning or the end of
the range, and galloping search has O(log n) complexity.
Andrei
