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 reply "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
parent reply "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
parent reply "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
parent reply "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
parent reply "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
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
prev 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 "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 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