4
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Chris Rackauckas Feb 8 '18 at 4:50
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – EternusVia Feb 8 '18 at 18:13

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.