Re: Performance optimization (allocation inside a for loop)

[Francesco Potorti`]

>function retval = test(n)
>  # retval = zeros(1, n);
>  for n = [1:n]
>    retval(n) = n;
>  endfor
>endfunction

Note that your loop style is not advisable, as you use the same variable
as an index and as a limit.  While it works, it is not easy to read and
is prone to errors.  A prefereable way is to write

for ii = 1:n
  retval(ii) = ii;
endfor

In the cases when you really need a for loop because your code cannot be
vectorised, the efficient way is to either preallocate the vector, as
you did, or to start writing from the end using 
 for ii = n:-1:1
so that Octave allocates the vector on the first iteration.

>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).

Well, given two points, it could be anything :)

>Is it possible to adjust the Octave's allocation algorithm so that it
>could allocate larger chunks of data (or growing chunks of data)?

Hm.  Maybe growing in fixed-size chunks would be a good idea, in fact it
would significantly alleviate the problem you observe.  Maybe also
growing in variable-size chunks would be a good idea.  In fact, others
have observed that this would be dangerous for really big arrays, but
growing a big array is anyway bad practice and very slow, so those
conciously working at the limits of available memory will use the
currently recommended techniques, while the others could benefit from
improved performance and not be too disturbed by the occasional
out-of-memory error.

-- 
Francesco Potortì (ricercatore)        Voice: +39 050 315 3058 (op.2111)
ISTI - Area della ricerca CNR          Fax:   +39 050 315 2040
via G. Moruzzi 1, I-56124 Pisa         Email: address@hidden
(entrance 20, 1st floor, room C71)     Web:   http://fly.isti.cnr.it/