{"id":3972,"date":"2021-02-24T11:09:31","date_gmt":"2021-02-24T16:09:31","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=3972"},"modified":"2021-03-16T10:21:58","modified_gmt":"2021-03-16T14:21:58","slug":"once-and-for-all","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2021\/02\/24\/once-and-for-all\/","title":{"rendered":"Once and for All"},"content":{"rendered":"
\r\n
I was talking to my long-time colleague, Mike Croucher, who joined MathWorks team recently (yay!). About a bunch of interesting topics, some of which could be good fodder for a blog post. Today I want to talk about for<\/a>-loops.<\/div>\r\n
\r\n
Table of Contents<\/span><\/div>\r\n
Nested Loops\r\n<\/a>Straight-forward Loop Solution, Inner Loop Rows\r\n<\/a>Straight-forward Loop Solution, Inner Loop Columns\r\n<\/a>Vectorized Solution\r\n<\/a>Analysis\r\n<\/a>Order Matters\r\n<\/a>Your Thoughts?<\/a><\/div>\r\n<\/div>\r\n
<\/div>\r\n

Nested Loops<\/h2>\r\n
In my old Fortran programming days (yes, long gone), I learned early on that my code ran faster if I arranged my nested for-<\/span>loops optimally. In Fortran, if I were computing one element at a time in a matrix, it meant making sure I filled the elements sequentially, which meant looping over each row, 1 column at a time, because that's the way Fortran (and MATLAB) stores arrays. This is not how arrays are stored in C.<\/div>\r\n
I was curious what happens in MATLAB today if I try to run nested loops in different orders. So let's see!<\/div>\r\n
\r\n\r\nLet's compute\r\n\r\nAr,c\u2009=r*(r+c3)+17 \r\n\r\n<\/div>\r\n

Straight-forward Loop Solution, Inner Loop Rows<\/h2>\r\n
Of course I preallocate my output array, Ar<\/span>.<\/div>\r\n
\r\n
\r\n
t = zeros(1,3);<\/span><\/div>\r\n<\/div>\r\n
\r\n
n = 1000;<\/span><\/div>\r\n<\/div>\r\n
\r\n
tic;<\/span><\/div>\r\n<\/div>\r\n
\r\n
Ar = zeros(n,n);<\/span><\/div>\r\n<\/div>\r\n
\r\n
[nrows,ncolumns] = size(Ar);<\/span><\/div>\r\n<\/div>\r\n
\r\n
for <\/span>rows = 1:nrows<\/span><\/div>\r\n<\/div>\r\n
\r\n
for <\/span>columns = 1:ncolumns<\/span><\/div>\r\n<\/div>\r\n
\r\n
Ar(rows,columns) = rows*(rows+columns^3)+17;<\/span><\/div>\r\n<\/div>\r\n
\r\n
end<\/span><\/span><\/div>\r\n<\/div>\r\n
\r\n
end<\/span><\/span><\/div>\r\n<\/div>\r\n
\r\n
t(1) = toc;<\/span><\/div>\r\n<\/div>\r\n
\r\n
<\/div>\r\n<\/div>\r\n<\/div>\r\n

Straight-forward Loop Solution, Inner Loop Columns<\/h2>\r\n
And now the other order.<\/div>\r\n
\r\n
\r\n
tic;<\/span><\/div>\r\n<\/div>\r\n
\r\n
Ac = zeros(n,n);<\/span><\/div>\r\n<\/div>\r\n
\r\n
[nrows,ncolumns] = size(Ac);<\/span><\/div>\r\n<\/div>\r\n
\r\n
for <\/span>columns = 1:ncolumns<\/span><\/div>\r\n<\/div>\r\n
\r\n
for <\/span>rows = 1:nrows<\/span><\/div>\r\n<\/div>\r\n
\r\n
Ac(rows,columns) = rows*(rows+columns^3)+17;<\/span><\/div>\r\n<\/div>\r\n
\r\n
end<\/span><\/span><\/div>\r\n<\/div>\r\n
\r\n
end<\/span><\/span><\/div>\r\n<\/div>\r\n
\r\n
t(2) = toc;<\/span><\/div>\r\n<\/div>\r\n<\/div>\r\n

Vectorized Solution<\/h2>\r\n
And, of course, the vectorized version.<\/div>\r\n
\r\n
\r\n
tic;<\/span><\/div>\r\n<\/div>\r\n
\r\n
tmpr = (1:nrows).';<\/span><\/div>\r\n<\/div>\r\n
\r\n
Av = tmpr .* (tmpr+(1:ncolumns).^3) + 17;<\/span><\/div>\r\n<\/div>\r\n
\r\n
t(3) = toc;<\/span><\/div>\r\n<\/div>\r\n<\/div>\r\n

Analysis<\/h2>\r\n
Let's make sure they also produce the same results.<\/div>\r\n
\r\n
\r\n
areAnswerEqual = isequal(Ac,Ar,Av)<\/span><\/div>\r\n
\r\n
\r\n
\r\n
areAnswerEqual = logical<\/span><\/span><\/div>\r\n
1<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n
And what about the execution times?<\/div>\r\n
\r\n
\r\n
t<\/span><\/div>\r\n
\r\n
\r\n
\r\n
\r\n
t = <\/span>1\u00d73<\/span><\/div>\r\n<\/div>\r\n
\r\n
0.1236 0.0190 0.0082<\/div>\r\n
<\/div>\r\n
<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n

Order Matters<\/h2>\r\n
In MATLAB, using nested for<\/span>-loops, clearly the order of the loops matters from a timing perspective. So it would be wise to order them knowing that the data is stored column by column, if you can write your algorithm that way. And I did not show what the effects might be if we didn't preallocate the output matrices. You can try that for yourselves.<\/div>\r\n
Despite getting a pretty good speedup by wrangling the nested loops, it's still often preferable, from a speed standpoint, to try to vectorize the code. Notice that I am using implicit expansion<\/a> to compute Av<\/span>. Also note that you won't always get the same ratio of speed difference between loops and the equivalent vectorized version - it will depend very much on how much work is going on for each computation and how much overhead arises.<\/div>\r\n

Your Thoughts?<\/h2>\r\n
When using loops in MATLAB, from a speed viewpoint, it's best if you can set up the loops so the elements are accessed as close to sequentially as possible. You can see from the small example above that running down the columns gives superior performance vs. running across the rows. This is because of the way MATLAB stores arrays.<\/div>\r\n
Have you run into a situation where reordering loops helped you out? Let us know here<\/a>.<\/div>\r\n
<\/div>\r\n
Copyright 2021 The MathWorks, Inc.<\/span><\/div>\r\n<\/div>\r\n