Simple Piece of Code for improvement

Hi. It is known that MATLAB works slow with for loop. I have tried to vectorize the following code without success. Perhaps I am wrong with the implementation.

    for I = NS2:-1:1
             A = 0;
             for J=1:8
                A = A + KS2(J,I)*FA(J);
             end
             S2 = S2 + ( SS2(1,I)*sin(A) + SS2(2,I)*cos(A) );
          end

where:

NS2 = 25

FA is a matrix 1x8

KS2 is a matrix 8x25

SS2 is a matrix 2x25

A is a scalar

S2 is a scalar

I try to improve it in this way:

    A = 0;
    J = 1:8;
    for I = NS2:-1:1

     A = FA(1,J)*KS2(J,I);

     S2 = S2 + ( SS2(1,I)*sin(A) + SS2(2,I)*cos(A) );
     end

However, the runtime for this improvement is similar to the original code.

[Fangjun Jiang]

Please see my comparison post. There is a solution without any for-loop and it is much faster.

Answer 1

[Fangjun Jiang]

I am amazed by Jan's insight. He seems to know without tic/toc.

t1=0;t2=0;t3=0;
for k=1:1000 % repeated run
    %common data
    FA=rand(1,8);KS2=rand(8,25);SS2=rand(2,25);
    NS2=25;S2=0;S4=0;
    %Original 
    tic;
    for I = NS2:-1:1
             A = 0;
             for J=1:8
                A = A + KS2(J,I)*FA(J);
             end
             S2 = S2 + ( SS2(1,I)*sin(A) + SS2(2,I)*cos(A) );
    end
    t1=t1+toc;
    %Fangjun's method 
    tic;
    A=FA*KS2;
    S3=sum(sum(SS2.*[sin(A);cos(A)]));
    t2=t2+toc;

      if abs(S3-S2)>1e-10,error('incorrect'),end
      %Jan's method
      tic;
      FAJ = FA(1, 1:8);
      KS2J = KS2(1:8, :);
      SS21 = SS2(1, :);
      SS22 = SS2(2, :);
      for I = NS2:-1:1
         A = FAJ * KS2J(:, I);
         S4 = S4 + (SS21(I) * sin(A) + SS22(I) * cos(A));
      end
      t3=t3+toc;

      if abs(S4-S2)>1e-10,error('incorrect'),end

end
fprintf('Original time: %f\n',t1);
fprintf('Fangjun''s time: %f\n',t2);
fprintf('Jan''s time: %f\n',t3);

Original time: 0.409646
Fangjun's time: 0.022221
Jan's time: 0.136472

[Jan]

Thanks, Fangjun. A nice counter-example for the "vectorization is not better than FOR loops" theory. +1

[Julián Francisco]

@Jan Simon: After seeing the Fangjun's results, it does appears that the vectorization is better than FOR loops theory (almost one order of magnitude).

Answer 2

[Jan]

Move the indexing out of the loop:

A = 0;
FAJ = FA(1, 1:8);
KS2J = KS2(1:8, :);
SS21 = SS2(1, :);
SS22 = SS2(2, :);
for I = NS2:-1:1
   A = FAJ * KS2J(:, I);
   S2 = S2 + (SS21(I) * sin(A) + SS22(I) * cos(A));
end

How much does this help?

In general "X(1:8)" is faster than "J=1:8; X(J)", because for the first case the boundaries are checked for the first and last element only.

[Sean de Wolski]

Interesting about the boundary checking!

[Julián Francisco]

@Jan Simon: What is the difference between writing KS2J = KS2(1:8,:) or KS2? I think you are using all elements of KS2 in both cases. My opinion is the same for FA.

[Jan]

@Julian: You are right, for this case KS2J is not very helpful at first sight. I've shown this for educational reasons only. The actual acceleration is coming from using "KS2J(:, I)" instead of "KS2(J, I)" and I've limited the 1st dimension of KS2J to allow to use the colon even if the original KS2 is larger.

Answer 3

[Fangjun Jiang]

See if the following gives correct result and fast speed.

A=FA*KS2;
S2=sum(sum(SS2.*[sin(A);cos(A)]));

[Fangjun Jiang]

Previously it missed the right ']'

Answer 4

[William]

To speed things up make an array of zeros

zeros( however big you need it)

then perform operation on each member of the array. So basically you want to allocate space for the loop prior to doing any operations.

[Julián Francisco]

@William: Thank you for your answer. I have forgot to mention the matrices and vectors were already allocated prior to for loops.