faster splitter

[qznc via Digitalmars-d]

On Monday, 4 March 2013 at 19:11:17 UTC, Steven Schveighoffer 
wrote:
> On Mon, 04 Mar 2013 12:35:23 -0500, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> That's comparable, please file an enh request.
>
> http://d.puremagic.com/issues/show_bug.cgi?id=9646


Below is an implementation, which matches MySplitter with dmd, 
but not with ldc. More precisely:

dmd -O -release -inline -noboundscheck:
std.algorithm.splitter took 5 secs, 170 ms, and 656 μs
MySplitter took 4 secs, 835 ms, 748 μs, and 1 hnsec
my_splitter took 4 secs, 862 ms, 914 μs, and 4 hnsecs

ldc2 -O -release:
std.algorithm.splitter took 3 secs, 540 ms, and 84 μs
MySplitter took 2 secs, 288 ms, and 535 μs
my_splitter took 3 secs, 463 ms, and 897 μs

CPU: Intel i7 M 620 2.67GHz
dmd: v2.070.2
ldc: 0.17.1 (based on DMD v2.068.2 and LLVM 3.7.1)

auto my_splitter(alias pred = "a == b", Range, Separator)(Range 
r, Separator s)
if (is(typeof(binaryFun!pred(r.front, s.front)) : bool)
         && (hasSlicing!Range || isNarrowString!Range)
         && isForwardRange!Separator
         && (hasLength!Separator || isNarrowString!Separator))
{
     import std.algorithm.searching : find;
     import std.conv : unsigned;

     static struct Result
     {
     private:
         Range _input;
         Separator _separator;
         size_t _next_index;
         bool _empty;

         @property auto separatorLength() { return 
_separator.length; }

         void findIndex()
         {
             auto found = find!pred(_input, _separator);
             _next_index = _input.length - found.length;
         }

     public:
         this(Range input, Separator separator)
         {
             _input = input;
             _separator = separator;
             _empty = false;
             findIndex();
         }

         @property Range front()
         {
             assert(!empty);
             return _input[0 .. _next_index];
         }

         static if (isInfinite!Range)
         {
             enum bool empty = false;  // Propagate infiniteness
         }
         else
         {
             @property bool empty()
             {
                 return _empty;
             }
         }

         void popFront()
         {
             assert(!empty);
             if (_input.empty) {
                 _empty = true;
                 assert(_next_index == 0);
             } else if (_input.length == _next_index) {
                 _input = _input[$ .. $];
                 _empty = true;
             } else {
                 _input = _input[_next_index + separatorLength .. 
$];
                 findIndex();
             }
         }

         static if (isForwardRange!Range)
         {
             @property typeof(this) save()
             {
                 auto ret = this;
                 ret._input = _input.save;
                 return ret;
             }
         }
     }

     return Result(r, s);
}