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 
<seewebsiteforem...@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);
}