Performance optimization (allocation inside a for loop)

[r]

On Thu, Apr 2, 2009 at 9:59 AM, Francesco Potorti` <Potorti at isti.cnr.it> wrote:
>>  for n = [1:n]
>  A prefereable way is to write
>
> for ii = 1:n

Sure, my mistake.

> 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

That's a good idea. Perhaps it would be enough to document these
solutions (e.g. in "help for") so that newcomers didn't had to
rediscover them on their own.

>>So the complexity is O(n^2).
>
> Well, given two points, it could be anything :)

plot([10 20 30 40 50 60 70 80 90 100 120 150]*1000, [0.88 2.11 3.9
6.48 10.7 19.9 28.3 39.8 58.2 82.1 123 215])

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

I think chunks of ~5% of the structure size (perhaps more for smaller
arrays) would be affordable by anyone and would effectively fix these
allocation issues in practical applications. Whether it is worth the
effort is a different question. It certainly doesn't help Octave when
somebody executes the same code in Matlab and Octave and the latter is
hundreds times slower.

Regards,

-r.