When to evaluate expressions

I've been thinking about this subject, and wondered if any of you have some
ideas on this.  (Disclaimer - I'm no expert).

With expression templates, evaluation of expressions is deferred.  This is a
bit like lazy evaluation in languages such as Haskell.

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?

This is a lot like other forms of optimization.  Ultimately, hand-tuned
assembly can out-perform compiled code - but only when the programmer has a
lot of knowledge and a lot of spare time.  Otherwise, the compiler can
generate better code.

Does anyone agree with me that it is desirable for a compiler to decide on the
point of evaluation of expressions (rather than the programmer)?  If so, is
there any reasonable way to implement this in c++?
_______________________________________________
glas mailing list
glas@...
http://lists.boost.org/mailman/listinfo.cgi/glas

[Marcin Zalewski]

Neal,

I think you are right; most of the time it would be best if the compiler could decide what to do. Unfortunately though, since expression templates are by their very design a user-level optimization, a compiler cannot optimize much. C++ will probably never include lazy computations like, for example, Haskell. The way to go is probably with external tools that translate generic code to C++ and choose how to handle lazy computations.

-m

On 1/3/07, Neal Becker <ndbecker2@...> wrote:

I've been thinking about this subject, and wondered if any of you have some
ideas on this.  (Disclaimer - I'm no expert).

With expression templates, evaluation of expressions is deferred.  This is a
bit like lazy evaluation in languages such as Haskell.

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?

This is a lot like other forms of optimization.  Ultimately, hand-tuned
assembly can out-perform compiled code - but only when the programmer has a
lot of knowledge and a lot of spare time.  Otherwise, the compiler can
generate better code.

Does anyone agree with me that it is desirable for a compiler to decide on the
point of evaluation of expressions (rather than the programmer)?  If so, is
there any reasonable way to implement this in c++?
_______________________________________________
glas mailing list
glas@...
http://lists.boost.org/mailman/listinfo.cgi/glas

_______________________________________________
glas mailing list
glas@...
http://lists.boost.org/mailman/listinfo.cgi/glas

[Toon Knapen]

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

_______________________________________________
glas mailing list
glas@...
http://lists.boost.org/mailman/listinfo.cgi/glas