help-octave
[Top][All Lists]

## Performance optimization (allocation inside a for loop)

 From: r Subject: Performance optimization (allocation inside a for loop) Date: Wed, 1 Apr 2009 21:15:26 +0100

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.