for-loop order

I am wondering whether the order of for-loop affects the speed. For example, I am running multiple for-loops and they have different number of elements.

for i=1:n
  for j=1:m
     for  k=1:p
        ....

       end
     end
  end

In this case, is it better to place the loop with the smallest number into the outer loop ? or doesn't it matter?

[dpb]

The loops themselves don't matter; what does matter (and can be huge impact for large arrays) is to address data in column major order to avoid cache misses by addressing elements in sequential order. This implies advancing leftmost subscripts first.

Answer 1

[James Tursa]

For the m-code loop itself it probably doesn't matter since the total number of iterations is the same. The stuff inside the for loops can easily dominate the run-time so it may be a moot point. But for memory access, it is often good practice to transverse an array in memory order to take advantage of memory caching. E.g.,

A = some MxN matrix
for i=1:M
    for j=1:N
        % some stuff involving A(i,j) here
    end
end

The above does not access the elements of A in linear order since A is stored in column order. So the memory access pattern for A jumps around in memory.

A = some MxN matrix
for j=1:N
    for i=1:M
        % some stuff involving A(i,j) here
    end
end

The above does access A in linear order in memory, so it would take better advantage of the memory cache.

All that being said, the m-code for-loop stuff and what you are doing inside the for-loops may easily dominate the A memory access times so in practice you may not see much difference between the two.

E.g., take this code

A = rand(5000);
disp('Access jumping around in memory');
tic
for i=1:5000
    for j=1:5000
        A(i,j);
    end
end
toc
disp('Access in linear order');
tic
for j=1:5000
    for i=1:5000
        A(i,j);
    end
end
toc

And run it:

Access jumping around in memory
Elapsed time is 1.542680 seconds.
Access in linear order
Elapsed time is 0.802103 seconds.

[icdi]

Thanks a lot for your detailed explanation.