Code to multiply matrices together I've got a short algorithm used in my code to multiply two matrices and put them into a destination Matrix. I decided to use the temporary array t_elements, which allows the user to make one of the input matrices the output matrix as well. 

Usually I like to save optimization for later, but this code is going to be called often, so I was wondering if anyone could suggest ways to make it faster. 

#include &lt;vector&gt;

struct Matrix{
    std::vector&lt;std::vector&lt;float&gt;&gt; elements;
    int height;
    int width;

    Matrix(int w, int h)
    {
        width = w;
        height = h;

        for (int i = 0; i &lt; height; i++) {
            elements.push_back(std::vector&lt;float&gt;());

            for (int j = 0; j &lt; width; j++) {
                elements[i].emplace_back(0.0f);
            }
        }
    }

    float get_element(int x, int y) const { return elements[y][x]; }

    void set_element(int x, int y, float value) { elements[y][x] = value; }
};

void dot(Matrix const&amp; left, Matrix const&amp; right, Matrix&amp; dest)
{
    float t_elements[right.width][left.height];

    for (int i = 0; i &lt; left.height; i++) {
        for (int j = 0; j &lt; right.width; j++) {
            float elementVal = 0;

            for (int k = 0; k &lt; left.width; k++)
                elementVal += (left.get_element(k, i) * right.get_element(j, k));

            t_elements[j][i] = elementVal;
        }
    }

    for (int i = 0; i &lt; dest.width; i++)
        for (int j = 0; j &lt; dest.height; j++)
            dest.set_element(i, j, t_elements[i][j]);
}

int main()
{
    Matrix m1 = Matrix(3,3);
    Matrix m2 = Matrix(3,3);
    Matrix m3 = Matrix(3,3);

    dot(m1, m2, m3);

    return 0;
}
Both of the other answers make some very good points, especially when it comes to replacing vector. Two dimensional vectors are particularly iffy because the whole lump of memory will not be contiguous. If you access elements[y][x] you first have to look in elements[y] for the address of the inner vector, and then have to look into that inner vector. By contrast if you have an array that is say, 4x4, the compiler would typically internally have a single 1D array of length 16. Then to get elements[2][2] it might just grab the entry in offset 11 (i.e. 2*4+3)

There are (at least) three distinct performance advantages associated with this when you think about low level hardware. 


You don't waste time chasing pointers to find which bit of memory you need.
Having the values that you're working with all be close together gives you nice cache locality. 
This simplifies the code within the key loops, giving the compiler a better chance of automatically vectorizing your code.




Snowbody mentions templating your Matrix so that you could have different primitive types in it (A matrix of ints or of doubles or whatever). I would further suggest templating your matrix to specify the sizes. Comparing with how std::array is done, where you might have std::array&lt;int, 3&gt;;, you could have matrix&lt;float, 3, 3&gt;. (In fact it would be necessary if you wanted your internal data storage to be a std::array as vnp suggests.)

This again gives the compiler more guarantees about your program ahead of time, which again means it has a better chance of doing helpful optimisations. For example a classic optimisation that compilers might do is "Loop unrolling", whereby they actually rewrite 

for (int i = 0; i &lt; 3; ++i) {
    doSomething();
}


as 

doSomething();
doSomething();
doSomething();


They can do this because they know ahead of time how many iterations of the loop to expect, and calculate whether duplicating the machine code is justified by getting rid of the loop overhead. 

As well as probably helping performance, this opens the door to writing compile time checks for your program. For example you could get the compiler to stop you from accidentally adding a 4x4 matrix to a 2x2 matrix, just like it would stop you from adding a double and a string.

Finally, because this information is known at compile time it does not need to be stored or accessed during the running of the program. Instead of i &lt; dest.width the compiler would be writing machine code for i &lt; 3. (But, importantly, you would still not have to write i &lt; 3 which is inflexible and harder to understand than width.)



Modern optimisers have their own cost models to decide when to inline methods, but sensible hints still wouldn't go amiss. I'd suggest that get_element and set_element are particularly good candidates for inlining. 

I actually disagree with vnp about directly accessing elements, although I do agree that the current getter and setter aren't any better. The advantages of using such methods are that they give you opportunity to


add precondition and postcondition checks, such as requiring that the indices are within bounds.
mess with the internal representation, such as the aforementioned storing your data in a 1D array and directly indexing it as if it was a 2D one. (If for some reason you didn't trust the compiler to do that indexing for you.) 




Note that 

float t_elements[right.width][left.height];


Is not legal c++, because c++ requires that array size (for stack arrays) must be a constant expression. You do have the option of using new, in which case you must remember to delete[] 



I would also suggest, though this strays away from performance questions, that doing some error checking would be sensible. If you don't want to include sizes in the templates as above, it's still worth a basic check that you're not multiplying a 2x5 matrix by a 3x4 one.



Please note that all of the above is based on some theoretical understanding of the sorts of machine code that compilers can write. It is not based on empirical profiling of your code with a representative set of test data, which should be your first move when looking to optimise anything. (Closely followed of course by questioning whether there might be a suitable third party library that has already done all the hard work for you.)