[Issue 12991] New: Possible performance optimization for std.range binary search

[via Digitalmars-d-bugs]

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 at puremagic.com
          Reporter: bearophile_hugs at 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).

--