Comment #0 by bearophile_hugs — 2014-06-25T14:00:37Z
In std.range there is a binary search for SortedRange:
// Assuming a predicate "test" that returns 0 for a left portion
// of the range and then 1 for the rest, returns the index at
// which the first 1 appears. Used internally by the search routines.
private size_t getTransitionIndex(SearchPolicy sp, alias test, V)(V v)
if (sp == SearchPolicy.binarySearch && isRandomAccessRange!Range)
{
size_t first = 0, count = _input.length;
while (count > 0)
{
immutable step = count / 2, it = first + step;
if (!test(_input[it], v))
{
first = it + 1;
count -= step + 1;
}
else
{
count = step;
}
}
return first;
}
Binary search isn't very cache-friendly, so perhaps inside the binary search it's a good idea to switch to a linear search when the search interval is small enough. Where "small enough" means few cache lines long (assuming cache lines of 64 bytes. So you need T.sizeof to know how many items of type T this interval is).
Comment #1 by andrei — 2014-06-25T14:12:26Z
A cache-friendly binary search with cache friendliness and performance guarantees would be galloping search.
Comment #2 by bearophile_hugs — 2014-06-25T14:16:52Z
(In reply to Andrei Alexandrescu from comment #1)
> A cache-friendly binary search with cache friendliness and performance
> guarantees would be galloping search.
That's not what I have suggested here. Here I have suggested to use binary search followed by linear search when the search range is few cache lines long. This is a generic (possible) improvement for the standard binary search, to be used (ideally) when you want to use a binary search.
Galloping search is for a different purpose, like when you know the data you search for is near the start (or end, or a given point) of the array.
Comment #3 by robert.schadek — 2024-12-01T16:21:36Z