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(WallyMatrix, BestMatrix));
		BestMatrix2.setScore(SumOfSquaredDifferences(WallyMatrix, BestMatrix2));
		BestMatrix3.setScore(SumOfSquaredDifferences(WallyMatrix, 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(WallyMatrix, 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

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(WallyMatrix, BestMatrix));
		BestMatrix2.setScore(SumOfSquaredDifferences(WallyMatrix, BestMatrix2));
		BestMatrix3.setScore(SumOfSquaredDifferences(WallyMatrix, 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(WallyMatrix, 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

To copy to clipboard, switch view to plain text mode 

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

#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

To copy to clipboard, switch view to plain text mode 

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

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

To copy to clipboard, switch view to plain text mode 

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));

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

To copy to clipboard, switch view to plain text mode 

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

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

To copy to clipboard, switch view to plain text mode 

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.

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.

To copy to clipboard, switch view to plain text mode 

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
}

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
}

To copy to clipboard, switch view to plain text mode 

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.