www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - One against binary searches

reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Jul 30 2012
next sibling parent "Xinok" <xinok live.com> writes:
On Monday, 30 July 2012 at 15:40:32 UTC, 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

My stable sort makes heavy use of binary searches [1], so just for fun, I tried inserting a ternary search before the binary search. After some optimizing, I found it ideal to use ternary search on ranges larger than 8KiB (with 32KiB L1D cache) and binary search on anything less. While sorting using additional space saw no improvement, in-place sorting went from 408ms to 371ms. As well, there's a very negligible increase in the number of comparisons. [1] https://github.com/Xinok/XSort/blob/master/stablesort.d#L331
Jul 30 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Xinok:

 My stable sort makes heavy use of binary searches [1], so just 
 for fun, I tried inserting a ternary search before the binary 
 search.

I think in the end he suggests to use a "offseted binary" or a "quaternary search", over both binary and ternary searches (if the array is not too much small). Bye, bearophile
Jul 30 2012
prev sibling next sibling parent reply Don Clugston <dac nospam.com> writes:
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.
Jul 30 2012
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jul 30 2012
prev sibling parent Sean Cavanaugh <WorksOnMyMachine gmail.com> writes:
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).
Jul 31 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Don Clugston:

 Fantastic article, thanks!

If you like that, some time ago the same author has written an equally nice article on a related topic :-) http://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/ Bye, bearophile
Jul 30 2012
prev sibling next sibling parent "Xinok" <xinok live.com> writes:
On Monday, 30 July 2012 at 17:20:54 UTC, bearophile wrote:
 Xinok:

 My stable sort makes heavy use of binary searches [1], so just 
 for fun, I tried inserting a ternary search before the binary 
 search.

I think in the end he suggests to use a "offseted binary" or a "quaternary search", over both binary and ternary searches (if the array is not too much small).

An offseted binary search wouldn't work in this case. The "binary search" is actually comparing elements in two adjacent ranges which are equidistant from the center, so it's impossible to align in both ranges. I also tried a quaternary search, but it was 25-30ms slower than a ternary search, albeit it was a bit faster than a binary search.
Jul 30 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Xinok:

 I also tried a quaternary search, but it was 25-30ms slower 
 than a ternary search, albeit it was a bit faster than a binary 
 search.

I see. are you willing to add some of those searches here? http://dlang.org/phobos/std_range.html#SearchPolicy Bye, bearophile
Jul 30 2012
prev sibling next sibling parent "Xinok" <xinok live.com> writes:
On Monday, 30 July 2012 at 19:52:35 UTC, bearophile wrote:
 Xinok:

 I also tried a quaternary search, but it was 25-30ms slower 
 than a ternary search, albeit it was a bit faster than a 
 binary search.

I see. are you willing to add some of those searches here? http://dlang.org/phobos/std_range.html#SearchPolicy

I've added it to my todo list. I still haven't taken the time to familiarize myself with Phobos' conventions, so I don't feel comfortable contributing anything yet.
Jul 30 2012
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Xinok:

 I've added it to my todo list. I still haven't taken the time 
 to familiarize myself with Phobos' conventions, so I don't feel 
 comfortable contributing anything yet.

Thank you. The code we are talking about (like a quaternary search) is a small amount of code. And I think other people in GitHub are willing to show you where you are not following the conventions. Bye, bearophile
Jul 30 2012