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.
