Performance benchmark of std.algorithm.iteration.joiner

joiner.d

import std.range, std.traits;
import std.stdio;

private void doNotOptimizeAway(T)(auto ref T t)
{
    import core.thread : getpid;
    import std.stdio;
    if(getpid() == 1) {
        writeln(*cast(char*)&t);
    }
}

auto joiner(RoR, Separator)(RoR r, Separator sep)
if (isInputRange!RoR && isInputRange!(ElementType!RoR)
        && isForwardRange!Separator
        && is(ElementType!Separator : ElementType!(ElementType!RoR)))
{
    static struct Result
    {
        private RoR _items;
        private ElementType!RoR _current;
        private Separator _sep;
        private size_t sepIndex;
        private size_t sepLength; // cache the length for performance

        this(RoR items, Separator sep)
        {
            _items = items;
            _sep = sep;
            sepIndex = sepLength = sep.length;

            if (_items.empty)
                _current = _current.init;   // set invalid state
            else
            {
                useCurrent();
                // No data in the current item - toggle to use the separator
                if (_current.empty)
                    useSeparator();
            }
        }

        @property auto empty()
        {
            return _items.empty;
        }

        @property ElementType!(ElementType!RoR) front()
        {
            if (sepIndex < sepLength)
                return _sep[sepIndex];
            return _current.front;
        }

        private void useCurrent()
        {
            // If we're exporting .save, we must not consume any of the
            // subranges, since RoR.save does not guarantee that the states
            // of the subranges are also saved.
            static if (isForwardRange!RoR &&
                       isForwardRange!(ElementType!RoR))
                _current = _items.front.save;
            else
                _current = _items.front;
        }

        void useSeparator()
        {
            if (!_current.empty) return;
            if (_items.empty) return;
            _items.popFront;

            // If there are no more items, we're done, since separators are not
            // terminators.
            if (_items.empty) return;

            if (_sep.empty)
            {
                // pop through empty elements
                while (_items.front.empty)
                {
                    _items.popFront;
                    if (_items.empty) return;
                }
                useCurrent();
            }
            else
            {
                sepIndex = 0;
            }
        }

        void popFront()
        {
            assert(!_items.empty, "Attempting to popFront an empty joiner.");
            // Using separator?
            if (sepIndex < sepLength)
            {
                sepIndex++;
                if (_items.empty) return;
                if (sepIndex < sepLength) return;
                _current = _items.front;
                if (_current.empty)
                    useSeparator();
            }
            else
            {
                // we're using the range
                _current.popFront();
                useSeparator();
            }
        }

        static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
        {
            @property auto save()
            {
                Result copy = this;
                copy._items = _items.save;
                copy._current = _current.save;
                copy._sep = _sep.save;
                return copy;
            }
        }
    }
    return Result(r, sep);
}

auto joinerAliasThis(bool F, RoR, Separator)(RoR r, Separator sep)
if (isInputRange!RoR && isInputRange!(ElementType!RoR)
        && isForwardRange!Separator
        && is(ElementType!Separator : ElementType!(ElementType!RoR)))
{
    static struct Result
    {
        private RoR _items;
        private ElementType!RoR _current;
        //static if (isRandomAccessRange!Separator)
        static if (F)
        {
            static struct CurrentSep
            {
                private Separator _sep;
                private size_t sepIndex;
                private size_t sepLength; // cache the length for performance
                auto front() { return _sep[sepIndex]; }
                auto popFront() { return sepIndex++; }
                auto empty() { return sepIndex >= sepLength; }
                auto save()
                {
                    auto copy = this;
                    copy._sep = _sep;
                    return copy;
                }
                void reset()
                {
                    sepIndex = 0;
                }

                void init(Separator sep)
                {
                    _sep = sep;
                    sepIndex = sepLength = _sep.length;
                }
            }
        }
        else
        {
            static struct CurrentSep
            {
                private Separator _sep;
                Separator payload;

                alias payload this;

                auto save()
                {
                    auto copy = this;
                    copy._sep = _sep;
                    return copy;
                }

                void reset()
                {
                    payload = _sep.save;
                }

                void init(Separator sep)
                {
                    _sep = sep;
                }
            }
        }

        private CurrentSep _currentSep;

        private void setItem()
        {
            if (!_items.empty)
            {
                // If we're exporting .save, we must not consume any of the
                // subranges, since RoR.save does not guarantee that the states
                // of the subranges are also saved.
                static if (isForwardRange!RoR &&
                           isForwardRange!(ElementType!RoR))
                    _current = _items.front.save;
                else
                    _current = _items.front;
            }
        }

        private void useSeparator()
        {
            // Separator must always come after an item.
            assert(_currentSep.empty && !_items.empty,
                    "joiner: internal error");
            _items.popFront();

            // If there are no more items, we're done, since separators are not
            // terminators.
            if (_items.empty) return;

            if (_currentSep._sep.empty)
            {
                // Advance to the next range in the
                // input
                while (_items.front.empty)
                {
                    _items.popFront();
                    if (_items.empty) return;
                }
                setItem;
            }
            else
            {
                _currentSep.reset;
                assert(!_currentSep.empty);
            }
        }

        this(RoR items, Separator sep)
        {
            _items = items;
            _currentSep.init(sep);

            //mixin(useItem); // _current should be initialized in place
            if (_items.empty)
                _current = _current.init;   // set invalid state
            else
            {
                // If we're exporting .save, we must not consume any of the
                // subranges, since RoR.save does not guarantee that the states
                // of the subranges are also saved.
                static if (isForwardRange!RoR &&
                           isForwardRange!(ElementType!RoR))
                    _current = _items.front.save;
                else
                    _current = _items.front;

                if (_current.empty)
                {
                    // No data in the current item - toggle to use the separator
                    useSeparator();
                }
            }
        }

        @property auto empty()
        {
            return _items.empty;
        }

        @property ElementType!(ElementType!RoR) front()
        {
            if (!_currentSep.empty) return _currentSep.front;
            assert(!_current.empty, "Attempting to fetch the front of an empty joiner.");
            return _current.front;
        }

        void popFront()
        {
            assert(!_items.empty, "Attempting to popFront an empty joiner.");
            // Using separator?
            if (!_currentSep.empty)
            {
                _currentSep.popFront();
                if (!_currentSep.empty) return;
                if (_items.empty) return;
                setItem;
                if (_current.empty)
                {
                    // No data in the current item - toggle to use the separator
                    useSeparator();
                }
            }
            else
            {
                // we're using the range
                _current.popFront();
                if (!_current.empty) return;
                useSeparator();
            }
        }

        static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
        {
            @property auto save()
            {
                Result copy = this;
                copy._items = _items.save;
                copy._current = _current.save;
                copy._currentSep = _currentSep.save;
                return copy;
            }
        }
    }
    return Result(r, sep);
}

struct ZeroAppender
{
    size_t count;
    void put(T)(T t)
    {
        if (t == 'c')
            +++++count;
        else
            count++;
    }
}

version(unittest) {} else
void main() {
    import std.array;
    import std.datetime.stopwatch;
    import std.stdio;
    import std.conv;

    auto rawArr = "a"d.repeat(20_000);
    //auto arr = rawArr.filter!(a => a);
    auto arr = rawArr;
    auto bench = benchmark!(
        { doNotOptimizeAway({
            static import std.algorithm.iteration;
            ZeroAppender app;
            foreach (e; std.algorithm.iteration.joiner(arr, ","d))
                app.put(e);

            return app.count;
        }());},
        { doNotOptimizeAway({
            ZeroAppender app;
            foreach (e; arr.joinerAliasThis!false(","d))
                app.put(e);

            return app.count;
        }());},
        { doNotOptimizeAway({
            ZeroAppender app;
            foreach (e; arr.joinerAliasThis!true(","d))
                app.put(e);

            return app.count;
        }());},
        { doNotOptimizeAway({
            ZeroAppender app;
            foreach (es; arr)
            {
                foreach (e; es)
                    app.put(e);

                app.put(',');
            }
            return app.count;
        }());},
    )(100_000);

    immutable names = ["std.joiner", "std.joiner.alias", "new.joiner", "foreach"];
    foreach(j,r;bench)
        writefln("%-15s = %s", names[j], r.to!Duration);
}

unittest
{
    import std.stdio;
    ["", "foo", "", "bar"d, ""].joiner("|"d).writeln;
}

@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.conv : text;

    assert(["abc", "def"].joiner("").equal("abcdef"));
    assert(["Mary", "has", "a", "little", "lamb"]
        .joiner("...")
        .equal("Mary...has...a...little...lamb"));
    assert(["", "abc"].joiner("xyz").equal("xyzabc"));
    assert([""].joiner("xyz").equal(""));
    assert(["", ""].joiner("xyz").equal("xyz"));
}

@system unittest
{
    import std.algorithm.comparison : equal;
    import std.range.interfaces;
    import std.range.primitives;
    // joiner() should work for non-forward ranges too.
    auto r = inputRangeObject(["abc", "def"]);
    assert(equal(joiner(r, "xyz"), "abcxyzdef"));
}

@system unittest
{
    import std.algorithm.comparison : equal;
    import std.range;

    // Related to issue 8061
    auto r = joiner([
        inputRangeObject("abc"),
        inputRangeObject("def"),
    ], "-*-");

    assert(equal(r, "abc-*-def"));

    // Test case where separator is specified but is empty.
    auto s = joiner([
        inputRangeObject("abc"),
        inputRangeObject("def"),
    ], "");

    assert(equal(s, "abcdef"));

    // Test empty separator with some empty elements
    auto t = joiner([
        inputRangeObject("abc"),
        inputRangeObject(""),
        inputRangeObject("def"),
        inputRangeObject(""),
    ], "");

    assert(equal(t, "abcdef"));

    // Test empty elements with non-empty separator
    auto u = joiner([
        inputRangeObject(""),
        inputRangeObject("abc"),
        inputRangeObject(""),
        inputRangeObject("def"),
        inputRangeObject(""),
    ], "+-");

    assert(equal(u, "+-abc+-+-def+-"));

    // Issue 13441: only(x) as separator
    string[][] lines = [null];
    lines
        .joiner(only("b"))
        .array();
}

@safe unittest
{
    import std.algorithm.comparison : equal;

    // Transience correctness test
    struct TransientRange
    {
    @safe:
        int[][] src;
        int[] buf;

        this(int[][] _src)
        {
            src = _src;
            buf.length = 100;
        }
        @property bool empty() { return src.empty; }
        @property int[] front()
        {
            assert(src.front.length <= buf.length);
            buf[0 .. src.front.length] = src.front[0..$];
            return buf[0 .. src.front.length];
        }
        void popFront() { src.popFront(); }
    }

    // Test embedded empty elements
    auto tr1 = TransientRange([[], [1,2,3], [], [4]]);
    joiner(tr1, [-1]).writeln;
    assert(equal(joiner(tr1, [0]), [0,1,2,3,0,0,4]));

    // Test trailing empty elements
    auto tr2 = TransientRange([[], [1,2,3], []]);
    assert(equal(joiner(tr2, [0]), [0,1,2,3,0]));

    // Test no empty elements
    auto tr3 = TransientRange([[1,2], [3,4]]);
    assert(equal(joiner(tr3, [0,1]), [1,2,0,1,3,4]));

    // Test consecutive empty elements
    auto tr4 = TransientRange([[1,2], [], [], [], [3,4]]);
    tr4.joiner([0, 1]).writeln;
    assert(equal(joiner(tr4, [0,1]), [1,2,0,1,0,1,0,1,0,1,3,4]));

    // Test consecutive trailing empty elements
    auto tr5 = TransientRange([[1,2], [3,4], [], []]);
    assert(equal(joiner(tr5, [0,1]), [1,2,0,1,3,4,0,1,0,1]));
}

@safe unittest
{
    static assert(isInputRange!(typeof(joiner([""], ""))));
    static assert(isForwardRange!(typeof(joiner([""], ""))));
}

results

> ldmd -O3 -release -inline joiner.d && ./joiner
std.joiner      = 5 secs, 319 ms, 190 μs, and 8 hnsecs
std.joiner.alias = 5 secs, 567 ms, 148 μs, and 2 hnsecs
new.joiner      = 3 secs, 437 ms, 571 μs, and 2 hnsecs
foreach         = 2 secs, 768 ms, 547 μs, and 8 hnsecs