Performance optimization (allocation inside a for loop)

[James Sherman Jr.]

I'm sure someone will answer this in a more technically precise way, but I
believe the answer is, in short, no.  Essentially since octave is a script,
there is no way for octave to "know" that you are going to eventually want a
vector of size n.  It basically sees (in the first case)

allocate room for a vector of size 1
write vector of size 1
allocate room for a vector of size 2
copy previous vector
write new value at end of vector

and so on.  The second case is:
allocate room for a vector of size n
write value in first element
write value in second element

and so on.  At least this is my understanding.

James

On Wed, Apr 1, 2009 at 4:15 PM, r <nbs.public at gmail.com> wrote:

> I've recently hit a performance problem with a "for" loop producing
> vectors of data. Consider the following (deliberately simple) example:
>
> function retval = test(n)
>  # retval = zeros(1, n);
>  for n = [1:n]
>    retval(n) = n;
>  endfor
> endfunction
>
> octave:26> tic;test(10000);toc
> Elapsed time is 0.8 seconds.
> octave:27> tic;test(100000);toc
> Elapsed time is 72 seconds.
>
> So the complexity is O(n^2).
>
> The same function with a preallocated retval vector:
>
> function retval = test2(n)
>  retval = zeros(1, n);
>  for n = [1:n]
>    retval(n) = n;
>  endfor
> endfunction
>
> has a complexity of O(n):
>
> octave:29> tic;test2(10000);toc
> Elapsed time is 0.16 seconds.
> octave:30> tic;test2(100000);toc
> Elapsed time is 1.9 seconds.
>
> Is it possible to adjust the Octave's allocation algorithm so that it
> could allocate larger chunks of data (or growing chunks of data)?
>
> Regards,
> -r.
> _______________________________________________
> Help-octave mailing list
> Help-octave at octave.org
> https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www-old.cae.wisc.edu/pipermail/help-octave/attachments/20090401/a67dec67/attachment.html