MATLAB Answers

No performance improvement with preallocating for object arrays

49 views (last 30 days)
Tom Wenk
Tom Wenk on 13 Apr 2018
Edited: Tom Wenk on 25 Apr 2018
Hi everyone,
I programmed a database where I want to save handle-class-objects in an array ( Matlab R2016b). Now for testing I programmed a loop and Matlab suggested me to preallocate the array. I started reading more about Preallocation and tried to test whether the time saved is worth it or not (because it is difficult in my task to say how many objects I get).
As far as I understood, I can preallocate an object-array by using:
objectArray( numberOfObjects ) = classObject
whereas classObject needs to have a default constructor. The array is then filled with default objects.
Now for testing I wrote the following code:
% Signal = class object / needs to be implemented first
numberOfObjects = 100000;
iterations = 100;
timeNeeded = zeros( iterations, 1 );
% WITH preallocation
for i = 1 : iterations
clear objectArray;
objectArray( numberOfObjects ) = Signal; % Preallocating the array
tic;
for index = 1 : numberOfObjects
% Assigning elements to the array
objectArray( index ) = Signal( 'Test', index, numberOfObjects, iterations );
end
timeNeeded( i ) = toc;
end
meanValue = mean( timeNeeded );
clear timeNeeded objectArray;
timeNeeded = zeros(50,1);
% WITHOUT preallocation
for i = 1 : iterations
clear objectArray;
tic;
for index = 1 : numberOfObjects
% Directly assigning the elements to the array without preallocation
objectArray( index ) = Signal( 'Test', index, numberOfObjects, iterations );
end
timeNeeded( i ) = toc;
end
meanValue = [ meanValue; mean( timeNeeded ) ]
In this test I saved 100000 class objects for 100 times, took the time and calculated the mean. For me, the time needed with preallocating was 1.2640s and without preallocating 1.2613s.
Did I make a mistake or has the 'organization' of Matlab become so fast that preallocation is not needed anymore? In the the following article from 2011, the author says that with Matlab R2011a they improved some algorithms, so automatic array growth gets significantly faster. Maybe there have been some more improvements?
Thanks for the help
Tom
EDIT: The objects I'm talking about are handle class objects
EDIT: I also tried filling the array with the following line (in the for-loop)
objectArray = [ objectArray, Signal ]; % Assigning elements to the array
In this variant there was a huge improvement with preallocating against without it! Without preallocating I even had the time increasing non linear with the number of objects I assigned.
  10 Comments
Tom Wenk
Tom Wenk on 13 Apr 2018
Maybe you're right and there is no point in preallocating the array.
But now that I tested the benefit and didn't see one, I still want to know why that is the case! :D

Sign in to comment.

Answers (4)

James Tursa
James Tursa on 13 Apr 2018
Edited: James Tursa on 13 Apr 2018
Pre-allocation of variables means different things depending on the variable class.
(1) Numeric, char, and logical classes:
This is pretty straightforward since the data model is easily understood. You have data pointer(s) that point to blocks of memory that hold the raw data. If you are going to fill that data in a loop, pre-allocation makes a lot of sense so the data areas don't get copied & recopied over and over again at each iteration. This copying and recopying can easily dominate run times.
(2) Cell and struct class and the old @directly style class objects:
This begins to get a little harder to understand, especially for beginners. You still have data pointer(s) that point to blocks of memory that hold the raw data, but the raw data of cell and struct variables is other variable pointers. That is, the raw data areas of cell and struct arrays contain 32-bit or 64-bit addresses of other variables. (The field names for struct variables is a side complication that doesn't affect the points of this discussion ... they are actually held in a "global" common field name pool that all structs use). Internally, the old @directory class objects are actually structs.
For cell and struct variables, pre-allocating of variables can make sense but only if you do it correctly and here is where it gets tricky for the beginner because they don't understand the underlying data model. Consider this code:
C = {}; % start with an empty cell
n = 1000; % number of cells that I want
for k=1:n
C{k} = zeros(1,100); % pre-allocate because I know I will fill this in downstream
end
% isshared call goes here
% now fill in the data
for k=1:n
C{k} = myfunction(100); % some function that returns a 1x100 double vector
end
The above code is bad. The first loop grows the size of the C array in a loop which is bad for the reasons already mentioned above. In this case the data that is getting copied & recopied are the 32-bit or 64-bit variable pointers, not the zeros(1,100) variables. So it is not quite as bad as it might originally seem, but it is still bad. But also there are 1000 different zeros(1,100) variables created and stored in the cell array, which are then wiped out with the very next loop. So just a bunch of wasted effort in the first loop. If you use my isshared( ) function from the FEX you can see that after the first loop (but prior to the second loop) there is no sharing:
>> [N,M] = isshared
N =
Empty matrix: 0-by-1
M =
Empty cell array: 0-by-1
So now consider this modification:
n = 1000; % number of cells that I want
C = cell(1,n); % at this point C contains 1000 NULL pointers
C(1:n) = {zeros(1,100)}; % now C has 1000 addresses that are all the same
% isshared call goes here
% now fill in the data
for k=1:n
C{k} = myfunction(100); % some function that returns a 1x100 double vector
end
This is a better way of doing the initial C pre-allocation, since there is only one physical zeros(1,100) variable in memory. That is, there are 1000 shared reference copies of that zeros(1,100) variable contained in C. All 1000 addresses in the data area of C are exactly the same. But again it is wasted effort because they are all wiped out with the second loop. To see the sharing going on after the initial pre-allocation (but prior to the last loop):
>> [N,M] = isshared
N =
1000
M =
{1x1000 cell}
>> M{1}(1:3)
ans =
'C{1}' 'C{2}' 'C{3}'
So, all 1000 elements of C are in fact physically the same variable in memory. A good way to pre-allocate, but not if you are simply going to turn around and replace the elements downstream.
(3) Classdef objects:
Now it is a lot harder to understand, because the data model of classdef objects is not published. There is no official documentation telling you how or where the properties are stored, or what happens when you create arrays of them. Things can be quite different if the object is derived from handle or not. Or the objects may contain connections to other resources. So what happens when you create one of these objects, or arrays of these objects, can depend intimately on the details of the class definition. So a general discussion of what happens when you create arrays of them is probably out of scope until specific details of the class are known.
IF your class object is of the "straightforward" variety (e.g., has properties of regular MATLAB variables and functions that operate on them), then my guess is that the behavior of creating arrays of them acts like creating arrays of cell or struct variables. That is, you get deep or shared copies of stuff depending on how you do the pre-allocation. And there may be NULL or shared reference copies held in the data areas for some elements. Here, isshared( ) can shed some light on things. Consider this class definition:
classdef myclass3
properties
a
b
end
end
Then consider this code:
>> clear all
>> m = myclass3
m =
myclass3
Properties:
a: []
b: []
Methods
>> m.a = 1:3;
>> m.b = 4:6;
>> A(3) = m; % Method A
>> B(1:3) = m; % Method B
>> [N,M] = isshared
N =
6
6
M =
{1x6 cell}
{1x6 cell}
>> M{1}
ans =
'A(3).a' 'B(1).a' 'B(2).a' 'B(3).a' 'm.a' []
>> M{2}
ans =
'A(3).b' 'B(1).b' 'B(2).b' 'B(3).b' 'm.b' []
So things worked as we might have expected. When we created the A array, only the 3rd element got a copy of our m classdef object. The other two array element are there, but when we look at them they are just default empty elements:
>> A(1)
ans =
myclass3
Properties:
a: []
b: []
Methods
What is not clear to me is if the underlying variable addresses for A(1) and A(2) are NULL in the background (like cell and struct arrays), or if there is a physical variable (with empty properties) in memory. Since the data model is not published, I can't look there even in a mex routine to confirm anything. So how the A(1) and A(2) elements are created when A gets created is still unclear to me.
For the B variable, fortunately it appears to behave in the "shared" sense that we were hoping. That is, B(1) and B(2) and B(3) are all shared copies of each other (and of m). There is really only one physical copy of the 1:3 and 4:6 data in memory, just like we were hoping.
Another example with a slightly different class definition:
classdef myclass4
properties
a = 1:10;
b = 2:20;
end
end
Here the default object has non-empty properties. Now let's see what happens:
>> clear all
>> m = myclass4;
>> m.a = 1:3;
>> m.b = 4:6;
>> A(3) = m;
>> [N,M] = isshared
N =
2
2
2
2
M =
{1x2 cell}
{1x2 cell}
{1x2 cell}
{1x2 cell}
>> M{1}
ans =
'A(1).a' 'A(2).a'
>> M{2}
ans =
'A(1).b' 'A(2).b'
>> M{3}
ans =
'A(3).a' 'm.a'
>> M{4}
ans =
'A(3).b' 'm.b'
So here it becomes clear that when building the object array A, MATLAB has apparently called the constructor only once to fill in the A(1) and A(2) elements, since we see that A(1) and A(2) are shared copies of each other.
Now consider this modification:
classdef myclass5
properties
a = 1:1000;
b = rand(1,1000); % a random element
end
end
And some array creation code:
>> clear all
>> m = myclass5;
>> A(3) = m;
>> [N,M] = isshared
N =
4
4
M =
{1x4 cell}
{1x4 cell}
>> M{1}
ans =
'A(1).a' 'A(2).a' 'A(3).a' 'm.a'
>> M{2}
ans =
'A(1).b' 'A(2).b' 'A(3).b' 'm.b'
With this example, it appears that MATLAB has only called the default constructor once when m was created. It also appears that this default object is saved in memory somewhere and re-used for the A(1) and A(2) elements when the object array A is created. The fact that even the rand parts "b" of A(1) and A(2) and A(3) are shared with each other seems to further confirm that the default constructor was only called once overall. As long as the classdef remains in memory, this background default object appears to get re-used for all default object creations. It is only when the classdef itself is cleared from memory (which apparently causes that background default object to get cleared) that forces MATLAB to re-construct a new default object when it first gets called. E.g.,
>> clear all
>> m = myclass5;
>> m.b(1:3)
ans =
0.3796 0.3191 0.9861
>> clear m
>> m = myclass5;
>> m.b(1:3)
ans =
0.3796 0.3191 0.9861 % <-- same as first time. rand( ) did not get called again
>> clear all % <-- force the classdef itself to get cleared from memory
>> m = myclass5;
>> m.b(1:3)
ans =
0.4271 0.9554 0.7242 % <-- now rand( ) gets called again
BACK TO THE ORIGINAL QUESTION:
Q: Can the original poster save any time by doing a pre-allocation of some sort for this object array?
A: Maybe or maybe not. It all depends on the specifics of what the class does, and what he is doing with the object elements downstream in his code. Based on the small examples I show, doing a "last element assignment" method of pre-allocating the object array ala Method A appears to be a good approach. The Method B approach really only makes sense if you are not replacing these elements downstream in your code.
I'm going to hazard a guess that growing a classdef object array in a loop probably behaves the same way as cell and struct variables. That is, you are probably only copying and recopying 32-bit or 64-bit pointers around in memory. If the classdef object array is not too big in size then you probably won't notice much of an overall timing difference between the pre-allocating and not pre-allocating cases.
FYI, isshared( ) can be found here:
isshared( ) does not yet work with R2018a+ versions because the data memory model has changed and I have yet to write new mex code to support that.
  2 Comments
James Tursa
James Tursa on 16 Apr 2018
"Cell-Array: Pointer => Pointer => raw data"
Yes. That is essentially what is going on.
"As far as I understood preallocating there is always unnecessary data you fill the array with (which should allocate the same memory as the data you want to assign later) which is overwritten again later."
Let's separate the memory allocation part from the data filling part, and be clear about what we mean by data filling. When you create a variable with usual MATLAB functions, the raw data part does get initialized to something. If you use the zeros( ) function for numeric variables, the memory is allocated and the raw data is filled with 0's. E.g.,
x = zeros(1,10); % data memory is allocated and filled with 0's
If you use the cell( ) function to create a variable, memory is allocated for the raw data (in this case pointers) and the raw data is filled with NULL values. E.g.,
x = cell(1,10); % data memory is allocated and filled with NULL's
But for cell and struct variables, that is the only thing that is done. That "2nd layer" of variables is not filled in with anything until you the programmer put something there. Creating a variable to replace a NULL makes no sense if you are simply going to assign something to that element downstream in your code. That is where the waste is in the examples above. When you access a NULL pointer of a cell or struct variable at the m-code level, MATLAB creates a temporary empty double variable on the fly.
For classdef objects, the situation appears to be different. When I look at the reference count of the properties by hacking into them in a mex routine, it appears that reference copies of the default object have been created for each uninitialized element of the object array. I.e., it appears to me that the uninitialized object array elements are not NULL and created on the fly when accessed (like cell and struct array elements), but are actually physically present in the array element spots (as reference copies of the default object). This is educated guesswork on my part based on mex hacking since this info is not officially published, but it sure looks like that is what is going on. (Otherwise I can not explain the reference count numbers I am seeing). So you can ignore my guess in my original post. Based on some hacking just done a few minutes ago, I see evidence that the uninitialized object array elements actually physically contain reference copies of the default object (and do not contain NULL values like cell and struct arrays). At least that is what appears to happen when the default object has properties that are given a default value. Whether this behavior applies to objects whos properties are not given default values I have no way of checking, even with a mex hack.
For the myclass4 example above, I was just trying different things out to see what the resulting MATLAB behavior would be. Nothing else implied.

Sign in to comment.


John D'Errico
John D'Errico on 13 Apr 2018
Edited: John D'Errico on 13 Apr 2018
First. There are many ways of pre-allocating a matrix!!!!!!
Ones pre-allocates with ones, not zeros, for example:
x = ones(100);
Spalloc allocates as sparse matrix.
Zeros allocates as zeros.
You can just use assignment, thus if was previously undefined, then this preallocates z with zeros:
z(100,100) = 0;
Use repmat.
z = repmat(0,100,100);
repmat is actually a good way to pre-allocate struct arrays.
A.x = 1;
A = repmat(A,100,100);
Assignment in general can be a pre-allocation. Thus, this pre-allocates z as a vector
z = 1:100000;
Or, you can pre-allocate as inf, or NaN.
z = inf(1000,100);
z = NaN(100);
I often use NaN pre-allocation myself, at least when debugging code. That way I can easily check to see what was left unfilled when I am testing code.
You can pre-allocate a cell array.
C = cell(100,100);
Others too, I am sure. If I spent a few minutes I could think of many.
Next, WHY pre-allaocate? When will it help?
pre-allocation only helps when you would otherwise grow that array dynamically. This is bad:
z = [];
for i = 1:100000
z = [z,i];
end
In fact, that is obscenely bad. This is better:
z = zeros(1,100000);
for i = 1:100000
z(i) = i;
end
But still not as good as this simple line, where z is pre-allocated in place exactly as I want it anyway.
z = 1:100000;
You pre-allocate because growing an array dynamically, as I did above is BAD. That forces MATLAB to reallocate memory each time the array is grown. Then it copies the ENTIRE array contents over, plus inserting the one new extra element. This is a quadratic growth thing, where the time spent grows quadratically with size.
So unless you are growing the array, pre-allocation is a waste of time. You do not need in general to allocate memory for arrays, unless they are growing.
Finally, IF you pre-allocate an array, then clear it inside a loop, the array goes away. It is as if you have never done any pre-allocation. In fact, you spent more time than was needed, because the pre-allocation was a waste of time.
  4 Comments
John D'Errico
John D'Errico on 16 Apr 2018
This is pretty much equivalent to using repmat.
timeit(@() zeros(1,1000,'hpf'))
ans =
0.0052384
timeit(@() repmat(hpf(0),1,1000))
ans =
0.0052362
Both are efficient ways to create the result.

Sign in to comment.


Philip Borghesani
Philip Borghesani on 13 Apr 2018
Edited: Philip Borghesani on 13 Apr 2018
Your pre-allocation code is doing the work twice. Try profiling your code. ObjectArray( numberOfObjects ) = classObject will call the default class constructor once for each member of objectArray, then you are looping through the vector and re-initializing each object. The cost of calling the class constructor twice for each object can easily swamp the benefit of pre-allocating.
Growing an object array (or cell array or structure, especially for handle classes) is frequently not that bad. Only the pointers to the members need to be moved/copied with each growth so if the objects are large/complex the time to create new elements may swamp any time to copy the pointers. Of course if the array is huge O(n^2) will bite you every time.
  3 Comments
Tom Wenk
Tom Wenk on 14 Apr 2018
Hi Philip,
the second initialisation with the loop is on purpose, cause it is not meant as an initialisation but as an assignment. I want to preallocate the array and then assign elements to it in a for loop.
In the second variant I'm directly assigning the elements to the array in the loop without preallocating.
I hope I got your point right?

Sign in to comment.


Jan
Jan on 13 Apr 2018
When I run the code for
Signal = 7
The timings are (R2016b):
0.0017 % With pre-allocation
0.0134 % Without
The effect of pre-allocation is small in this example, if you use a simple numeric scalar as data. For a class object, there is not much additional overhead, because the much more expensive constructor is called exactly the same number of times in both cases. Only the storing in the array differs, but the concerning costs are comparable to appending/inserting scalar doubles in an array.
I think, the effects of pre-allocation are simply too small in your example to be impressing. Of course, pre-allocation helps to improve the speed of the program, but if the memory management is not the bottleneck of the code, the effects are tiny.
  7 Comments
Tom Wenk
Tom Wenk on 16 Apr 2018
Sorry for the confusion, I got confused myself!!! :S
"The decision was clear there was a huge improvement through preallocating."
I made a stupid mistake here! At the very beginning (not stated in my question-post) I had this line:
objectArray = [ objectArray, Signal ];
Then I looked into preallocating and preallocated the array. Obviously I could not use the same line again because like you said it just appends the new elements. Therefore I used
objectArray( index ) = Signal;
with the preallocated array and compared the times. This was the huge difference which I thought was coming from the preallocating. After that I compared
objectArray( index ) = Signal;
with and without preallocation (my question-post). Here there was no improvement and I questioned preallocation for handle-class-object-arrays, also because I couldn't find any information about this special case.
So my new question is, where is the difference between
objectArray( index ) = Signal;
when index exceeds the array dimension and
objectArray = [ objectArray, Signal ];
?
Because in my imagination the procedure behind the code was the same in both lines. But this seems not to be the case.
"As far as I can see, you have "numberOfObjects", such that you do know the number of objects in advance."
The number I used in the test is totally made up! I asked my supervisor if he could give me any number but he said no, he wants to have the program as flexible, fast and robust as possible..

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!