Variable appears to change size on every loop iteration - what?

When writing the following Matlab code:

for ii=1:n
    x(ii) = foo( ii ); % foo is some function of ii that cannot be vectorized.
end

I get the following m-lint warning:

The variable x appears to change size on every loop iteration

My question:

  1. What does that warning mean?
  2. Why is changing variable size every iteration is a bad thing?
  3. How can this problem be solved?

This question is not duplicate of this one, since it deals with more general aspects of preallocation, rather a specific instance of it.


Solution 1:

Well, first thing first.

1. What does this warning mean?

This code is correct in terms of syntax and it will execute correctly returning the expected result: the ii-th element of x will contain the value foo( ii ).
However, before this small piece of code runs, the variable x is not defined. Now, when the loop starts, x(1) is assigned the value foo( 1 ), and so Matlab creates x as a length-1 array. At the second iteration x(2) is assigned the value foo( 2 ) and so Matlab needs to change x to be of length 2, and so on: x changes its length/size at each iteration.

2. Why is changing variable size every iteration is a bad thing?

Consider what happens in the background (in terms of memory allocation) when x changes its size every iteration: At each iteration Matlab needs to find a free memory space to host the new size of x. If you are lucky, there is enough free space right after x so all that happens is a change to the amount of memory allocated to x and writing the new value at the right spot.
However, if there is not enough free space just after x, Matlab has to find a new spot for all the ii-1 elements already in x, allocate this new space for x, copy all ii-1 values already in x to the new spot, and free the old spot x used. This allocate-copy-free operations happening in the background can be extremely time consuming, especially when x is large.

3. How can this problem be solved?

The simplest solution is to pre-allocate all the space x needs before the loop:

x = zeros(1,n); 
for ii=1:n
    x( ii ) = foo( ii );
end

By pre-allocating we ascertain that x is allocated all the memory it requires up-front, thus no costly memory allocation/copy is needed when the loop is executing.

An alternative cool solution to the problem

If you are too lazy (like me) and don't want to pre-allocate you can simply:

for ii=n:-1:1
    x( ii ) = foo( ii );
end

This way, the first time x is assigned a value it is assigned to its n-th element (the last one) and therefore Matlab immediately allocates room for all n elements of x.
Cool!

Solution 2:

My answer is a bit late, but there are a few things I'd mention regarding array growth and pre-allocation in MATLAB.

The first thing to note is that MATLAB has improved automatic array growth performance a lot in recent versions, so the performance hit implied by the warning might not be too bad if you do it right (see below). Still, best practice is to pre-allocate your array (e.g. with zeros).

The Warning Explained

As of R2014a, the detailed explanation for the warning states the following:

The size of the indicated variable or array appears to be changing with each loop iteration. Commonly, this message appears because an array is growing by assignment or concatenation. Growing an array by assignment or concatenation can be expensive. For large arrays, MATLAB must allocate a new block of memory and copy the older array contents to the new array as it makes each assignment.

Programs that change the size of a variable in this way can spend most of their run time in this inefficient activity. ...

From this excerpt, it should be fairly clear why pre-allocation is a smart idea if you are at all concerned with performance.

Side note: There is limited information about the algorithm used for reallocation during array growth, but some information was provided on the same blog post by Steve Eddins, which I summarized in this previous answer.

Automatic Array Growth Optimization

If you want to use dynamic array resizing by growing along a dimension (without-preallocation), there are ways to do it right. See this this MathWorks blog post by Steve Eddins. The most important thing to note is that you should grow along the last dimension for best performance. This is not an issue in your case since the array is 1D. So, if you decide to let it ride, put %#ok<SAGROW> on the same line as the warning, after the culprit code, to silence the warning.

Yair discusses dynamic array resizing in another post on his blog. Also, there are ways of allocating an array without initializing using some hairy MEX API acrobatics, but that's it.

Pre-allocation

Pre-allocation is recommended. Get in the habit, learn to love zeros. If you are determined to squeeze every bit of performance out of MATLAB, Yair Altman has a couple of excellent articles on the topic of memory pre-allocation:

  • Preallocation performance
  • Preallocation performance and multithreading

Solution 3:

There is a lot of material out there on the subject. Here are a few selected links for more information:

Official documentation and technical solutions:

  • Techniques for Improving Performance: Preallocating Arrays
  • Strategies for Efficient Use of Memory: How to Avoid Fragmenting Memory
  • How do I pre-allocate memory when using MATLAB?

MathWorks Blogs:

  • Automatic array growth gets a lot faster in R2011a
  • More about automatic array growth improvements in MATLAB R2011a
  • Understanding Array Preallocation

Community Blogs:

  • Preallocation performance
  • Array resizing performance
  • Speed up your Code by Preallocating the size of Arrays, Cells, and Structures

Related Stack Overflow questions/answers:

  • Appending a vector to an empty MATLAB matrix
  • Matrix of unknown length in MATLAB?
  • What is the alternative to preallocating arrays in MATLAB?