Efficient functional style (C++11 ok)

Question

Lets say I have the following:

struct point
{
  double x;
  double y;
  double z;
};

I can write the following:

void point_mult(point& p, double c) { p.x *= c; p.y *= c; p.z *= c; }
void point_add(point& p, const point& p2) { p.x += p2.x; p.y += p2.y; p.z += p2.z; }

So I can then do the following:

point p{1,2,3};
point_mult(p, 2);
point_add(p, point{4,5,6});

This requires no copies of point, and only two constructions, namely the construction of point{1,2,3} and the construction of point{4,5,6}. I believe this applies even if point_add, point_mult and point{...} are in separate compilation units (i.e. can't be inlined).

However, I'd like to write code in a more functional style like this:

point p = point_add(point_mult(point{1,2,3}, 2), point{4,5,6});

How can I write point_mult and point_add such that no copies are required (even if point_mult and point_add are in separate compilation units), or is functional style forced to be not as efficient in C++?

Answer 1

Let's ignore the implicit fallacy of the question (namely that copying automatically means reduced efficiency). And let's also ignore the question of whether any copying would actually happen, or whether it would all be elided away by any half-decent compiler. Let's just take it on face value: can this be done without copying?

Yes, and it is probably the only other legitimate use for r-value references (though the previously ignored stipulations make this use case dubious):

point &&point_mult(point &&p, double c);

Of course, this will only bind to temporaries. So you would need an alternate version for l-values:

point &point_mult(point &p, double c);

The point is that you pass the references through as they are, either as references to temporaries or references to l-values.

Answer 2

It can be done with really ugly template metaprogramming. For example eigen uses templates so that expressions like matrix1 + matrix2 * matrix3 don't need to create any temporaries. The gist of how it works is the + and * operators for matrices don't return Matrix objects but instead return some kind of matrix expression object which is templatized on the types of the expression paramaters. This matrix expression object can then compute parts of the expression only when they are needed instead of creating temporary objects to store the result of subexpressions.

Actually implementing this can get quite messy. Have a look at Eigen's source if your interested. Boost's uBlas also does something similar, though it's not as extensively as eigen.

Answer 3

An efficient (and generalized) technique is expression templates. You can read a nice introductory explanation here.

It's difficult to implement and being based on templates, you cannot use separate compilation units, but it's very efficient. An interesting application in symbolic computation is parsing: Boost.Spirit builds very efficient parsers out of them.

C++11 auto keywords helps usage on practical programming tasks, as always when dealing with complex types, see this other answer.

Answer 4

First, why not use "better" functions ?

struct Point {
  double x;
  double y;
  double z;

  Point& operator+=(Point const& right) {
    x += right.x; y += right.y; z += right.z;
    return *this;
  }

  Point& operator*=(double f) {
    x *= f; y *= f; z *= f;
    return *this;
  }
};

Now it can be used as:

Point p = ((Point{1,2,3} *= 2) += Point{4,5,6});

But I truly think that you worry too much about copies here (and performance).

1. Make it work
2. Make it fast

If you don't have anything that already works, talking about performance is akin to chasing mills... bottlenecks are rarely where we thought they would be.

Answer 5

Change the definition of point_mult() to:

point& point_mult(point& p, double c) { p.x *= c; p.y *= c; p.z *= c; return p; }
^^^^^^                                                                ^^^^^^^^^

And call it as:

point & p = point_add(point_mult(*new point{1,2,3}, 2), point{4,5,6});
     ^^^                         ^^^^^

there is no copy involved. However, you have to later do delete &p; for releasing the memory.