• via Digitalmars-d-bugs (43/43) Jun 25 2014 https://issues.dlang.org/show_bug.cgi?id=12991

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=12991

          Issue ID: 12991
           Summary: Possible performance optimization for std.range binary
                    search
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: Phobos
          Assignee: nobody puremagic.com
          Reporter: bearophile_hugs eml.cc

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).

--