How to prevent creating intermediate objects in cascading operators?

Question

I use a custom Matrix class in my application, and I frequently add multiple matrices:

Matrix result = a + b + c + d; // a, b, c and d are also Matrices

However, this creates an intermediate matrix for each addition operation. Since this is simple addition, it is possible to avoid the intermediate objects and create the result by adding the elements of all 4 matrices at once. How can I accomplish this?

NOTE: I know I can define multiple functions like Add3Matrices(a, b, c), Add4Matrices(a, b, c, d), etc. but I want to keep the elegancy of result = a + b + c + d.

Answer 1

It is not possible, using operators.

Answer 2

In C++ it is possible to use Template Metaprograms and also here, using templates to do exactly this. However, the template programing is non-trivial. I don't know if a similar technique is available in C#, quite possibly not.

This technique, in c++ does exactly what you want. The disadvantage is that if something is not quite right then the compiler error messages tend to run to several pages and are almost impossible to decipher.

Without such techniques I suspect you are limited to functions such as Add3Matrices.

But for C# this link might be exactly what you need: Efficient Matrix Programming in C# although it seems to work slightly differently to C++ template expressions.

Answer 3

Something that would at least avoid the pain of

Matrix Add3Matrices(a,b,c) //and so on

would be

Matrix AddMatrices(Matrix[] matrices)

Answer 4

You can't avoid creating intermediate objects.

However, you can use expression templates as described here to minimise them and do fancy lazy evaluation of the templates.

At the simplest level, the expression template could be an object that stores references to several matrices and calls an appropriate function like Add3Matrices() upon assignment. At the most advanced level, the expression templates will do things like calculate the minimum amount of information in a lazy fashion upon request.

Answer 5

You could limit yourself to a single small intermediate by using lazy evaluation. Something like

public class LazyMatrix
{
    public static implicit operator Matrix(LazyMatrix l)
    {
        Matrix m = new Matrix();
        foreach (Matrix x in l.Pending)
        {
            for (int i = 0; i < 2; ++i)
                for (int j = 0; j < 2; ++j)
                    m.Contents[i, j] += x.Contents[i, j];
        }

        return m;
    }

    public List<Matrix> Pending = new List<Matrix>();
}

public class Matrix
{
    public int[,] Contents = { { 0, 0 }, { 0, 0 } };

    public static LazyMatrix operator+(Matrix a, Matrix b)
    {
        LazyMatrix l = new LazyMatrix();
        l.Pending.Add(a);
        l.Pending.Add(b);
        return l;
    }

    public static LazyMatrix operator+(Matrix a, LazyMatrix b)
    {
        b.Pending.Add(a);
        return b;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Matrix a = new Matrix();
        Matrix b = new Matrix();
        Matrix c = new Matrix();
        Matrix d = new Matrix();

        a.Contents[0, 0] = 1;
        b.Contents[1, 0] = 4;
        c.Contents[0, 1] = 9;
        d.Contents[1, 1] = 16;

        Matrix m = a + b + c + d;

        for (int i = 0; i < 2; ++i)
        {
            for (int j = 0; j < 2; ++j)
            {
                System.Console.Write(m.Contents[i, j]);
                System.Console.Write("  ");
            }
            System.Console.WriteLine();
        }

        System.Console.ReadLine();
    }
}

Answer 6

This is not the cleanest solution, but if you know the evaluation order, you could do something like this:

result = MatrixAdditionCollector() << a + b + c + d

(or the same thing with different names). The MatrixCollector then implements + as +=, that is, starts with a 0-matrix of undefined size, takes a size once the first + is evaluated and adds everything together (or, copies the first matrix). This reduces the amount of intermediate objects to 1 (or even 0, if you implement assignment in a good way, because the MatrixCollector might be/contain the result immediately.)
I am not entirely sure if this is ugly as hell or one of the nicer hacks one might do. A certain advantage is that it is kind of obvious what's happening.

Answer 7

My first solution would be something along this lines (to add in the Matrix class if possible) :

static Matrix AddMatrices(Matrix[] lMatrices) // or List<Matrix> lMatrices
{
    // Check consistency of matrices

    Matrix m = new Matrix(n, p);

    for (int i = 0; i < n; i++)
     for (int j = 0; j < n; j++)
      foreach (Maxtrix mat in lMatrices)
       m[i, j] += mat[i, j];

    return m;
}

I'd had it in the Matrix class because you can rely on the private methods and properties that could be usefull for your function in case the implementation of the matrix change (linked list of non empty nodes instead of a big double array, for example).

Of course, you would loose the elegance of result = a + b + c + d. But you would have something along the lines of result = Matrix.AddMatrices(new Matrix[] { a, b, c, d });.

Answer 8

I thought that you could just make the desired add-in-place behavior explicit:

Matrix result = a;
result += b;
result += c;
result += d;

But as pointed out by Doug in the Comments on this post, this code is treated by the compiler as if I had written:

Matrix result = a;
result = result + b;
result = result + c;
result = result + d;

so temporaries are still created.

I'd just delete this answer, but it seems others might have the same misconception, so consider this a counter example.

Answer 9

Might I suggest a MatrixAdder that behaves much like a StringBuilder. You add matrixes to the MatrixAdder and then call a ToMatrix() method that would do the additions for you in a lazy implementation. This would get you the result you want, could be expandable to any sort of LazyEvaluation, but also wouldn't introduce any clever implementations that could confuse other maintainers of the code.

Answer 10

Bjarne Stroustrup has a short paper called Abstraction, libraries, and efficiency in C++ where he mentions techniques used to achieve what you're looking for. Specifically, he mentions the library Blitz++, a library for scientific calculations that also has efficient operations for matrices, along with some other interesting libraries. Also, I recommend reading a conversation with Bjarne Stroustrup on artima.com on that subject.

Answer 11

There are several ways to implement lazy evaluation to achieve that. But its important to remember that not always your compiler will be able to get the best code of all of them.

I already made implementations that worked great in GCC and even superceeded the performance of the traditional several For unreadable code because they lead the compiler to observe that there were no aliases between the data segments (somethign hard to grasp with arrays coming of nowhere). But some of those were a complete fail at MSVC and vice versa on other implementations. Unfortunately those are too long to post here (don't think several thousands lines of code fit here).

A very complex library with great embedded knowledge int he area is Blitz++ library for scientific computation.