What algorithm does Matlab use to dynamically resize vectors and matrices?

Question

Running this code:

n = 5;
x = zeros(n, 1);
for ix=1:10
   x(ix) = rand();
   disp(getfield(whos('x'), 'bytes'))
end

outputs this:

40
40
40
40
40
48
56
64
72
80

which seems to indicate that when Matlab resizes a vector, it resizes it to have exactly as much space as it needs, no more. So, one element at a time.

Contrast this with the method in Sun's Java implementation of ArrayList, which allocates enough space so that every resizing won't need to happen on every assignment above the initial bound. Obviously since Matlab isn't open source there's no way to tell 100% what they do, but is there a better way to get some idea of how the resizing is done? Is the code above not a good way to estimate this?

Answer 1

From MathWorks' software development manager Steve Eddins:

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.

So, it is safe to say it does not allocate space for one element at a time, but overallocates to some degree. Also, as noted by Alexandre Bizeau, the memory will be contiguous.

Also, see this page for an array grown performance analysis.

Answer 2

When you assign a numeric or character array to a variable, MATLAB allocates a contiguous virtual block of memory and stores the array data in that block. MATLAB also stores information about the array data, such as its class and dimensions, in a separate, small block of memory called a header.

If you add new elements to an existing array, MATLAB expands the existing array in memory in a way that keeps its storage contiguous. This usually requires finding a new block of memory large enough to hold the expanded array. MATLAB then copies the contents of the array from its original location to this new block in memory, adds the new elements to the array in this block, and frees up the original array location in memory.

Source : Creating and Modifying Arrays