range behaviour

[via Digitalmars-d]

On Wednesday, 14 May 2014 at 11:23:16 UTC, Ola Fosheim Grøstad 
wrote:
> On Wednesday, 14 May 2014 at 09:47:56 UTC, Marc Schütz wrote:
>> I wouldn't say never, because optimizers have become damn good.
>
> Well, "never" without a proof is of course a too strong claim. 
> :-) I agree with that, but I don't think optimizers are that 
> good yet even though some of my troubles have been solved.
>
>> I believe the additional overhead of lazy initialization is 
>> mostly optimized away where it matters, i.e. inner loops, 
>> because  the compiler can see that the initialization has 
>> already been performed in the first iteration. All it requires 
>> is unrolling the first iteration of the loop and treating it 
>> specially.

As a demonstration of what I mean:

///////////////////////////////////
import std.functional;

struct Filter(alias predicate, Range) {
         Range r;

private:
         bool is_initialized;

public:
         void initialize() {
                 alias pred = unaryFun!predicate;
                 if(is_initialized)
                         return;
                 while(!r.empty && !pred(r.front))
                         r.popFront();
                 is_initialized = true;
         }

         @property bool empty() {
                 initialize();
                 return r.empty;
         }

         @property auto front() {
                 initialize();
                 return r.front;
         }

         void popFront() {
                 r.popFront();
                 is_initialized = false;
         }

         auto sum() {
                 typeof(r.front) result = 0;
                 foreach(v; this)
                         result += v;
                 return result;
         }
}

auto filter(alias predicate, Range)(Range r) {
         return Filter!(predicate, Range)(r);
}

extern bool myPredicate(int);

struct MyGen {
         int front;
         int max;

         @property bool empty() {
                 return front > max;
         }

         void popFront() {
                 front++;
         }
}

void main() {
         auto gen = MyGen(1, 6);
         gen.filter!myPredicate.sum();
         gen.filter!"a % 2".sum();
         gen.filter!(a => true).sum();
}
///////////////////////////////////

Compile this with:

     ldc2 -O3 -release -output-s demo.d

and have a look a the generated assembly code for the 
Filter.sum() functions. All of them have been inlined as much as 
possible, and in particular the variable `is_initialized` has 
disappeared, even in the version that uses an external (unknown 
to the compiler) predicate.

Of course, if you don't access the range in a tight loop, these 
optimizations usually aren't possible. But arguably, in such 
cases an extra variable and an extra check for initialization 
aren't too bad. This means that we can have lazy implementations 
even without a guaranteed call to `empty`, and still have 
comparable performance to eagerly initialized ranges where it 
matters most.