Last active
February 19, 2018 04:24
-
-
Save wilzbach/ffd5d20639766a831fd4b1962572897a to your computer and use it in GitHub Desktop.
Performance benchmark of std.algorithm.iteration.joiner
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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([""], "")))); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
> 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment