4

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?

Community
  • 1
  • 1
Michael A
  • 4,391
  • 8
  • 34
  • 61
  • I'm pretty sure your conclusions are correct: there's no fancy algorithm whatsoever, MATLAB only allocates as much as needed for an array. MATLAB is simply not designed for `append` operations on arrays/lists. – sebastian Sep 27 '13 at 22:22
  • 1
    True that preallocation is the recommended approach, but see my answer regarding the algorithm. It has seemingly gotten more intelligent. – chappjc Sep 27 '13 at 22:31

2 Answers2

6

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.

chappjc
  • 30,359
  • 6
  • 75
  • 132
4

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

Vuwox
  • 2,331
  • 18
  • 33