[Top][All Lists]

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

Re: Performance optimization (allocation inside a for loop)

From: Rob Mahurin
Subject: Re: Performance optimization (allocation inside a for loop)
Date: Fri, 3 Apr 2009 15:49:11 -0400

On Apr 3, 2009, at 2:39 PM, Przemek Klosowski wrote:
Is it possible to adjust the Octave's allocation algorithm so that it could allocate larger chunks of data (or growing chunks of data)?

The common way of doing what you're asking is to over-allocate, e.g. on filling up the current size-N block, re-allocate a new block of size 2N; this way the allocation and copying cost is proportional to the log(size) rather than size of the array.

The problem for Octave is that it results in wasting a constant fraction of the total allocated size, which is a critical no-no for anyone with large data sets.

I wonder if the allocation algorithm could be modified to over- allocate a constant _amount_ (rather than constant fraction)---or maybe a constant fraction up to certain array size and constant amount above that. Of course this approach would require arrays to have two sizes: user-visible and internal---because we don't want the over-allocation to be shown in length(array)

One solution might be to allocate the requested amount of memory on creation, and use some over-allocation if the (end+1)th element is accessed. Then code like

        list = []; for i = 1:n; list(i) = something; endfor

would have some-but-fewer reallocations, while

        data = zeros([big huge enormous]);
        for i = 1:numel(data); data(i) = something; endfor

wouldn't have a space penalty.

This sort of under-the-carpet trickiness would still lead to subtle bugs, but different ones from a reallocation for every size change.

Another option would be to have an internal counter associated with a matrix that counts how many times it's been reallocated, and switches strategies (perhaps emitting a warning) if the same object's size increases by the same amount more than a handful of times.


Rob Mahurin
Department of Physics and Astronomy
University of Tennessee                 865 207 2594
Knoxville, TN 37996                     address@hidden

reply via email to

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