[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Performance optimization (allocation inside a for loop)

From: James Sherman Jr.
Subject: Re: Performance optimization (allocation inside a for loop)
Date: Wed, 1 Apr 2009 17:35:52 -0400

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.


On Wed, Apr 1, 2009 at 4:15 PM, r <address@hidden> 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;

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;

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

Help-octave mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]