Performance optimization (allocation inside a for loop)

[Jaroslav Hajek]

On Thu, Apr 2, 2009 at 9:53 PM, r <nbs.public at gmail.com> wrote:
> 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

based on what...?

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

I don't think things work differently in Matlab. At least with Matlab
2007, I see the same behaviour.
A lot of code runs faster in Matlab because it's better optimized,
especially given the JIT accelerator. But there's also code that runs
faster in Octave. We don't take always the same path as Matlab. I, for
instance, don't think that a JIT compiler is really such a great idea.
What doesn't help Octave would probably fill a long list. What does
help Octave includes donations, patches, bug reports, etc.

-- 
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz