What algorithm does Matlab use to dynamically resize vectors and matrices?
dynamic-arrays, matlab, matrix, memory-management
Solution
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.
Problem
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?