Performance optimization (allocation inside a for loop)

[Rob Mahurin]

On Apr 1, 2009, at 7:18 PM, r wrote:
> BTW, low "for"
> loop performance is commonly blamed on the lack of a JIT compiler, but
> I wouldn't be surprised if at least some of the test cases were
> actually suffering from issues like memory allocation. After all, JIT
> compilers don't typically speed up evaluation by more than a constant
> factor.

Right, but it's a big factor.  Compare your test2

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


to the equivalent

octave:29> tic; n = 1e5; retval = 1:n; toc
Elapsed time is 0.000756025 seconds.
octave:30> tic; n = 1e5; retval = (1:n)(1:n); toc
Elapsed time is 0.00757694 seconds.
octave:31> tic; n = 1e5; retval = [1:n]; toc
Elapsed time is 0.0125589 seconds.

(These apparently take different paths through Octave's lazy-copying  
logic.)

Rob

-- 
Rob Mahurin
Department of Physics and Astronomy
University of Tennessee 		865 207 2594
Knoxville, TN 37996 			rob at utk.edu