Performance optimization (allocation inside a for loop)

[Rob Mahurin]

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

-- 
Rob Mahurin
Department of Physics and Astronomy
University of Tennessee 		865 207 2594
Knoxville, TN 37996 			rob at utk.edu