digitalmars.D.bugs - [Issue 12991] New: Possible performance optimization for std.range
- via Digitalmars-d-bugs (43/43) Jun 25 2014 https://issues.dlang.org/show_bug.cgi?id=12991
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). --
Jun 25 2014