Re: Performance optimization (allocation inside a for loop)

[Jaroslav Hajek]

On Thu, Apr 2, 2009 at 1:18 AM, r <address@hidden> wrote:
> This is a general problem. It doesn't just affect scripting languages
> - you may hit this issue equally well in C/C++.
>
> A common strategy is to allocate a bit more space than currently
> needed, so that malloc/realloc doesn't need to be called every single
> time the user appends data to the structure. Even better, this margin
> can be made dependent on the current structure size (e.g. proportional
> to n or to log(n)). This second scheme results in better
> performance/memory occupation ratio.
>
> I'm (now) perfectly OK with preallocating memory manually, but it took
> me a lot of time to figure out where the bottleneck is. 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.
>
> Regards,
> -r.
>

I don't think it would be hard to implement a chunked allocation in
Octave, though it surely would complicate the array internals
somewhat. But I see little need for it. The preferred coding style in
Octave is using vectorized expressions, where you normally don't face
this issue.
Also, the choice of a good allocation strategy is subtle. To reduce
the reallocation time in your loop to O(log(N)), you need to
over-allocate by a multiplicative factor, which may actually make
things worse for someone dealing with large arrays.



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