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

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

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

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.

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

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

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.

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

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.

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