{"id":371,"date":"2011-05-16T20:38:35","date_gmt":"2011-05-17T00:38:35","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2011\/05\/16\/automatic-array-growth-gets-a-lot-faster-in-r2011a\/"},"modified":"2019-10-29T16:36:41","modified_gmt":"2019-10-29T20:36:41","slug":"automatic-array-growth-gets-a-lot-faster-in-r2011a","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2011\/05\/16\/automatic-array-growth-gets-a-lot-faster-in-r2011a\/","title":{"rendered":"Automatic array growth gets a lot faster in R2011a"},"content":{"rendered":"
\r\n

One of the most significant MATLAB improvements in the R2011a release is in how certain kinds of array growth operations are\r\n handled. This is a kind of \"under-the-hood\" change that I think is exciting and deserves some publicity.\r\n <\/p>\r\n

For those of you who are MATLAB power users and understand preallocation and why it is necessary, I'll tell you the story's\r\n ending first: MATLAB R2011a performs much<\/b> better than previous MATLAB versions when performing repeated array growth in a loop.\r\n <\/p>\r\n

For everyone else, let's start with some not-so-hypothetical tech support questions:<\/p>\r\n

\r\n
    \r\n
  • \"Why is the MATLAB function foobar<\/tt> so slow?\"\r\n <\/li>\r\n
  • \"Why does MATLAB hang if I put a call to foobar<\/tt> in a loop?\"\r\n <\/li>\r\n
  • \"Why does the function foobar<\/tt> run so much faster at the command line than when I put it in a function?\"\r\n <\/li>\r\n <\/ul>\r\n <\/div>\r\n

    The tech support engineer will start digging into the question to see why the unhappy MATLAB user has reached his conclusion:<\/p>\r\n

    \"Well, I ran the profiler on my function flibbergibble<\/tt>, which calls foobar<\/tt>:\r\n <\/p>\r\n

    <\/p>\r\n

    \"You can see that foobar<\/tt> takes about 0.35 ms per call (70.93 \/ 200000), but when I call foobar<\/tt> 200000 times from the command line in a loop it only takes 8.5e-7 seconds per call:\r\n <\/p>

     tic, for k = 1:200000, foobar(k); end, toc\r\n Elapsed time is 0.173287 seconds.<\/pre>
    \"That's more than 400 times faster! Why is foobar<\/tt> so slow in a function?\"\r\n   <\/p>\r\n   
    Experienced MATLAB users know that the performance problem has little to do with foobar(k)<\/tt> on line 4 of the profile report and much to do with y(k) =<\/tt> on the same line.\r\n   <\/p>\r\n   
    Let's examine why. The first time through the loop, the variable y<\/tt> hasn't been assigned to yet, so MATLAB creates it through the assignment to y(1)<\/tt>. The second time through the loop assigns to y(2)<\/tt>, which doesn't exist yet. So MATLAB allocates enough new memory for two elements and then copies y(1)<\/tt> and assigns y(2)<\/tt> into the new space. The third time through the loop assigns to y(3)<\/tt>, which doesn't exist yet. So MATLAB allocates enough new memory for three elements and then copies y(1)<\/tt> and y(2)<\/tt> and assigns y(3)<\/tt> into the new space.\r\n   <\/p>\r\n   
    See the pattern? On the k-th time through the loop, MATLAB has to make a copy of k elements into newly allocated memory. The\r\n      time required to copy k elements is proportional to k. The time required to execute the entire loop is therefore proportional\r\n      to the sum of the integers from 1 to n, which is n*(n+1)\/2.\r\n   <\/p>\r\n   
    Bottom line: memory copying during the assignment statement causes the time required to execute the loop to be proportional\r\n      to n^2.\r\n   <\/p>\r\n   
    Let's see some data. I timed flibbergibble<\/tt> for various values of n<\/tt> using MATLAB R2010b. Here's the data:\r\n   <\/p>
    n = [100 200 500 1000 2000 10000 20000 40000 50000];\r\nt = [1.2e-4 2.7e-4 8.6e-4 2.4e-3 2.8e-3 5.8e-2 .24 1.32 2.4];\r\n\r\nplot(n,t)\r\ntitle('n versus t, MATLAB R2010b'<\/span>)<\/pre> 
    That looks pretty parabola-like. I checked it out with cftool<\/tt> from the Curve Fitting Toolbox and found that a rough fit to the data is the curve 1.0e-9 * n^2<\/tt>. What if we tried n = 1000000<\/tt>?  From our curve we could estimate that it would take about 17 minutes:\r\n   <\/p>
    n = 1e6;\r\nt_minutes = 1e-9 * n^2 \/ 60<\/pre>
    \r\nt_minutes =\r\n\r\n   16.6667\r\n\r\n<\/pre>
    This is what triggers the tech support call where the user thinks that the function foobar<\/tt> has caused MATLAB to hang. MATLAB isn't hung, it's just working really hard reallocating all that memory.\r\n   <\/p>\r\n   
    The solution is to preallocate<\/i> space for y<\/tt> before beginning the loop, like this:\r\n   <\/p>
    type flibbergibble2<\/span><\/pre>
    \r\nfunction y = flibbergibble2(n)\r\n\r\ny = zeros(1, n);\r\nfor k = 1:n\r\n    y(k) = foobar(k);\r\nend\r\n\r\n<\/pre>
    The code above does not have to reallocate any memory each time through the loop. In MATLAB R2010b on my computer it runs\r\n      in less than a second:\r\n   <\/p>
     tic, flibbergibble2(1000000); toc\r\n Elapsed time is 0.737451 seconds.<\/pre>
    The big change in MATLAB R2011a is that MATLAB uses a better strategy for reallocating memory as the array grows when it detects\r\n      this growth pattern. As a result, the time required to execute the loop grows only linearly with n.\r\n   <\/p>\r\n   
    Here's how it takes for n = 1000000<\/tt> in MATLAB R2011a on my computer:\r\n   <\/p>
     tic, flibbergibble(1000000); toc\r\n Elapsed time is 1.105256 seconds.<\/pre>
    That's in the neighborhood of a thousand times faster than R2010b. You can see that the preallocation strategy (in flibbergibble2<\/tt>) is still a bit faster, but the performance penalty for not preallocating has been substantially reduced.\r\n   <\/p>\r\n   
    If the final size of your output array is trivial to calculate, then I would say go ahead and preallocate. It's just one extra\r\n      code line and it's a little faster. But if the final size is complicated to calculate, then maybe you don't have to work as\r\n      hard you did before to optimize your code. If you are growing a vector, or if the array growth is in the final dimension of\r\n      a matrix or multidimensional array, you can now seriously consider just letting MATLAB do its own \"automatic array growth\"\r\n      thing.\r\n   <\/p>