benchmark std.algorithm.searching.extremum with and without identity specialization

results

> dmd -release -O test.d && ./test
extremum.before = 54 secs, 12 ms, 347 μs, and 9 hnsecs
extremum.after  = 29 secs, 521 ms, 896 μs, and 5 hnsecs

> ldc -release -O3 test.d && ./test
extremum.before = 13 secs, 186 ms, 176 μs, and 4 hnsecs
extremum.after  = 2 secs, 241 ms, 454 μs, and 9 hnsecs

test.d

import std.range;
import std.traits;
import std.algorithm;
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);
    }
}

private auto extremum(alias map = "a", alias selector = "a < b", Range,
                      RangeElementType = ElementType!Range)
                     (Range r, RangeElementType seedElement)
    if (isInputRange!Range && !isInfinite!Range &&
        !is(CommonType!(ElementType!Range, RangeElementType) == void))
{
    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 extremeElement = seedElement;
    MapType extremeElementMapped = mapFun(extremeElement);

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

struct IdentityFun {}

private auto extremumF(alias map = IdentityFun, alias selector = "a < b", Range,
                      RangeElementType = ElementType!Range)
                     (Range r, RangeElementType seedElement)
    if (isInputRange!Range && !isInfinite!Range &&
        !is(CommonType!(ElementType!Range, RangeElementType) == void))
{
    enum isMappingFirst = __traits(compiles, unaryFun!map(seedElement));
    enum isIdentity = is(map == IdentityFun);

    // shorthand: if a binary function is given, it is the selector
    static if (isMappingFirst || isIdentity)
    {
        alias selectorFun = binaryFun!selector;
    }
    else
    {
        alias selectorFun = binaryFun!map;
    }

    alias Element = ElementType!Range;
    alias CommonElement = CommonType!(Element, RangeElementType);
    Unqual!CommonElement extremeElement = seedElement;

    static if (isIdentity || !isMappingFirst)
    {
        static if (isRandomAccessRange!Range && hasLength!Range)
        {
            foreach (const i; 0 .. r.length)
            {
                if (selectorFun(r[i], extremeElement))
                {
                    extremeElement = r[i];
                }
            }
        }
        else
        {
            while (!r.empty)
            {
                if (selectorFun(r.front, extremeElement))
                {
                    extremeElement = r.front;
                }
                r.popFront();
            }
        }
    }
    else
    {
        alias mapFun = unaryFun!map;

        alias MapType = Unqual!(typeof(mapFun(CommonElement.init)));
        MapType extremeElementMapped = mapFun(extremeElement);
        static if (isRandomAccessRange!Range && hasLength!Range)
        {
            foreach (const i; 0 .. r.length)
            {
                MapType mapElement = mapFun(r[i]);
                if (selectorFun(mapElement, extremeElementMapped))
                {
                    extremeElement = r[i];
                    extremeElementMapped = mapElement;
                }
            }
        }
        else
        {
            while (!r.empty)
            {
                MapType mapElement = mapFun(r.front);
                if (selectorFun(mapElement, extremeElementMapped))
                {
                    extremeElement = r.front;
                    extremeElementMapped = mapElement;
                }
                r.popFront();
            }
        }
    }
    return extremeElement;
}

void main() {
    import std.datetime;
    import std.stdio;
    import std.array;
    import std.conv;
    import std.random;
    auto arr = iota(100_000).array;
    arr.randomShuffle;
    auto bench = benchmark!(
        { doNotOptimizeAway({
            return arr.extremum(100_000);
        }());},
        { doNotOptimizeAway({
            return arr.extremumF(100_000);
        }());},
    )(100_000);

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