MATLAB Matrix Multiply Efficiency

Question

I am using MATLAB to prototype a few matrix multiply techniques and compare efficiency. Eventually, I will move the prototype codes to C. It is for a homework assignment where we need to write an efficient matrix multiply routine (by being aware of cache size, locality, etc.).

I am curious about the efficiency differences between these two very similar loops:

Matrix Multiply Loop 1 - sum over columns of A times elements of B -> column of C

function [C] = dgemm_naivepe( A,B,C,n )

for j=1:n
    tempcol=zeros(n,1);
    for k=1:n
        for i=1:n
            tempcol(i)=tempcol(i)+A(i+(k-1)*n)*B(k+(j-1)*n);
        end
    end
    for k=1:n
        C(k+(j-1)*n)=tempcol(k);
    end
end

end

Matrix Multiply Loop 2 - sum over columns of A times elements of B -> column of C

function [C] = dgemm_naivepe( A,B,C,n )

for j=1:n
    for k=1:n
        for i=1:n
            C(i+(j-1)*n)=C(i+(j-1)*n)+A(i+(k-1)*n)*B(k+(j-1)*n);
        end
    end
end

end

After several test runs of various matrix sizes, I found that Loop 1 is faster than Loop 2. Could someone help me understand why this is?

PS: I posted this on a general coding stack exchange but didn't get much of a response, so I figured I could post it here as well.

Answer 1

Your loop 2 does not preallocate $C$. Hence it gets resized $n$ times, which requires many reallocations. Try adding C = zeros(n, n) before the for loops.

[EDIT: so does the first one, so probably this isn't the true reason.]

(That said, I second ChrisRackauckas's comment --- there is little point in testing timings under Matlab at this level.)

Answer 2

Maybe the size of C vs the size of tempcol is what is making the difference?
If it is pulling the C matrix into cache it has to make more room than for tempcol, possibly removing data from A and/or B which wouldn't have been removed for the smaller tempcol.