Operator + for matrices in C++

Question

I suppose the naive implementation of a + operator for matrices (2D for instance) in C++ would be:

class Matrix {

  Matrix operator+ (const Matrix & other) const {
      Matrix result;
      // fill result with *this.data plus other.data
      return result;
  }
}

so we could use it like

Matrix a;
Matrix b;
Matrix c;

c = a + b;

Right?

But if matrices are big this is not efficient as we are doing one not-necessary copy (return result).

Therefore, If we wan't to be efficient we have to forget the clean call:

c = a + b;

Right?

What would you suggest / prefer ? Thanks.

Answer 1

The C++ standard gives permission for the compiler to elide the unnecessary copy in this case (it's called the "named return value optimization", usually abbreviated to NRVO). There's a matching "RVO" for when you return a temporary instead of a named variable.

Nearly all reasonably recent C++ compilers implement both NRVO and RVO, so generally speaking you can ignore the fact that this construct wouldn't otherwise be particularly efficient.

Edit: I was, of course, talking about the copy involved in returning the new matrix holding the result of the addition. You probably do want to either pass the input by const reference:

Matrix operator+(Matrix const &other) const { 
    Matrix result;
    // ...
    return result;
}

...or else, pass by value, but return the passed value:

Matrix operator+(Matrix other) const { 
    other += *this;
    return other;
}

Note that this depends on commutativity though (i.e., it's really doing b+a instead of a+b) so while it's fine for addition, it won't work for some other operations.

Answer 2

You can return a value without triggering a copy construction. Its called R-Value references Explained in a bit of detail here http://www.artima.com/cppsource/rvalue.html

Answer 3

Two ways to solve it.

1) Use references:

Matrix& operator+ (Matrix& other) const {

2) Use shallow copy in copy constructor. Yes, new Matrix object will be created but the real matrix will not be created again

Answer 4

I would try to construct the Matrix at the return statement:

Matrix Matrix::operator + (const Matrix& M)
{
    return Matrix(
        // 16 parameters defining the 4x4 matrix here
        // e.g. m00 + M.m00, m01 + M.m01, ...
    );
}

That way you won't be using any temporaries.

Answer 5

As others have pointed out, your implementation isn't as expensive as you think. However, it may make some sense to define additional methods that modify the object in-place for use in critical inner loops.

EDIT - fixed following paragraph

The point here is that even with return value optimisations, you still end up constructing a local variable and then assigning that to the result variable after operator+ exits. And destructing that extra object, of course. There is still an extra object used to temporarily hold the result. It's possible to do reference-counting with copy-on-write, but that adds a dereferencing overhead to each use of a matrix.

These are non-issues for 99% of cases, but once in a while you get a critical case. If you were dealing with large matrices, reference-counting overheads would be insignificant - but for 2D up to 4D there are times when you may care a great deal about those few extra cycles - or more to the point, about not putting the matrix on the heap when you want it on the stack or embedded within some struct/class/array.

That said - in those cases, you probably won't be writing your own matrix code - you'll just use the matrix ops from DirectX or OpenGL or whatever.

Answer 6

class Matrix { 

  Matrix & operator+=(const Matrix & other) {
      // fill result with *this.data plus other.data 
      // elements += other elements 
      return *this;
  }
  Matrix operator+ (const Matrix & other) {
      Matrix result = *this; 
      return result += other; 
  } 
} 

Answer 7

If you're really concerned about performance (have you profiled?) you probably shouldn't implement operator+ at all since you can't control if it will result in a non-optimal temporary being created. Just implement operator+= and/or member function add(Matrix& result, const Matrix& in1, const Matrix& in2) and let your clients create the correct temporaries.

If you do want operator+ either of Jerry Coffin's will work fine.

Answer 8

Note that your first naive implementation is very native, as nothing is passed by reference. I'll assume this was a really naive example and that there is no need to remind readers of the benefits of passing by-reference instead of by-value.

Note, too, that I have used the non-member-function operators, instead of the member-functions, but in the end, the results are (almost) the same.

If you want to be sure no necessary copy will be created, you should try a non-operator version:

void add(Matrix & result, const Matrix & lhs, const Matrix & rhs) ;

If you want to do it the operator way (which is my prefered solution), then you should assume operator + will create a temporary. You should then define both operator + and operator += :

Matrix & operator += (Matrix & result, const Matrix & rhs) ;
{
   // add rhs to result, and return result
   return result ;
}

Matrix operator + (const Matrix & lhs, const Matrix & rhs) ;
{
   Matrix result(lhs) ;
   result += rhs ;
   return result ;
}

Now, you could try to "leverage" compiler optimisations and write it as:

Matrix & operator += (Matrix & result, const Matrix & rhs) ;
{
   // add rhs to result, and return result
   return result ;
}

Matrix operator + (Matrix lhs, const Matrix & rhs)
{
   return lhs += rhs ;
}

As proposed by Herb Sutter in C++ Coding Standards, 27. Prefer the canonical forms of arithmetic and assignment operators, p48-49:

A variation is to have operator @ [@ being +, -, whatever] accept its first parameter by value. This way, you arrange for the compiler itself to perform the copy for you implicitely, and this can give the compiler more leeway in applying optimizations.