help-octave
[Top][All Lists]

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

--
Rob Mahurin
Department of Physics and Astronomy
University of Tennessee                 865 207 2594