Dynamic allocation of memory problem

[Kazik�]

Hi,
for some reason that I don't understand I have problem with dynamic
allocation of memory. Though I think I did everything correctly, the
amount of RAM used by my application increases when the program is
running and finally the program runs out of memory completely. I have
found the part of the program that is responsible for that but I don't
understand how is it happening- from my perspective everything should
work fine (in the meaning that the usage of memory should be
constant). Here is this part of the code:

for(int k=0; k<Nq; k++){

double** Matrix = init_2_re(2*Nz);

for(int u=0; u<2*Nz; u++){
for(int v=0; v<2*Nz; v++){
Matrix[v] = AllMatrixTerms(2*Nz, u, v, qArray[k], g_ij, gd_ij,
dz, psirX, AnalyticalFrArray, z);
}
}

double* wr = new double[2*Nz];
double* wi = new double[2*Nz];

dgeevCPP(Matrix, 2*Nz, wr, wi);

delete [] Matrix;
delete [] wi;
delete [] wr;

}

The functions that have been used above are:

1)
double** init_2_re(const int n){
double **Matrix = new double*[n];
for(int i=0; i<n; i++)
Matrix = new double[n];
return Matrix;
}

2)
AllMatrixTerms is not important in the context of my problem- if you
put
Matrix[v] = 1.;
it would work exactly the same as using AllMatrixTerms and thus I
don't paste the code for that here.

3)
/
*-----------------------------------------------------------------------------------
* The routine dgeevCPP is a C-like routine for diagonalisation of a
* real-valued, non-symmetric matrix, using FORTRAN-base routine dgeev
* (google "dgeev" for details)
*
* Arguments:
* h- the C-like real-valued non symmetric matrix to be diagonalised.
* n- the order of the matrix h
* wr- an array storing real parts of calculated eigenvalues
* wi- an array storing imaginary parts of calculated eigenvalues

-----------------------------------------------------------------------------------
*/

void dgeevCPP(double** h, int n, double* wr, double* wi)
{
char jobvl = 'N'; //'N'- left eigenvectors of A are not computed
//'V'- left eigenvectors of A are computed
char jobvr = 'N'; //'N'- right eigenvectors of A are not computed
//'V'- right eigenvectors of A are computed

//Here, the matrix h is rewritten into FORTRAN-like array:
double* a = new double[n*n];
for (int j=0; j < n; j++){
for (int i=0; i < n; i++){
a[n*j+i] = h[j];
}
}

int ldvl = 1; // if jobvl='V', ldvl >= n
int ldvr = 1; // if jobvr='V', ldvr >= n
double* vl = new double[ldvl];
double* vr = new double[ldvr];

int lwork = 6*n; // lwork >= max(1,3*N), and if jobvl='V' or
jobvr='V', lwork >= 4*n
double* work = new double[lwork];

int info;

dgeev_(&jobvl, &jobvr, &n, a, &n, wr, wi, vl, &ldvl, vr, &ldvr,
work, &lwork, &info);

delete [] work;
delete [] vl;
delete [] vr;
delete [] a;

}

So, just as I said, the program works fine, but the amount of memory
constantly increases and if I put some large value of Nz, finally the
program crashes. From my point of you I delete everything that I
create, so I really don't understand what's going on.

I would be really grateful if somebody could help me with this stuff.
Thank you in advance,

 

[Victor Bazarov]

for some reason that I don't understand I have problem with dynamic
allocation of memory. Though I think I did everything correctly, the
amount of RAM used by my application increases when the program is
running and finally the program runs out of memory completely. I have
found the part of the program that is responsible for that but I don't
understand how is it happening- from my perspective everything should
work fine (in the meaning that the usage of memory should be
constant). [..]

Please count how many allocations you are making and how many
deallocations. They must match. I believe the main culprit is your
main "matrix".

Dynamic allocation is not as easy as it might seem. That's why there
are containers. See if you can replace your 'double**' with

std::vector<std::vector<double> >

by doing

typedef std::vector<std::vector<double> > Matrix_t;

which will provide the same indexing ability. All you need to do is to
allocate it properly:

Matrix_t Matrix(2*NZ, vector<double>(2*Nz));

That's it. Of course, everywhere you pass Matrix as an argument, you
need to change your interface to accept a reference to Matrix_t.

V

 

[Kazik�]

Thank you Victor,
I know it sounds silly, but yes- I have calculated all "new"'s and
"delete"'s and the numbers match- both in dgeevCPP and in the part of
main() that I have pasted in the previous post. This is something that
makes me really crazy- it must work but it does not...
Talking about STL- I know I should learn them but since now I have to
finish the current project as soon as possible, it's not the most
effective idea to begin STL-education right now.
I suspect what could be the reason for running out of memory. It's
about the way that I initialize the 2-dimensional array, namely by the
function:

double** init_2_re(const int n){
double **Matrix = new double*[n];
for(int i=0; i<n; i++)
Matrix = new double[n];
return Matrix;

}

So, in main() I write:
double** Matrix = init_2_re(2*Nz);
and when playing with Matrix is over:
delete [] Matrix;
Ok, but then I thought: since I don't use word "new" (explicitly in
main()) to initialize the Matrix (though it appears in init_2_re),
maybe "delete [] Matrix" somehow doesn't work or work different then I
think? Is it possible? I'm sorry if it's stupid but I'm really running
out reasonable ideas..

 

[Jerry Coffin]

Hi,
for some reason that I don't understand I have problem with dynamic
allocation of memory. Though I think I did everything correctly, the
amount of RAM used by my application increases when the program is
running and finally the program runs out of memory completely.

That doesn't surprise me. Your new's and delete's need to match, and
they don't.

[ ... ]

for(int k=0; k<Nq; k++){

double** Matrix = init_2_re(2*Nz);

Let's substitute the code for init_2_re inline, and take out the
intervening processing code, and see if it doesn't help make the
problem a bit more apparent.

for (int k=0; k<Nq; i++) {
double **Matrix = new double*[n];
for(int i=0; i<n; i++)
Matrix = new double[n];
// ...

delete [] Matrix;

You're allocating Matrix as an array of n pointers, then iterating
through those pointers, and allocating an array of n doubles for each
to point at -- but when you delete, you only delete the array of
pointers, leaving n arrays of n doubles still allocated, but no
access to them anymore -- i.e. leaked.

There are a couple of ways to deal with this. The most obvious is to
add some code to delete the doubles before you delete the pointers to
them, so just before the 'delete [] Matrix;' above, you'd add
something like:

for (int i=0; i<n; i++)
delete [] Matrix;

At least IMO, that's just treating a symptom though. The real problem
is that what should be relatively simple processing has a bunch of
ugly dynamic allocation and deallocation mixed in, so it's difficult
to follow either one, or have any confidence that it's entirely
correct (without more careful inspection, I'm not entirely sure what
I've given above cures the whole problem).

A much better cure is to encapsulate the dynamic allocation and
deallocation into a class that does nothing else. Put the allocation
in its ctor, and the deallocation in its dtor, and you don't have to
deal with them at all any more. The C++ standard library already
provides std::vector, which can be used for your wi and wr (i.e. for
single-dimension matrices).

For your Matrix (i.e. a two-dimensional matrix) you have a couple of
choices. You can either create a new class specifically for that job,
or you can create a vector of vectors. The latter is closer to what
you're doing right now, but the former can (usually) be made a bit
more efficient. For the moment, I'd just write the code with a vector
of vectors, and deal with optimization later (if necessary):

// Make Matrix an array of n vectors of double:
std::vector<std::vector<double> > Matrix(n);

// Make each element a vector of n doubles:
for (int i=0; i<n; i++)
Matrix.resize(n);

Do the AllMatrixTerms calculation:
for (int u=0; u<2*Nz; u++)
for (int v=0; v<2*Nz; v++)
Matrix[v] = AllMatrixTerms(2*Nz,
u,
v,
qArray[k],
g_ij,
gd_ij,
dz,
psirX,
AnalyticalFrArray,
z);

std::vector<double> wr(2*Nz);
std::vector<double> wi(2*Nz);

dgeevCPP(Matrix, 2*Nz, wr, wi);

Note the compete _lack_ of new or delete in any of the code above --
that's all handled by the code for std::vector itself, so when one
goes out of scope, its associated memory is deleted automatically.

I haven't rewritten the code for dgeevCPP for you, but you should be
able to do so fairly easily based on the code above. You can probably
also make the code substantially more efficient by using a purpose-
built matrix class instead of a vector of vectors. Right now in
dgeevCPP, you allocate a square matrix. You'd probably be better off
allocating Matrix as a single block of n*n doubles to start with, and
using it throughout.

 

[Kazik�]

Wow, thank you so much. You cannot imagine how grateful I am. I should
have noticed that..
So far, I made only the "delete change" that you have suggested and in
deed- the total amount of memory being used is constant now.
Definitely, during the weekend I will start to read about the STL
stuff- I have to admit that it's far more readable and if it does the
job new/delete for me- why not?
Thank you once more

 

[Victor Bazarov]

Thank you Victor,
I know it sounds silly, but yes- I have calculated all "new"'s and
"delete"'s and the numbers match- both in dgeevCPP and in the part of
main() that I have pasted in the previous post. This is something that
makes me really crazy- it must work but it does not...
Talking about STL- I know I should learn them but since now I have to
finish the current project as soon as possible, it's not the most
effective idea to begin STL-education right now.
I suspect what could be the reason for running out of memory. It's
about the way that I initialize the 2-dimensional array, namely by the
function:

double** init_2_re(const int n){
double **Matrix = new double*[n];
for(int i=0; i<n; i++)
Matrix = new double[n];
return Matrix;

}

So, in main() I write:
double** Matrix = init_2_re(2*Nz);
and when playing with Matrix is over:
delete [] Matrix;

That's your problem. How many 'new[]' do you have in the function
'init_2_re'? Count them properly. How many 'delete[]' do you have? One.

Ok, but then I thought: since I don't use word "new" (explicitly in
main()) to initialize the Matrix (though it appears in init_2_re),
maybe "delete [] Matrix" somehow doesn't work or work different then I
think? Is it possible?

No. All uses of 'new' have to be matched with 'delete' to avoid leaks
and all uses of 'new[]' have to be matched with 'delete[]'.

> I'm sorry if it's stupid but I'm really running
out reasonable ideas..

V

 

[Rainer Grimm]

Hallo,
if linux is an option for you, you should have a look at valgrind.
It's a great tool for debugging your programm. Especially for
finding memory leaks.

Greetings Rainer

 

[Richard Herring]

In message

Thank you Victor,
I know it sounds silly, but yes- I have calculated all "new"'s and
"delete"'s and the numbers match- both in dgeevCPP and in the part of
main() that I have pasted in the previous post. This is something that
makes me really crazy- it must work but it does not...
Talking about STL- I know I should learn them but since now I have to
finish the current project as soon as possible, it's not the most
effective idea to begin STL-education right now.

But it is! You don't have to learn the whole of the STL to make use of
std::vector. It's very simple to use and will completely remove the need
for all this analysis of matching news and deletes and new[]s and
delete[]s.

Count up how much time you have wasted already trying to make your code
work. Then look at this:

Instead of this:
double **Matrix = new double*[n];
for(int i=0; i<n; i++)
Matrix = new double[n];

you'd write:

vector<vector<double> > Matrix(n, n);

And instead of scratching your head over how many deletes and whether
they need [] in this:

for (int i=0; i<n; ++i)
delete[] Matrix;
delete[] Matrix;

you'd write

/* nothing at all! */

And you'd refer to the elements in exactly the same way as before:

Matrix[j] = somevalue;
somevar = Matrix[j][k];

(assuming that you have the necessary housekeeping at the top of your
file:

#include <vector>
using std::vector;

)

Job done.

 

[James Kanze]

[...]

Count up how much time you have wasted already trying to make
your code work. Then look at this:

Instead of this:
double **Matrix = new double*[n];
for(int i=0; i<n; i++)
Matrix = new double[n];

you'd write:

vector<vector<double> > Matrix(n, n);

Is this still true? I know that the C++03 standard guarantees
it, but I was under the impression that this was unintentional
(and the current draft seems to have been reworded to ban it).

The correct way of writing this is:

std::vector< std::vector< double > >
matrix( n, std::vector< double >( n ) ) ;

This can be made easier with typedefs.

More reasonably, of course, you'd write a Matrix class, and
never really write anything like the above, except maybe in the
Matrix class. (Also, if you use a Matrix class, you can easily
switch between a vector of vectors, and a one dimensional vector
with calculation of the indices in the class, depending on what
works best for you.) Trying to use a matrix without defining a
class to manage it is his first mistake, regardless of the
structures used to implement it.