MinMax benchmark vs. reduce

minmax_benchmark.d

import std.stdio;
import std.range;
import std.datetime;
import std.conv;
import std.algorithm;
import std.traits;
import std.typecons;
import std.functional;

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

auto minmaxElement(alias map, alias selector = "a < b", Range)(Range r)
    if (isInputRange!Range && !isInfinite!Range &&
        is(typeof(unaryFun!map(ElementType!(Range).init))))
in
{
    assert(!r.empty, "r is an empty range");
}
body
{
    alias Element = ElementType!Range;
    Unqual!Element seed = r.front;
    r.popFront();
    return minmaxElement!(map, selector)(r, seed, seed);
}

/// ditto
auto minmaxElement(alias map, alias selector = "a < b", Range,
                      RangeElementType = ElementType!Range)
                     (Range r, RangeElementType minSeed, RangeElementType maxSeed)
    if (isInputRange!Range && !isInfinite!Range &&
        !is(CommonType!(ElementType!Range, RangeElementType) == void) &&
        is(typeof(unaryFun!map(ElementType!(Range).init))))
{
    alias mapFun = unaryFun!map;
    alias selectorFun = binaryFun!selector;

    alias Element = ElementType!Range;
    alias CommonElement = CommonType!(Element, RangeElementType);
    alias MapType = Unqual!(typeof(mapFun(CommonElement.init)));

    Unqual!CommonElement minElement = minSeed;
    Unqual!CommonElement maxElement = maxSeed;

    MapType minElementMapped = mapFun(minElement);
    MapType maxElementMapped = mapFun(maxElement);

    alias minmaxTuple = Tuple!(Unqual!CommonElement, "min", Unqual!CommonElement, "max");

    static if (isRandomAccessRange!Range && hasLength!Range)
    {
        foreach (const i; 0 .. r.length)
        {
            MapType mapElement = mapFun(r[i]);
            if (selectorFun(mapElement, minElementMapped))
            {
                minElement = r[i];
                minElementMapped = mapElement;
            }
            if (selectorFun(maxElementMapped, mapElement))
            {
                maxElement = r[i];
                maxElementMapped = mapElement;
            }
        }
    }
    else
    {
        while (!r.empty)
        {
            MapType mapElement = mapFun(r.front);
            if (selectorFun(mapElement, minElementMapped))
            {
                minElement = r.front;
                minElementMapped = mapElement;
            }
            if (selectorFun(maxElementMapped, mapElement))
            {
                maxElement = r.front;
                maxElementMapped = mapElement;
            }
            r.popFront();
        }
    }
    return minmaxTuple(minElement, maxElement);
}

private auto minmaxElement(alias selector = "a < b", Range)(Range r)
    if (isInputRange!Range && !isInfinite!Range &&
        !is(typeof(unaryFun!selector(ElementType!(Range).init))))
{
    alias Element = ElementType!Range;
    Unqual!Element seed = r.front;
    r.popFront();
    return minmaxElement!selector(r, seed, seed);
}

// if we only have one statement in the loop it can be optimized a lot better
private auto minmaxElement(alias selector = "a < b", Range,
                      RangeElementType = ElementType!Range)
                     (Range r, RangeElementType minSeed, RangeElementType maxSeed)
    if (isInputRange!Range && !isInfinite!Range &&
        !is(CommonType!(ElementType!Range, RangeElementType) == void) &&
        !is(typeof(unaryFun!selector(ElementType!(Range).init))))
{
    alias Element = ElementType!Range;
    alias CommonElement = CommonType!(Element, RangeElementType);
    alias selectorFun = binaryFun!selector;

    Unqual!CommonElement minElement = minSeed;
    Unqual!CommonElement maxElement = maxSeed;

    alias minmaxTuple = Tuple!(Unqual!CommonElement, "min", Unqual!CommonElement, "max");

    // direct access via a random access range is faster
    static if (isRandomAccessRange!Range)
    {
        foreach (const i; 0 .. r.length)
        {
            if (selectorFun(r[i], minElement))
                minElement = r[i];

            if (selectorFun(maxElement, r[i]))
                maxElement = r[i];
        }
    }
    else
    {
        while (!r.empty)
        {
            if (selectorFun(r.front, minElement))
                minElement = r.front;

            if (selectorFun(maxElement, r.front))
                minElement = r.front;

            r.popFront();
        }
    }

    return minmaxTuple(minElement, maxElement);
}

void main()
{
    alias F = int;
    auto n = 80_000;
    auto arr = iota(n).map!(to!F).array;

    auto bench = benchmark!(
        { doNotOptimizeAway(arr.reduce!(min, max)); },
        { doNotOptimizeAway(arr.minmaxElement!"a"); },
        { doNotOptimizeAway(arr.minmaxElement); },
    )(50_000);

    string[] names = ["reduce", "minMax", "minMax.identity"];
    foreach(j,r;bench)
        writefln("%-15s = %s", names[j], r.to!Duration);
}

results

> dmd -inline -O -release -boundscheck=off test.d && ./test
reduce          = 8 secs, 507 ms, 942 μs, and 3 hnsecs
minMax          = 4 secs, 606 ms, 642 μs, and 2 hnsecs
minMax.identity = 4 secs, 405 ms, 915 μs, and 4 hnsecs

> ldc -O5 -release -boundscheck=off test.d && ./test
reduce          = 895 ms, 946 μs, and 9 hnsecs
minMax          = 5 secs, 378 ms, 146 μs, and 8 hnsecs
minMax.identity = 895 ms, 691 μs, and 7 hnsecs