Steve on Image Processing and MATLAB

Concepts, algorithms & MATLAB

More about automatic array growth improvements in MATLAB R2011a

Earlier this week I wrote about the improvements in automatic array growth in MATLAB R2011a. The posted comments made me realize that I should give a few more details so that you can understand all the circumstances under which this improvement might benefit you.

To illustrate the improvement with a slightly different code fragment than the for-loop I used the other day:

  y = [];
  while not_done_yet()
      if some_condition()
          y(end+1) = next_value();
      end
  end

We don't know in advance how big y is going to be, so it's harder to preallocate space for it. It would really be nice if I could just write the above code and let MATLAB handle all the boring details automatically efficiently.

Well, prior to R2011a, MATLAB would all handle all the boring details of array growth automatically but not efficiently. Now it also handles array growth efficiently.

Here are some more details you might find helpful.

  • Automatic array growth works best for vectors (of any orientation) or when growing along the last dimension of a multidimensional array.
  • Automatic array growth works for all numeric types as well as cell arrays and object arrays.
  • The optimization also helps when you are adding a large number of fields to a struct.

Also, for numeric array types, certain kinds of growth by concatenation are supported. Specifically, the case where a numeric array is concatenated with itself is now optimized:

   x = [];
   for k = 1:n
       x = [x k];
   end

One blog reader wondered if this optimization means that there might be situations where some very large vectors or arrays might be using twice as memory as necessary.

The answer is no, not really. MATLAB uses a smarter heuristic than simply doubling the allocated memory space whenever more is needed, so for large arrays the worst-case memory "overallocation" is much less than a factor of two. I don't intend to get into further details here because (a) I don't know them, and (b) I expect that we will continue to tune the heuristic and other aspects of automatic array growth with future releases.

I'll conclude by repeating my recommendation from earlier this week. If it's trivial to precalculate the final size of a growing array before entering a loop, then by all means use preallocation. It's the fastest way to go. But if it's not trivial, and if the pattern of growth matches one of the cases described above, then you can consider just letting MATLAB handle the array growth for you without worrying about bad performance scaling.




Published with MATLAB® 7.12

|

Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.