MATLAB Language Performance and Benchmarking The importance of preallocation
Example
Arrays in MATLAB are held as continuous blocks in memory, allocated and released automatically by MATLAB. MATLAB hides memory management operations such as resizing of an array behind easy to use syntax:
a = 1:4
a =
1 2 3 4
a(5) = 10 % or alternatively a = [a, 10]
a =
1 2 3 4 10
It is important to understand that the above is not a trivial operation, a(5) = 10 will cause MATLAB to allocate a new block of memory of size 5, copy the first 4 numbers over, and set the 5'th to 10. That's a O(numel(a)) operation, and not O(1).
Consider the following:
clear all
n=12345678;
a=0;
tic
for i = 2:n
a(i) = sqrt(a(i-1)) + i;
end
toc
Elapsed time is 3.004213 seconds.
a is reallocated n times in this loop (excluding some optimizations undertaken by MATLAB)! Note that MATLAB gives us a warning:
"The variable 'a' appears to change size on every loop iteration. Consider preallocating for speed."
What happens when we preallocate?
a=zeros(1,n);
tic
for i = 2:n
a(i) = sqrt(a(i-1)) + i;
end
toc
Elapsed time is 0.410531 seconds.
We can see the runtime is reduced by an order of magnitude.
Methods for preallocation:
MATLAB provides various functions for allocation of vectors and matrices, depending on the specific requirements of the user. These include: zeros, ones, nan, eye, true etc.
a = zeros(3) % Allocates a 3-by-3 matrix initialized to 0
a =
0 0 0
0 0 0
0 0 0
a = zeros(3, 2) % Allocates a 3-by-2 matrix initialized to 0
a =
0 0
0 0
0 0
a = ones(2, 3, 2) % Allocates a 3 dimensional array (2-by-3-by-2) initialized to 1
a(:,:,1) =
1 1 1
1 1 1
a(:,:,2) =
1 1 1
1 1 1
a = ones(1, 3) * 7 % Allocates a row vector of length 3 initialized to 7
a =
7 7 7
A data type can also be specified:
a = zeros(2, 1, 'uint8'); % allocates an array of type uint8
It is also easy to clone the size of an existing array:
a = ones(3, 4); % a is a 3-by-4 matrix of 1's
b = zeros(size(a)); % b is a 3-by-4 matrix of 0's
And clone the type:
a = ones(3, 4, 'single'); % a is a 3-by-4 matrix of type single
b = zeros(2, 'like', a); % b is a 2-by-2 matrix of type single
note that 'like' also clones complexity and sparsity.
Preallocation is implicitly achieved using any function that returns an array of the final required size, such as rand, gallery, kron, bsxfun, colon and many others. For example, a common way to allocate vectors with linearly varying elements is by using the colon operator (with either the 2- or 3-operand variant1):
a = 1:3
a =
1 2 3
a = 2:-3:-4
a =
2 -1 -4
Cell arrays can be allocated using the cell() function in much the same way as zeros().
a = cell(2,3)
a =
[] [] []
[] [] []
Note that cell arrays work by holding pointers to the locations in memory of cell contents. So all preallocation tips apply to the individual cell array elements as well.
Further reading:
- Official MATLAB documentation on "Preallocating Memory".
- Official MATLAB documentation on "How MATLAB Allocates Memory".
- Preallocation performance on Undocumented matlab.
- Understanding Array Preallocation on Loren on the Art of MATLAB
