Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
benchmark std.algorithm.searching.extremum with and without identity specialization
> 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
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment