Assigning values to a preallocated variable costs more time than to a non-preallocated variable?

Please see the following codes.

Why type-1 code is more costly than type-2 and type-3 codes?

As far as I know, type-1 preallocates variable and thus is supposed to save time every time it is assigned with the multiplication result. Type-2 and type-3 codes are expected to more costly due to the recreation and reallocate once a new multiplication is performed.

Are there anyone know what cause the difference?

t = testMain

t = 1×3

0.2646 0.1969 0.1970

function t = testMain
t = zeros(1,3);
f = @() testAssignment(1);
t(1) = timeit(f);
f = @() testAssignment(2);
t(2) = timeit(f);
f = @() testAssignment(3);
t(3) = timeit(f);
end

function testAssignment(type)
N = 10000;
b = rand(100,100);
c = rand(100,100);
if type == 1
    a = zeros(100,100);
    for i = 1:N
        a(:) = b*c;
    end
elseif type == 2
    for i = 1:N
        a = b*c;
    end
elseif type == 3
    a = zeros(100,100);
    for i = 1:N
        a = b*c;
    end
end
end

Answer 1

[Walter Roberson]

a(:) = b*c;

In MATLAB, as each expression is calculated, the result has to be stored in memory along with information about the size and class of the data, whether it is complex, and so on. This is all the same information that is needed to store a variable except for not having a name slot. For ease of code use, what is constructed to describe each intermediate result is probably the same data structure as a symbol table slot, except with the name empty.

So when b*c is calculated on the right hand side, the result has already been allocated memory.

And then when you do the a(:) = assignment, the results are copied out of that temporary memory into the previously-allocated memory in "a" -- which takes time.

Thus, when you are replacing all of an array, it is almost always faster and a better idea not to bother preallocating, just write over the entire array.

The benefits of pre-allocation come when you are assigning to part of an array. If you were assigning to a(:,:,i) in the loop, then at any one iteration size(b*c) would be how much memory would be copied over, and you would do that for N iterations so the result would be need to store numel(b*c)*N memory items if a had been preallocated as 3D .

If on the other hand you had not preallocated a but were still doing a(;,:,i) = b*c then if a did not exist the first time, then the first iteration a(:,:,1) = b*c would not copy anything -- in that special circumstance of creating a variable with (:,:,1) notation then the variable would be assigned the same data block as b*c without copying. But then iteration 2, a(:,:,2) = b*c would proceed by looking and seeing that a was currently too small to hold that, so it would allocate enough memory to hold the newer result, and would copy the existing a(:,:,1) into the new location, then copy the b*c into the now-allocated (:,:,2). Then for iteration 3, a(:,:,3) = b*c would notice the destination is too small, would allocate (:,:,3) layer, would copy the existing (:,:,1:2) into it, copy the b*c into (:,:,3) ... and so on. The first iteration copies 0 * numel(b*c), the second iteration has to copy the existing numel(b*c) into the expanded area and copy the new numel(b*c) so that is 2*numel(b*c) copied. The third iteration has to copy the existing 2*numel(b*c) into the expanded area, copy the new numel(b*c), so that is 3*numel(b*c) copied ... and so on. Over N iterations that would be 0+2+3+4+...N = (N*(N+1)/2 - 1) * numel(b*c) total copies -- as compared to the N*numel(b*c) copied in the pre-allocated case.

Thus, pre-allocation when you are going to write over the complete result is slower, but pre-allocation is the same speed as incremental growing for 2 iterations, and pre-allocation is faster for more than 2 iterations.

[lala]

I got it. Thank you.