Why is vertcat slowing things down?

In the code below, 10,000 repetitions takes 2 seconds... and 100,000 repetitions takes 60 seconds! (I was expecting 20 seconds or less)...

What is going on? by a process of elimination, I suspect "vertcat" is slowing things down...

(Please see how "tic toc" behaves with repetitions = 10,000 and 100,000)

Is this a known issue with vertcat? If so, what are my other options?

(Note: looping the 10,000 algorithm 10 times would be much faster... but surely there has to be a more elegant way to do 100,000 repetitions in 20 seconds)

Thanks

Doron

*********

tic

repetitions = 10000

llim = -1;
ulim = 3;

xstack = [];
xlifestack = [];

for i = 1:repetitions

x = 0;
xlife = 0;                   
while   ulim > x && x > llim 
x = x + normrnd(0,1);
xlife = xlife + 1;       % "...and the walk lives one more step"
end

if x > llim                        
x = ulim;
else x = llim;       
end

xstack = vertcat(xstack, x);     
xlifestack = vertcat(xlifestack, xlife);

end

xbar = mean(xstack);
xlifebar = mean(xlifestack);

toc

Answer 1

[Honglei Chen]

My 2 cents::

1. You may want to preallocate the memory. The in each iteration, you just put the new data into corresponding slots.

2. If your entire purpose is to compute the mean, then why not just record the sum and number of samples and update them for each iteration. These are just scalars.

[Oleg Komarov]

Point 1 is the reason. At each iteration you are growing the xstack and what happens is a ful copy paste of the array.

Preallocate: http://www.mathworks.co.uk/help/techdoc/matlab_prog/f8-784135.html

[Doron]

Thank you Honglei and Oleg...

Could you please explain the intuition behind preallocation? how does this help?

Doron

[Honglei Chen]

When you preallocate, MATLAB knows at the end how much memory it needs to maintain so it reserves the space for you. Thus this memory allocation only happens once. If you don't do the preallocation, each time you grow something by vertcat, it needs to find some room in the memory that can hold the combined result, copy everything over, add the new one, and then delete the old one. And you do this every time. When your array gets larger and larger, these operations become more complex.

[Doron]

Does this mean that simply by saying "zeros xtack = zeros(100000,1)" before the loop solves the problem?

[Honglei Chen]

yes, if every iteration x is just a scalar.

[Oleg Komarov]

No, you also have to allocate into xstack by indexing.

[Doron]

right...

xstack = zeros(100000,1)

%then

for i = 1:repetitions

% x is computed by an algorithm

xstack(i) = x

end

[Doron]

Thanks Oleg and Honglei,

I went with "xstack = (repetitions, 1)"

I don't know which one to accept as the answer, so I flipped a coin...

Thank you both

Doron