Do I need pre-allocation ?

Hello everybody !

You helped me a lot these last days, thanks !

I come up today with another question, concerning preallocation.

Let's consider 2 versions of code :

% a and b some matrix 1D
tab = zeros(length(a), length(b)); % PREALLOCATION
for x_idx = 1:length(a)
    for y_idx = 1:length(b)
        tab(x_idx, y_idx) = a(x_idx) * b(y_idx);
    end
end

And :

% x and y some matrix 1D
tab = zeros(length(x), length(y)); % PREALLOCATION
tab = a' .* b;

I am wondering if I really need preallocation in the second version, because I don't access to every key of an "growing up" array, but I use Matlab vectorization..

So I think I can write (without loosing in terms of perf, and event do a bargain) :

% x and y some matrix 1D
tab = a' .* b;

Am I right ?

Robin.

[Adam]

You are correct that preallocation is only needed when you would otherwise be growing an array in a loop. With vectorisation the whole result variable is assigned to memory at once so preallocation will do nothing other than take up some runtime.

[Stephen23]

This is NOT preallocation:

tab = zeros(length(x), length(y)); % NOT PREALLOCATION
tab = a' .* b;

All you have done is allocate one array to a variable and then allocate another array to that variable. This is totally unrelated to array preallocation. The MATLAB documentation explains what array preallocation is:

https://www.mathworks.com/help/matlab/matlab_prog/preallocating-arrays.html

Array preallocation requires a loop* and indexing. Your version 2 has neither of these.

* or any other kind of incremental code where data gets added to the output array.

[Robin L.]

Thank you !

Stephen Cobeldick I don't understand why using

tab = zeros(length(x), length(y));

is not pre-allocation, because as written in the documentation (your link), « Use the appropriate preallocation function for the kind of array you want to initialize: zeros for numeric arrays ».

And using this line will compute :

tab =

     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0

for example, so the matrix has been created and has been "pre-allocated" with zero values... ?

[Stephen23]

"so the matrix has been created and has been "pre-allocated" with zero values... ?"

Sure, you create an array of zeros... that is not the problem! That line could be array preallocation, if it were followed by some code that accessed that array using some indexing.

But what you actually do on your very next line of code is to simply discard that entire array and replace it entirely with a totally new array. All you are doing is just basic allocatiion of an array to a variable name. And then allocation of another array to that same variable name.

But none of this has anything to do with array preallocation before a loop.

The explanation at the top of that documentation explains what array preallocation is and when it is needed: preallocate before LOOP/S and then inside the loop/s access the array elements using INDEXING. Without the indexing there is no point, you simply discard everything.

Because you simply discard the first array then its class and size are totally irrelevant to the second line. Try it with a cell array, and you will see that MATLAB simply replaces your first (cell) array with the second (numeric) array: no problem, no errors, no preallocation:

>> tab = cell(3,4); % NOT PREALLOCATION
>> tab = [1,2,3] .* [4,5,6]
tab =
  4  10  18

[Steven Lord]

In general the zeros function is one tool you can use to preallocate.

In your specific example your call to the zeros function is not preallocation.

Preallocating an array means allocating/initializing an array so you can fill it in later on, as opposed to reallocating the array to be a new size every time you add an element to it.

You're allocating an array, then throwing that allocated array away and reusing that name for a whole new array that has no relation with the originally allocated array.

[Robin L.]

I thank you Stephen Cobeldick and Steven Lord ! Now I understand what means pre-allocation ?

Answer 1

[Guillaume]

Robin, in the 2nd case, yes you were attempting to preallocate the array. However, the array you preallocated is not the same array that you will end up with. In fact, the array you preallocated is immediately destroyed and replaced by a completely different array on the next line. Hence why Stephen says it's not preallocation.

In fact, more than unnecessary, your preallocation attempt is counter productive. Matlab waste time preallocating an array that is never going to be used and will be destroyed immediately.

There is a big difference between

tab(r, c) = something   %indexing

and

tab = something  %no indexing

In the first case, using indexing, you're assigning to one or more elements of the array. If the array is not big enough to start with, then matlab waste time making room for the new element(s). Hence preallocation is important.

In the second case, where there's no indexing, you're copying an entire array. Whatever was in the variable before that gets discarded, so preallocation doesn't work.

[Robin L.]

Thank you Guillaume ! Now I understand what means pre-allocation ?

Answer 2

[madhan ravi]

Preallocation is not necessary in your second version.

[Stephen23]

The second version has no preallocation anyway. It just allocates an array to a variable. And then allocates another array to that variable. Which has nothing to do with preallocation.

[madhan ravi]

I said Preallocation is not needed for the second case , where have I ever said it was preallocation?, one flaw was I never explained the reason for it but Guillaume did so +1.

[Robin L.]

Thank you madhan ravi ! Now I understand what means pre-allocation ?