1

Consider the two following functions:

std::pair<double,Vector> myMatrixOperation1(Matrix const& A, Vector const& V) {
    Vector AV = A*V;
    double norm_A_V = std::sqrt(dot(V,AV));

    return make_pair(norm_A_V,AV);
}

std::pair<double,Vector> myMatrixOperation2(Matrix const& A, Vector const& V) {
    return make_pair( norm(V,A) , A*V );
}
double norm(Vector const& V, Matrix const& innerProductMatrix) {
    double norm_A_V = std::sqrt(dot(V,innerProductMatrix*V));
}

They obviously do the same thing, except that the Matrix-Vector product is garanteed to be computed only once in the first function.

However, the second function is more readable because it was refactored in order to have a complete separation of concerns: the concept of the norm of a vector with respect to an arbitrary inner product was abstracted into a separate function.

Now the problem is that without any optimisation, the Matrix-Vector product is now computed twice.

My question is the following: Is the compiler smart enought to compute the Matrix-Vector product only once ? And if yes, what do I need to do ?

I suppose that at least I need to inline the norm() function. Also, regarding operator*(Matrix const& A, Vector const& V), is lazy evaluation of any help ? (Side-note: I am using the Eigen Library)

Note: I am aware of a similar question: Will the compiler optimize repeated math computations?. However, please note that my problem is harder for the compiler, since operator*(Matrix const& A, Vector const& V) is not a built-in, and hence the compiler should need some garantees about it

Edit:

After further thinking an this citation from Wikipedia (http://en.wikipedia.org/wiki/Optimizing_compiler):

For example, in some languages functions are not permitted to have side effects. Therefore, if a program makes several calls to the same function with the same arguments, the compiler can immediately infer that the function's result need be computed only once. In languages where functions are allowed to have side effects, another strategy is possible. The optimizer can determine which function has no side effects, and restrict such optimizations to side effect free functions. This optimization is only possible when the optimizer has access to the called function.

it seems like the compiler can replace the second function by the first one provided operator+ is pure (that is: no side effect). According to https://stackoverflow.com/a/5464114/1583122, in C++, purity can be garanteed to the compiler by telling it that a function is constexpr, has only constexpr function calls, and has const arguments. So I think it would be possible for a compiler to garantee such an optimization, provided some requirements are met. Further, note that restrictions on constexpr functions have been greatly reduced in C++14

Community
  • 1
  • 1
Bérenger
  • 2,678
  • 2
  • 21
  • 42
  • 2
    Actually both cases will have the product computed twice without further optimization. `A*V` (and `dot()`) both produce an expression tree object. The actual work is not done until you need the actual value - in conversion to `double` for the `sqrt` call and conversion to `Vector` to construct the `std::pair` return value. – T.C. Jul 22 '14 at 16:05
  • You're right. I changed from auto to Vector to explicitly ask for the computation to be done – Bérenger Jul 22 '14 at 16:08
  • The only reliable way to answer the question would be to measure the performance of the two functions with full optimizations, but I'm rather doubtful that the compiler will be able to optimize this out. As a purely anecdotal example, some recent code I've been working on calls `std::accumulate` on a `std::vector` and then calls a function that calls `std::accumulate` on the same `std::vector` again, and I saw a measurable performance increase when I passed the result of `accumulate` instead. – T.C. Jul 22 '14 at 16:23
  • I know performance measurement will tell what the compiler actually did, but not why, nor if there is any way of telling the compiler what to do. I am also doubtful, but regarding your example, I wonder what would happen with, say, a std::valarray instead of a std::vector – Bérenger Jul 22 '14 at 16:43

1 Answers1

0

If optimization for speed matters in this code, I would not rely on compiler behavior at all.

Even if a smart compiler spotted the trick (which I doubt here as this would involve a fair amount of semantic insight - making the functions inline could hint the compiler), you have no guarantee that another compiler will see it. Even a future version of the same!

It often arises that such numerical algorithms rely on reuse of intermediate results. I see no readability problem if you clearly comment that you keep a result for later. Code compactness does not always mean code readability.