C++ Memory Leak?

[dannyhodge]

Hey guys, so I've been working on my assignment and i'm pretty happy with it, but I've had a pretty massive problem with a memory leak (I had to limit a for loop because otherwise it was passing 2GB and just stopped running).

I've spoken to my lecturer who will be marking this, and this was a problem he was fine helping me with (so i'm not breaching any sole work rules, don't worry), but even he had no idea where I was going wrong. I'm hoping someone here can save me (based on past experience, they will, and his name will be carnage. Much love <3).

I'm really hoping I'm just declaring my Matrix objects incorrectly, but I thought that the way i've done it meant that it was overriding them, instead of creating more.

So the loop that contains the memory leak(sorry this is so long):


int i = 768;
int j = 1024;

int startRow = 0;
int endRow = 49;
int startCol = 0;
int endCol = 36;

Matrix SceneMatrix(i, j, input_data); //Matrix of cluttered_scene
Matrix WallyMatrix(49, 36, wally_data); //Matrix of wally

Matrix BestMatrix = SceneMatrix.getBlock(startRow, endRow, startCol, endCol); //Matrix to contain the best result that matches wally, based on a subset of SceneMatrix
Matrix BestMatrix2 = BestMatrix; //Set to same details as BestMatrix(Copy constructer runs here)
Matrix BestMatrix3 = BestMatrix; //Set to same details as BestMatrix(Copy constructer runs here)

if (ans == 1) { //If SSD
BestMatrix.setScore(SumOfSquaredDifferences(WallyM atrix, BestMatrix));
BestMatrix2.setScore(SumOfSquaredDifferences(Wally Matrix, BestMatrix2));
BestMatrix3.setScore(SumOfSquaredDifferences(Wally Matrix, BestMatrix3));

}

int corrStartRow = 0; //Pos of best option
int corrEndRow = 0;
int corrStartCol = 0;
int corrEndCol = 0;

int corrStartRow2 = 0; //Pos of second best option
int corrEndRow2 = 0;
int corrStartCol2 = 0;
int corrEndCol2 = 0;

int corrStartRow3 = 0; //Pos of third best option
int corrEndRow3 = 0;
int corrStartCol3 = 0;
int corrEndCol3 = 0;

double moveValue = 6; //Amount that the scanner will shift each iteration

for (endRow; endRow < (i - 49); endRow += moveValue, startRow+= moveValue) { //Loop through each row

for (endCol; endCol < (j - 36); endCol += moveValue, startCol += moveValue) { //Loop through each column


Matrix TestMatrix = SceneMatrix.getBlock(startRow, endRow, startCol, endCol); //Matrix that will be tested against current best matrix

if (ans == 1) { //If SSD
TestMatrix.setScore(SumOfSquaredDifferences(WallyM atrix, TestMatrix)); //Test score using SSD
}

if (ans == 1) { //If SSD
if (TestMatrix.getScore() < BestMatrix.getScore()) { //Best option

BestMatrix = TestMatrix; //Set BestMatrix and a set of coords to the test matrix, as this is better than the previous BestMatrix
corrStartRow = startRow; //Coords to be used when drawing rectangle
corrEndRow = endRow;
corrStartCol = startCol;
corrEndCol = endCol;

}

} //end if ans == 1 (SSD)

} //End for loop of columns
endCol = 36; //Move to next row
startCol = 0;

} //End for loop of rows


And the Matrix Class:

#pragma once

class Matrix { //This matrix class allows me to make a new object for each matrix I need

public: //Allows anything that is public to be accessed (e.g. matrix1.getBlock)


Matrix(int sizeR, int sizeC, double input_data[]); //Class constructer
~Matrix(); //Class Destructer
Matrix getBlock(int startRow, int endRow, int startCol, int endCol); //Function which takes a limit in terms of columns and rows, and returns the Matrix inside it
double* Matrix::getMatrixVals(); //Function which returns the data array in a matrix
double getScore(); //Function which returns the score variable (as it is private and cannot otherwise be accessed outside of the scope of the Matrix class)
void setScore(double Score); //Function which sets the score variable
int* getSceneVals(); //Function which returns the indexes that the new matrix occupied in its larger matrix (where the 36 x 49 matrix existed in terms of position inside the 1024 x 768 matrix)
Matrix(const Matrix& e); //Copy Constructer



private: //Can't be accessed outside of Matrix class
int M, N; //Amount of rows and columns in the matrix
double *data; //The data read into the matrix
double *newData; //The new set of data, taken out of the data variable, based on the getBlock function
double score; //The score, assigned by either the Sum of Squared Differences function, or the Normalized Correlation function
int* posInScene; //An array which contains the indexes that the new matrix occupied in its larger matrix (where the 36 x 49 matrix existed in terms of position inside the 1024 x 768 matrix)
//To be used for putting a square around wally
};

Matrix::Matrix(int sizeR, int sizeC, double input_data[]) { //The Class Constructer (runs whenever a new Matrix object is created)

M = sizeR; //M = height
N = sizeC; //N = width


data = new double[M*N]; //Sets the total space of the data array
newData = new double[36*49]; //Sets the total space of the new data array
posInScene = new int[36*49]; //Sets the total space of the position in scene array

for (int ii = 0; ii < M*N; ii++) { //Loops through the rows * columns of the matrix, to add the data read into the function to the data function
data[ii] = input_data[ii]; //Adding each value in the data array, one by one
}
}


Matrix::~Matrix() { //The class destructer, which runs every time a matrix is deleted (included when it is passed through a function as a reference)


} //End of class destructer



Matrix Matrix::getBlock(int startRow, int endRow, int startCol, int endCol) { //Function which returns a Matrix based on a start/end row/column



int currentCol = startCol;
int currentRow = startRow; //Temporary variables used to retain value of start row/start column
int counter = 0;


for (currentRow; currentRow < endRow; currentRow++) {

for (currentCol; currentCol < endCol; currentCol++) { //The nested for loop means this will run endCol * endRow times (in this case, 36 * 49 times)

newData[counter] = data[(currentRow * N) + currentCol]; //This formula will set each value of new data as the value of the matrix, as if it were a 2d matrix, using the formula (currentRow * N) + currentCol, using the values passed through the function
posInScene[counter] = (currentRow * N) + currentCol; //This will store the position that each value of newData had inside data, for future reference, like when identifying wally in the cluttered_scene image
counter++; //Incrementing the counter
} //End of the currentCol for loop
currentCol = startCol; //After finishing a row, this moves onto the next one
} //End of the currentRow for loop

Matrix NewMatrix(endRow - startRow, endCol - startCol, newData); //The matrix that will be returned as the subset of the original matrix

return NewMatrix;
} //End getBlock function

Matrix::Matrix(const Matrix& e) { //Copy Constructer

M = e.M;
N = e.N;
data = e.data;
newData = e.newData;
score = e.score;
posInScene = e.posInScene; ///Whenever a Matrix is copied, each of these variables is set to what it was
} //End copy constructer


double* Matrix::getMatrixVals() { //Function which returns the values in the data array

double* matrixVals; //Declaring the array

int size = M * N;

matrixVals = new double[size]; ///Declares the size of the array


for (int i = 0; i < size; i++) { //Loops through as many values as there are in the matrix

matrixVals[i] = data[i]; //Replacing every value of the array as it goes
}

return matrixVals; //Returning a double array
} //End of the getmatrixvals function



Thanks a lot,
Danny

*I had to remove some variables and stuff to get this post to fit, but don't worry, referencing variables that aren't here isn't the problem, it compiles perfectly*

[Lesiok]

In Matrix constructor You create 3 arrays wit operator new. You should delete them in Matrix destructor.

[d_stranz]

but even he had no idea where I was going wrong.

He couldn't find an error this obvious? Wow. The very first thing you look for when you have a program that grows without bounds is unmatched new / delete pairs.

By the way, as soon as you fix the memory leak, your program is likely to start crashing. You are allocating memory (via operator new()) in the Matrix constructor. You have incorrectly implemented a copy constructor and have not implemented an assignment operator for your Matrix class. The compiler will generate the assignment operator for you, but unfortunately this will make a bitwise copy of the contents of the class instance. In your case, it will copy the pointers to the arrays, not the arrays themselves. This means that as soon as the first Matrix instance goes out of scope, all of the other Matrix instances you have created via assignment or copy constructors will be left holding pointers to deleted arrays. When one of these copies tries to access the array, it will crash.

One solution is to correctly implement a copy constructor (Matrix( const Matrix & rhs )) and assignment operator (const Matrix & operator=( const Matrix & rhs ) ). In each of these, you must create new arrays and copy the arrays held by "rhs" (right-hand side) into them. In the assignment operator, you should also protect against self assignment by checking &rhs != this first.

The alternative solution to all this manual copying is to use std::vector< double > or std::vector< int > (or their QVector counterparts) to hold your array data. These do not need to be allocated with operator new(), do not need to be manually deleted in the destructor, and can be treated as ordinary arrays in algorithms. You will also not need to implement a copy constructor or assignment operator, since a bitwise copy of the class will make copies of the vectors and their contents too.

[anda_skoa]

I can only guess but if your lecturer didn't spot the cross mismatch between allocating memory in the constructor and not releasing it in the destructor then this is a lecture in Mathematics or Physics, not Software engineering or Computer Science, right?

And I totally agree with d_stranz: vectors!
No point in trying to manually get all the manual memory handling issues fixed if you can avoid them alltogether.

Cheers,
_

[dannyhodge]

Sorry, i didn't have space to mention, but i'd tried deleting everything in my deconstructor, but that just caused a load more errors, so I assumed i was going in the wrong direction. I'll try your solutions, thanks!

[dannyhodge]

Okay, i've implemented vectors, and as much as i think it's working, it's taking an enormous amount of time to go through my for loops... Is that normal?
This is my implementation of one of the functions. Please bare in mind that this function runs on 800,000 values in data:



std::vector<double> Matrix::getMatrixVals() { //Function which returns the values in the data vector
std::cout << "4" << std::endl;
std::vector<double> matrixVals; //Declaring the vector

int size = M * N;

matrixVals = std::vector<double>(M*N);


for (int i = 0; i < size; i++) { //Loops through as many values as there are in the matrix
matrixVals[i] = data[i]; //Replacing every value of the vector as it goes
}

return matrixVals; //Returning a double array
} //End of the getmatrixvals function


Edit** Using .resize() has improved performance, but overall this still takes a good few minutes(i've not had chance to see it run to the end yet). Clearly something else is wrong.

[anda_skoa]

Vectors are basically just wrappers around arrays, a way to make copying and memory handling easier.

You can even retrieve the underlying array with the data() method if you want to try looping over that or using things like memcpy.
e.g.


memcpy(matrixVals.data(), &data, size * sizeof(double));


Cheers,
_

[d_stranz]

it's taking an enormous amount of time to go through my for loops

Well for one thing it looks like you are unnecessarily making copies of arrays. In your "getMatrixVals" method, you could simply rewrite it as:



const std::vector<double> & Matrix::getMatrixVals() const { //Function which returns the values in the data vector
std::cout << "4" << std::endl;
return data;
} //End of the getmatrixvals function


Why? Because you are using vectors to store your data, there is no need to make a copy of it for return. You can simply return a reference to the member variable. Because it is declared as a const vector, the caller can't modify it, and because it is a const method, the compiler knows that the class instance won't be modified so it can optimize a bit better.

Your caller gets back a const reference to a vector. It can either assign that to a const vector reference (in which case no copying is done) or assign it to a vector variable, in which case a copy is made. The caller determines when the copy is made, not the Matrix class.



const std::vector< double > & noCopy = myMatrix.getMatrixVals(); // doesn't make a copy of "data"
std::vector< double > copy = myMatrix.getMatrixVals(); // makes a copy

// from here onward, the usage is identical, except that "copy" can change the values in the vector, but "noCopy" can't.
// "copy" has its own version of the data, which it is free to modify without any change to the data in myMatrix.


You can probably find other places in your code where these copies are being made, only to be thrown away. The rules of thumb are, whenever a method does not modify the information stored in the class instance, declare the function as "const", use std::vector<> or other container classes from the STL rather than raw C++ arrays wherever possible, and return references to the data whenever possible instead of making copies.


it's taking an enormous amount of time to go through my for loops

We did some performance testing a while back, using Microsoft VC++ on Windows. We found that using STL iterators was up to an order of magnitude slower than using operator[]() on vectors, and that operator[]() was slower than using pointers, but not by a lot, maybe a factor of two:



std::vector< double > myVector( 100000, 42.0 );

// Slowest, by 10x
std::vector< double >::iterator it = myVector.begin();
std::vector< double >::iterator eit = myVector.end();
while ( it != eit )
{
double v = *it;
// do something with v
it++;
}

// Fast
long nPts = myVector.size();
for ( long nPt = 0; nPt < nPts; ++nPt )
{
double v = myVector[ nPt ];
// do something with v
}

// Fastest
double * pV = &(myVector[0]);
for ( long nPt = 0; nPt < nPts; ++nPt, pV++ )
{
double v = *pV;
// do something with v
}


You can do the last loop because the STL guarantees that std::vector elements occupy contiguous memory, in the same way as if you had used operator new[]() to allocate a C++ array.