# MATLAB Matrix Multiply Efficiency

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.

• I wouldn't trust timings that come out of MATLAB. There's many other things involved that make its timings not indicative of well-optimized C code. – Chris Rackauckas Feb 8 '18 at 4:50

## 2 Answers

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.)

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.

• The weird thing is that the C accesses should be contiguous in memory, just like the accesses of tempcol. But yeah, I would guess it has something to do with that, just not sure exactly how it works. – EternusVia Feb 8 '18 at 18:13