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