Glas List: Re: [glas] When to evaluate expressions

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2007-01-04 03:47:01

To me, lazy evaluation is beneficial if you are not sure you are going 
to use the _whole_ result as described in 'More effective C++' (Meyers).
e.g.:

vector<double> v(1000,1),w(1000,2),z(1000);
z=v+w;
std::cout << z[3] ;

But to me the program above contains a serious programming error in the 
first place and thus lazy evaluation should not be used to cover it up. 
Because in most cases, lazy evaluation will give you a serious time 
penalty, e.g:

vector<double> v(1000,1),w(1000,2),z(1000),x(1000);
z=v+w;
std::cout << z ;
x=z+w;

where the z risks to be evaluated twice.

So, at least in numerical computing, it is the programmers 
responsibility to avoid computations that are not necessary. Just like 
it is any programmers responsibility to avoid defining variables that 
will not be used (although the compiler has little trouble detecting the 
latter situation).

There are however scenario's where some sort of lazy computation would 
be beneficial, like in:

matrix<double> A(1000,1000);
vector<double> x(1000),y(1000),z(1000);
z = gemv(A,x)
z += y

In this case, it would probably be more efficient to do: z = 
gemv(A,x)+y. This way, z will only be one time iterated over.
But again, delaying the evaluation of an expression in this way risks to 
degrade performance due to the problem described at the top.

So if we leave lazy evaluation out to avoid having to recompute things 
and therefore we also leave out optimizing blocks of expressions (like 
in the gemv example), we could suggest to the programmer to always write 
the least possible number of expressions. And thus, instead of breaking 
the gemv example up in two expression, why not write one expression like:

z = gemv(A,x) + y

This way, the numerical library (when using expression templates) can 
see the whole expression at once and can decide how to optimize it.

That works great for this example though but suppose we want to multiply 
3 matrices A,B and C. Writing

Z = prod(A,prod(B,C))

would be less performant as breaking this up into:

TMP = prod(B,C)
Z = prod(A,TMP)

Writing this as one expression though, would provide the numerical 
library all information necessary and eventually the library might 
decide to break the expression up and use a TMP matrix to be more 
efficient. For the library to detect these inefficiencies and to perform 
sub-expression optimisation is on the other hand really complicated. The 
compiler is certainly not able to help out here.

So the only one that can decide how and when to evaluate (sub-) 
expressions are the programmer or the numerical library. In an ideal 
world, it would be the numerical library but I am not convinced that 
this is feasible.

toon

> 
> Evaluation usually? occurs on assignment to a concrete container:
> 
> vector<T> out = in1 * in2;
> 
> But can be carried in deferred form:
> 
> typeof (in1 * in2) out = in1 * in2;
> 
> So the current practice (which is what I'm identifying above) is relying on 
> the programmer to decide when evaluation occurs.
> 
> My question is, is this the right appoach?  Perhaps, instead, by default the 
> compiler should decide?
>