Performance of non-preallocated array

I'm trying to understand the reason these two options are so differnet in performance:

>> tic;z=[];for i = 1:1e5;z(end+1)=i;end;toc
Elapsed time is 0.022571 seconds.
>> tic;z=[];for i = 1:1e5;z = [z i];end;toc
Elapsed time is 7.752663 seconds.

In both we create an array of the numbers 1 to 100000 while increasing the size of the array (without pre-allocating the array) but in the second option, the concatenation is taking much more time than the isertion option, although in both cases we have to re-allocate the memory and copy the array to the new place in memory.

Thanks Noam

Answer 1

[Titus Edelhofer]

Hi,

two comments:

• You are doing the timing in the command line. This gives typically worse results than in a function, because MATLAB can do within functions some runtime optimizations (acceleration) that is not possible on command line. If you put the code into a function, the results (for my machine) are 0.02 vs 0.10 seconds, so still quite a difference but not as drastic as in your case.
• Second: the line "z(end+1)=i" is recognized by the accelerator as "grow in a loop without preallocation", so behind the scenes it will grow the array not simply element by element but will do some sort of preallocation itself. That's better than nothing but of course never as good as explicit preallocation.

Titus

[Noam]

Thanks

[Noam]

I want to create an array (Ar) with a certain size (for instance 10) and a certain capacity (100) , so if i would use the line:

    Ar = [Ar Ar Ar];

It only copy (twice) the Ar array but not reallocate the memory (because the capacity is bigger). It's possible in c++ vector (size and capacity are different values) is it possible in Matlab?

[Titus Edelhofer]

Hi Noam,

not really. You can make the array bigger by using zeros(), and then insert new arrays into the array, but that's not really the same ...

Therefore it's basically "pre-allocate if possible" and don't if not possible.

Titus

[Bjorn Gustavsson]

I remember a good while ago very good people argued that for cases where one wouldn't know beforehand how big an array to pre-allocate it was more efficient to allocate in "sizeable steps" (maybe 10-20 percent of the current array size in the relevant dimension) when needed and then possibly reduce the array after the last assignment - that way there would be a far smaller number or re-allocations and one would win out in the long run. Perhaps the allocation is more efficient these days, maybe the extra overhead would be too big for your case but it might be something to consider...

HTH

[Titus Edelhofer]

Hi Bjorn, yes, that used to be a good workaround but should not be necessary with current releases, since MATLAB does this automatically behind the scenes ...

[John D'Errico]

In fact, MATLAB CAN preallocate an array to have an initial size that is larger than what the array contains, IF the array is sparse. Thus spalloc can allow you to specify the initial size of a sparse zero array.

S = spalloc(M,N,NZMAX) creates an M-by-N all zero sparse matrix
    with room to eventually hold NZMAX nonzeros.

It would be nice if the zeros function had this ability. Add an extra argument at the end, to allow the user to specify the initial allocated space for an array that will be grown.

[James Tursa]

Side Note: The NZMAX value in a MATLAB variable is a size_t type (in C parlance) in the variable structure, and is actually part of the structure definition and available in all MATLAB variables (but to my knowledge unused in everything except sparse). So it is available and could be used for full variables without any changes to the low level variable structure definition if TMW chose to do so.

Answer 2

[James Tursa]

MATLAB's parser can sometimes pre-allocate an array behind the scenes for you (even though you didn't code it that way) if it recognizes a pattern in the for loop. It appears the parser recognizes the pattern in the first case but not the second case.

[Noam]

Thanks