Prev: InitialMagnification is linear?
Next: Need cross-sectional area of non-convex 3D point cloud.
From: James Tursa on 4 May 2010 17:29
It was recently pointed out to me by a user of my mtimesx tool that if you start with a large sparse matrix A and then do the operation 0*A, the result takes just as much space as the original A even though it only needs enough space for one element. I tracked it down to the MATLAB API mxRealloc function, and indeed the behavior changes from R2008a to R2008b. In 2008a (and earlier I presume, although I only tested R2007a) when a large block is reallocated with mxRealloc the large block is freed and a new small block is allocated, thus recovering the extra memory. But for R2008b and beyond, the large block remains allocated even though only 1 element is requested in the mxRealloc call. So I checked the MATLAB intrinsic * operator and it has the same undesirable behavior so it is apparently calling the same (or similar) routine in the background. e.g., try the following:

A = sprand(10000,10000,0.1);
C = cell(1,100);
for k=1:100; C{k} = 0*A; end

For R2008a and below the above code behaves nicely. For each iteration the 0*A operation temporarily produces a large sparse matrix, but once the zeros are cleared out the result is much smaller and you can easily fit 100 of them in the cell array. But for R2008b and beyond all of the 0*A results take large amounts of memory and quickly exhaust the heap.

So bottom line for me is I think I will have to write my own version of mxRealloc for use in mex functions and not rely on mxRealloc to free the unneeded memory. Also, it appears that MATLAB intrinsic functions that rely on realloc behavior like the 0 * sparse operation may not behave nicely and may need workarounds. Maybe a bug report to TMW is in order.

Tested system: 32-bit WinXP PC, R2007a through R2010a

Anyone out there have comments on this?

James Tursa
From: Walter Roberson on 4 May 2010 18:46
James Tursa wrote:
> I tracked it down to the MATLAB
> API mxRealloc function, and indeed the behavior changes from R2008a to
> R2008b. In 2008a (and earlier I presume, although I only tested R2007a)
> when a large block is reallocated with mxRealloc the large block is
> freed and a new small block is allocated, thus recovering the extra
> memory. But for R2008b and beyond, the large block remains allocated
> even though only 1 element is requested in the mxRealloc call.

I can see why they might have done this: it might be a performance improvement
strategy for typical code.

If one is creating a logically "new" result, then most of the time one would
allocate a new memory region instead of down-sizing an existing memory region.
Down-sizing an existing memory region would be a characteristic of code that
initializes an array and then dynamically grows the array until it was
finished with it, and then looped back again.

If there is reasonable ground to believe that an array is going through a
repeated initialize-and-grow cycle, then if you shrink the memory allocation
down to the minimum, you risk the possibility that the code is going to have
to do a lot of copying around in order to grow the array as the routine
progresses. Any one particular allocation doesn't hint at how an array is
going to grow (and thus hint at how much consecutive memory should be set
aside for it to avoid having to keep moving the data), but re-allocation does
offer the hint, and the strategy that "if it grew this big before, there's a
good chance it will grow about that big again".

It is, of course, a strategy that fails if you are very tight on memory and
the code is doing something unusual that involves the array staying small
while large temporary objects are created and deleted, with the array suddenly
bursting in size after that... or if you are using the same array to hold
different things at different times, with the initial ones small and the later
ones happening to be large and you preallocate the smaller size instead of the
larger...

Soooo,.. once you have adopted the hypothesis that "a variable that has grown
big once is probably going to grow big again", the cases that break the
hypothesis can start to seem pretty unlikely compared to typical coding.
From: Bruno Luong on 5 May 2010 03:07
"James Tursa" <aclassyguy_with_a_k_not_a_c(a)hotmail.com> wrote in message <hrq3j1$dm$1(a)fred.mathworks.com>...
> In 2008a (and earlier I presume, although I only tested R2007a) when a large block is reallocated with mxRealloc the large block is freed and a new small block is allocated, thus recovering the extra memory. But for R2008b and beyond, the large block remains allocated even though only 1 element is requested in the mxRealloc call.

James, can you explain how you know with certainty the block size hasn't changed after callibng mxRealloc? As I understand, the block size always change, but the returned pointer value can changed or unchanged. The API decides to do whatever the strategy it likes.

If the block *size* hasn't change, then it's a bug. However I would still be prudent before to associate the behavior 0*sparse with this issue, nothing indicates it causes by mxRealloc.

Interesting issue you pick up here.

Bruno
From: James Tursa on 5 May 2010 04:49
"Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hrr5en$i61$1(a)fred.mathworks.com>...
> "James Tursa" <aclassyguy_with_a_k_not_a_c(a)hotmail.com> wrote in message <hrq3j1$dm$1(a)fred.mathworks.com>...
> > In 2008a (and earlier I presume, although I only tested R2007a) when a large block is reallocated with mxRealloc the large block is freed and a new small block is allocated, thus recovering the extra memory. But for R2008b and beyond, the large block remains allocated even though only 1 element is requested in the mxRealloc call.
>
> James, can you explain how you know with certainty the block size hasn't changed after callibng mxRealloc? As I understand, the block size always change, but the returned pointer value can changed or unchanged. The API decides to do whatever the strategy it likes.

Yes, I thought of that. Just because you get back the same pointer from mxRealloc doesn't mean definitively that the block size hasn't changed. The only way I know for sure, and the reason I make the claim, is that my posted script runs out of memory when it shouldn't. The *logical* block size may have changed, i.e. the valid addressable length of the block in C has changed, but the *physical* block size apparently has not changed and no memory is returned to the heap as a result of the mxRealloc call or the 0 * sparse operation.

> If the block *size* hasn't change, then it's a bug. However I would still be prudent before to associate the behavior 0*sparse with this issue, nothing indicates it causes by mxRealloc.

Just an assumption on my part that the intrinsic * operator is calling the same realloc function in the background that mxRealloc does based on the similar behavior. But of course I really have no proof one way or the other. All I really know for sure is that neither of them works as I expected them to, and they both tie up heap memory needlessly.

> Interesting issue you pick up here.

And annoying. I am going to have to recode my sparse matrix C stuff.

James Tursa
From: Bruno Luong on 5 May 2010 07:18
"James Tursa" <aclassyguy_with_a_k_not_a_c(a)hotmail.com> wrote in message <hrrbe0$5kt$1(a)fred.mathworks.com>...
> "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hrr5en$i61$1(a)fred.mathworks.com>...
> > "James Tursa" <aclassyguy_with_a_k_not_a_c(a)hotmail.com> wrote in message <hrq3j1$dm$1(a)fred.mathworks.com>...
> > > In 2008a (and earlier I presume, although I only tested R2007a) when a large block is reallocated with mxRealloc the large block is freed and a new small block is allocated, thus recovering the extra memory. But for R2008b and beyond, the large block remains allocated even though only 1 element is requested in the mxRealloc call.
> >
> > James, can you explain how you know with certainty the block size hasn't changed after callibng mxRealloc? As I understand, the block size always change, but the returned pointer value can changed or unchanged. The API decides to do whatever the strategy it likes.
>
> Yes, I thought of that. Just because you get back the same pointer from mxRealloc doesn't mean definitively that the block size hasn't changed. The only way I know for sure, and the reason I make the claim, is that my posted script runs out of memory when it shouldn't. The *logical* block size may have changed, i.e. the valid addressable length of the block in C has changed, but the *physical* block size apparently has not changed and no memory is returned to the heap as a result of the mxRealloc call or the 0 * sparse operation.

James, I run this code on 2010A/Vista64, and it obviously runs until the end, showing that mxRealloc is functioning. What if you run on your side?

#include "mex.h"

#define MAXTEST 100

void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) {

void *ptr[MAXTEST];
int n;

/* Allocate/Reallocte MAXTEST times */
for (n=0; n<MAXTEST; n++) {
ptr[n] = mxMalloc(1073741824); /* <- 1 Gbytes */
if (!ptr[n]) break;
mexPrintf("Allocate %d times, ptr[%d]=%p\n", n+1, n, ptr[n]);
/* If the following line is removed, 'Out of memory' error will be issued assuming RAM is less than 100 Bbytes*/
ptr[n] = mxRealloc(ptr[n], 1);

}
for (; n--;) {
if (ptr[n]) mxFree(ptr[n]);
}
return;
}

Bruno
 |  Next  |  Last
Pages: 1 2 3
Prev: InitialMagnification is linear?
Next: Need cross-sectional area of non-convex 3D point cloud.