Proposed Changes to the Range API for Phobos v3
Eyal Lotem
eyal at weka.io
Mon Sep 23 08:20:59 UTC 2024
Hey,
In continuation to the discussion about how 3-method ranges do
not apply at the conference, I wanted to refer you to Teodora
Serbanescu's work on ranges, showing how a single-method range
protocol is better optimized[1] than the 3 method range protocol.
Also, here's some benchmark code[2] of a repeated composition of
map/filter, and if you look at the generated assembly, you see
how well opApply is optimized vs. the phobos range which even in
-release -O4 remains non-inlined.
Results on my laptop:
**opApplyRange** took **13637** hnsecs
**phobosRange** took **207873** hnsecs
[1].
https://www.dropbox.com/scl/fi/bo9kj2jhd209ie503s00e/Teodora-Single-method-range-protocol.pdf?rlkey=p5qnai91xpsw1kme7im16zogy&st=l1phb9k5&dl=0
[2].
```
import std: iota, unaryFun, ForeachType;
struct MapResult(alias _Func, R) {
alias Func = unaryFun!_Func;
R underlying;
int opApply(scope int delegate(ref
typeof(Func(ForeachType!R.init))) dg) {
foreach(ref x; underlying) {
auto res = Func(x);
if(int rc = dg(res)) return rc;
}
return 0;
}
}
struct FilterResult(alias _Func, R) {
alias Func = unaryFun!_Func;
R underlying;
int opApply(scope int delegate(ref ForeachType!R) dg) {
foreach(ref x; underlying) {
if(Func(x)) if(int rc = dg(x)) return rc;
}
return 0;
}
}
auto map(alias Func, R)(R rng) { return MapResult!(Func, R)(rng);
}
auto filter(alias Func, R)(R rng) { return FilterResult!(Func,
R)(rng); }
auto benchmark(alias F, Args...)(auto ref Args args) {
import std: forward, writefln;
import std.datetime.stopwatch: StopWatch, AutoStart;
auto sw = StopWatch(AutoStart.yes);
scope(exit) {
sw.stop();
writefln("%s took %s hnsecs", __traits(identifier, F),
sw.peek.total!"hnsecs");
}
return F(forward!args);
}
auto opApplyRange(ref uint res) {
foreach(x;
iota(1000000).filter!"a%2".map!"a*2".filter!"a%3".map!"a*2".filter!"a%3".map!"a*2".filter!"a%3") res += x;
}
auto phobosRange(ref uint res) {
import std: map, filter;
foreach(x;
iota(1000000).filter!"a%2".map!"a*2".filter!"a%3".map!"a*2".filter!"a%3".map!"a*2".filter!"a%3") res += x;
}
unittest {
import std: writeln;
uint res = 0;
benchmark!opApplyRange(res);
benchmark!phobosRange(res);
}
```
More information about the Digitalmars-d
mailing list