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

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.

"James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <hrq3j1$dm$1@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

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hrr5en$i61$1@fred.mathworks.com>...
> "James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <hrq3j1$dm$1@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

"James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <hrrbe0$5kt$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hrr5en$i61$1@fred.mathworks.com>...
> > "James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <hrq3j1$dm$1@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

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hrrk5c$rkh$1@fred.mathworks.com>...
>
> 
> James, I run this code on 2010A/Vista64, and it obviously runs until the end, showing that mxRealloc is functioning. 

I carry out more tests:

Same command fails on 2010A/Vista32, and works with 2006B/Vista32.

So the problem seems to be real, and affects 32-bit OS.

Bruno

I have run the code and track down the pointer address as well as the memory. Here is the code

#include "mex.h"

#define MAXTEST 100

void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) {
    
    void *ptr[MAXTEST];
    int n;
    
    /* Allocate/Reallocate 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 Gbytes*/
        ptr[n] = mxRealloc(ptr[n], 1);
        mexPrintf("     reallocate at ptr[%d] = %p\n", n, ptr[n]);
        mexEvalString("[uV] = memory;");
        mexEvalString("fprintf('Matlab uses %d Mbytes\\n', round(uV.MemUsedMATLAB/1024^2));");        
    }
    for (; n--;) {
        if (ptr[n]) mxFree(ptr[n]);
    }
    
    /* Allocate 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 Gbytes*/
        mexEvalString("[uV] = memory;");
        mexEvalString("fprintf('Matlab uses %d Mbytes\\n', round(uV.MemUsedMATLAB/1024^2));");        
    }
    for (; n--;) {
        if (ptr[n]) mxFree(ptr[n]);
    }
    return;
}

When running on 2010A 64bit,
The output of the first part with reallocation is:

Allocate 1 times, ptr[0] = 0000000080000040
     reallocate at ptr[0] = 0000000080000040
Matlab uses 507 Mbytes
....
Allocate 100 times, ptr[99] = 00000019C0620040
     reallocate at ptr[99] = 00000019C0620040
Matlab uses 508 Mbytes

Note stability of that the memory used Matllab, even the pointer value does not change by reallocation.

----------------------------------------------------------------------------
The output of the first part WITHOUT reallocation is:

Allocate 1 times, ptr[0] = 0000000080000040
Matlab uses 1532 Mbytes
Allocate 2 times, ptr[1] = 00000000C0010040
Matlab uses 2556 Mbytes
Allocate 3 times, ptr[2] = 0000000180010040
Matlab uses 3580 Mbytes
Allocate 4 times, ptr[3] = 00000001C0020040
Matlab uses 4604 Mbytes
Allocate 5 times, ptr[4] = 0000000200030040
Matlab uses 5628 Mbytes
Allocate 6 times, ptr[5] = 0000000240040040
Matlab uses 6652 Mbytes
Allocate 7 times, ptr[6] = 0000000280050040
Matlab uses 7676 Mbytes
Allocate 8 times, ptr[7] = 00000002C0060040
Matlab uses 8700 Mbytes
Allocate 9 times, ptr[8] = 0000000300070040
Matlab uses 9724 Mbytes
Allocate 10 times, ptr[9] = 0000000340080040
Matlab uses 10748 Mbytes
Allocate 11 times, ptr[10] = 0000000380090040
Matlab uses 11772 Mbytes
Allocate 12 times, ptr[11] = 00000003C00A0040
Matlab uses 12796 Mbytes
Allocate 13 times, ptr[12] = 00000004000B0040
Matlab uses 13820 Mbytes
Allocate 14 times, ptr[13] = 00000004400C0040
Matlab uses 14844 Mbytes
Allocate 15 times, ptr[14] = 00000004800D0040
Matlab uses 15868 Mbytes
??? Error using ==> testrealloc
Out of memory. Type HELP MEMORY for your options.
 
The memory used Matllab increases until it crashes.

Bruno

I makes similar test on 2010A/32 bit Vista and the mxRealloc() doesn't free the memory. My conclusion: it is buggy on 32-bit OS, but works fine on 64 bit OS.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hrs9jk$iqe$1@fred.mathworks.com>...
> I makes similar test on 2010A/32 bit Vista and the mxRealloc() doesn't free the memory. My conclusion: it is buggy on 32-bit OS, but works fine on 64 bit OS.

I don't have a 64-bit system to test with, but I also consider the 32-bit behavior a bug, although I will admit I don't know exactly what the C standard says is required behavior for realloc calls with regards to returning memory to the heap. Maybe a post to the C newsgroup is in order.  In any event, I went ahead and submitted a bug report to TMW.

James Tursa

The problem seems to be even stranger.
I use R2010 and Win 7 x64.
If I run the first example

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

I loose no memory, even when I use mtimesx.
On the other hand, if I make A more sparse, e.g.

A = sprand(10000,100000,0.001);

then mtimesx will make me loose approx. 70 MB whereas Matlab's mtimes works flawlessly. 

So the problem is not restricted to x32 but less severe there.

Well, of course I wanted to say that the problem is more serious on x32 than on x64.

"Roland Kruse" <roland.kruse@uni-oldenburg.de> wrote in message <hru03c$dh9$1@fred.mathworks.com>...
> The problem seems to be even stranger.
> I use R2010 and Win 7 x64.
> If I run the first example
> 
> A = sprand(10000,10000,0.1);
> C = cell(1,100);
> for k=1:100; C{k} = 0*A; end
> clear
> 
> I loose no memory, even when I use mtimesx.
> On the other hand, if I make A more sparse, e.g.
> 
> A = sprand(10000,100000,0.001);
> 

But 10 times larger, the number of column is 1 billion and not 10 thousands.

The number of buffer allocated for non zeros elements in sparse is proportional to the matrix size.

Bruno

You may have noticed that I used "clear" to delete all variables. Even though, during each run of the program I loose ~ 70 MB till I'm out of memory. This is certainly not the correct behaviour. 
Strangely, if I set A =
sprand(100000,10000,0.001) instead of 
sprand(10000,100000,0.001), A uses still the same amount of memory but I "loose" only about 8 MB.
Interestingly, this is about the size of C which is 80 MB in the first case and 8 MB in the second case, even though A has the same number of elements. And C has been cleared but the memory is still allocated.