Skip to content

Instantly share code, notes, and snippets.

@wilzbach

wilzbach/benchmark.md

Created May 5, 2017 14:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save wilzbach/3407d80bfa757d46a3ac59a873d5f085 to your computer and use it in GitHub Desktop.
Save wilzbach/3407d80bfa757d46a3ac59a873d5f085 to your computer and use it in GitHub Desktop.
Download ZIP
minmaxElement comparison
Raw
benchmark.md

RandomAccess

ldc -release -O5 -mcpu=native test.d && ./test
reduce!(min,max) = 7 secs, 722 ms, 265 μs, and 4 hnsecs
fold.minMax     = 5 secs, 770 ms, and 427 μs
minmaxElement   = 5 secs, 410 ms, and 31 μs
minmaxElementInPairs = 15 secs, 362 ms, 724 μs, and 3 hnsecs

InputRange

>  ldc -release -O5 -mcpu=native test.d && ./test
reduce!(min,max) = 7 secs, 215 ms, 601 μs, and 1 hnsec
fold.minMax     = 6 secs, 507 ms, 278 μs, and 5 hnsecs
minmaxElement   = 6 secs, 361 ms, 248 μs, and 8 hnsecs
minmaxElementInPairs = 12 secs, 344 ms, 548 μs, and 3 hnsecs
Raw
test.d
import std.range;
import std.traits;
import std.algorithm;
import std.functional;
import std.typecons;
import std.stdio;
private void doNotOptimizeAway(T)(auto ref T t)
{
import core.thread : getpid;
import std.stdio : writeln;
if(getpid() == 1) {
writeln(*cast(char*)&t);
}
assert(t[0] == 0);
assert(t[1] == 99_999);
}
auto minmaxElement(alias map = "a", alias selector = "a < b", Range)(Range r)
if (isInputRange!Range && !isInfinite!Range)
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 = "a", 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))
{
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);
}
auto minmaxElementInPairs(alias map = "a", alias selector = "a < b", Range)(Range r)
if (isInputRange!Range && !isInfinite!Range)
in
{
assert(!r.empty, "r is an empty range");
}
body
{
alias Element = ElementType!Range;
Unqual!Element seed = r.front;
r.popFront();
return minmaxElementInPairs!(map, selector)(r, seed, seed);
}
/// ditto
auto minmaxElementInPairs(alias map = "a", 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))
{
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)
{
// We iterate in pairs of two, so we the uneven element needs to be skipped
if (r.length % 2 == 1)
{
MapType mapElement = mapFun(r[$ - 1]);
if (selectorFun(mapElement, minElementMapped))
{
minElement = r[$ - 1];
minElementMapped = mapElement;
}
if (selectorFun(maxElementMapped, mapElement))
{
maxElement = r[$ - 1];
maxElementMapped = mapElement;
}
}
foreach (const i; 0 .. r.length / 2)
{
immutable k = i * 2;
MapType mapElement1 = mapFun(r[k]);
MapType mapElement2 = mapFun(r[k + 1]);
if (selectorFun(mapElement1, mapElement2))
{
if (selectorFun(mapElement1, minElementMapped))
{
minElement = r[k];
minElementMapped = mapElement1;
}
if (selectorFun(maxElementMapped, mapElement2))
{
maxElement = r[k + 1];
maxElementMapped = mapElement2;
}
}
else
{
if (selectorFun(mapElement2, minElementMapped))
{
minElement = r[k + 1];
minElementMapped = mapElement2;
}
if (selectorFun(maxElementMapped, mapElement1))
{
maxElement = r[k];
maxElementMapped = mapElement1;
}
}
}
}
else
{
while (!r.empty)
{
MapType rawElement1 = r.front;
MapType mapElement1 = mapFun(rawElement1);
r.popFront();
// check if the range had an uneven amount of elements and thus has ended
if (r.empty)
{
if (selectorFun(mapElement1, minElementMapped))
{
minElement = rawElement1;
minElementMapped = mapElement1;
}
if (selectorFun(maxElementMapped, mapElement1))
{
maxElement = rawElement1;
maxElementMapped = mapElement1;
}
break;
}
MapType rawElement2 = r.front;
MapType mapElement2 = mapFun(rawElement2);
r.popFront();
if (selectorFun(mapElement1, mapElement2))
{
if (selectorFun(mapElement1, minElementMapped))
{
minElement = rawElement1;
minElementMapped = mapElement1;
}
if (selectorFun(maxElementMapped, mapElement2))
{
maxElement = rawElement2;
maxElementMapped = mapElement2;
}
}
else
{
if (selectorFun(mapElement2, minElementMapped))
{
minElement = rawElement2;
minElementMapped = mapElement2;
}
if (selectorFun(maxElementMapped, mapElement1))
{
maxElement = rawElement1;
maxElementMapped = mapElement1;
}
}
}
}
return minmaxTuple(minElement, maxElement);
}
auto minmaxElementNoMap(alias selector = "a < b", Range)(Range r)
if (isInputRange!Range && !isInfinite!Range)
in
{
assert(!r.empty, "r is an empty range");
}
body
{
alias Element = ElementType!Range;
Unqual!Element seed = r.front;
r.popFront();
return minmaxElementNoMap!(selector)(r, seed, seed);
}
auto minmaxElementNoMap(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))
{
alias selectorFun = binaryFun!selector;
alias Element = ElementType!Range;
alias CommonElement = CommonType!(Element, RangeElementType);
Unqual!CommonElement minElement = minSeed;
Unqual!CommonElement maxElement = maxSeed;
alias minmaxTuple = Tuple!(Unqual!CommonElement, "min", Unqual!CommonElement, "max");
static if (isRandomAccessRange!Range && hasLength!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))
{
maxElement = r.front;
}
r.popFront();
}
}
return minmaxTuple(minElement, maxElement);
}
void main() {
import std.datetime;
import std.stdio;
import std.array;
import std.conv;
import std.random;
auto rawArr = iota(50_000).array;
rawArr.randomShuffle;
//auto arr = rawArr.filter!(a => a);
auto arr = rawArr;
enum benchmarkType = "map";
static if (benchmarkType == "map")
{
alias m = (a) => a + a;
auto bench = benchmark!(
{ doNotOptimizeAway({
return arr.reduce!(
(a, b) => min(m(a), m(b)),
(a, b) => max(m(a), m(b)),
);
}());},
{ doNotOptimizeAway({
static struct MinMaxTuple(T) {
T min, max, minMap, maxMap;
T opIndex(size_t i) { return i ? max : min; }
}
return arr.dropOne.fold!((a, b) {
auto c = m(b);
if (c < a.minMap)
{
a.min = b;
a.minMap = c;
}
if (c > a.maxMap)
{
a.max = b;
a.maxMap = c;
}
return a;
})(MinMaxTuple!size_t(arr.front, arr.front, m(arr.front), m(arr.front)));
}());},
{ doNotOptimizeAway({
return arr.minmaxElement!m;
}());},
{ doNotOptimizeAway({
return arr.minmaxElementInPairs!m;
}());},
)(100_000);
string[] names = ["reduce!(min,max)", "fold.minMax", "minmaxElement", "minmaxElementInPairs"];
}
else
{
auto bench = benchmark!(
{ doNotOptimizeAway({
return arr.reduce!(min, max);
}());},
{ doNotOptimizeAway({
return arr.minmaxElement;
}());},
{ doNotOptimizeAway({
return arr.minmaxElementNoMap;
}());},
)(100_000);
string[] names = ["reduce!(min,max)", "minmaxElement", "minmaxElementNoMap"];
}
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