Boost logo

Glas :

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).

vector<double> v(1000,1),w(1000,2),z(1000);
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);
std::cout << z ;

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.


> 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?