Memory Leak

dannyhodge (4)
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'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): 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
	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)

	

	int ans = 0;

	cout << "Would you like to use the Sum Of Squared Differences(1) to find Wally, or Normalized Correlation(2)?" << endl;

	cin >> ans;

	if (ans == 1) {                                                                        //If SSD
		BestMatrix.setScore(SumOfSquaredDifferences(WallyMatrix, BestMatrix));
		BestMatrix2.setScore(SumOfSquaredDifferences(WallyMatrix, BestMatrix2));
		BestMatrix3.setScore(SumOfSquaredDifferences(WallyMatrix, BestMatrix3));

	}
	else if(ans == 2) {                                                                    //If NC
		BestMatrix.setScore(NormalisedCorrelation(WallyMatrix, BestMatrix));
		BestMatrix2.setScore(NormalisedCorrelation(WallyMatrix, BestMatrix2));
		BestMatrix3.setScore(NormalisedCorrelation(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
			  }
			  else if (ans == 2) {    //If NC
				  TestMatrix.setScore(NormalisedCorrelation(WallyMatrix, TestMatrix));  //Test score using NC
			  }

			  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;

				  }
				  else if(TestMatrix.getScore() < BestMatrix2.getScore()) {   //Second best option

				  BestMatrix2 = TestMatrix;      //Set BestMatrix2 and a set of coords to the test matrix, as this is better than the previous BestMatrix2
				  corrStartRow2 = startRow;      //Coords to be used when drawing rectangle
				  corrEndRow2 = endRow;
				  corrStartCol2 = startCol;
				  corrEndCol2 = endCol;

				  } 
				  else if (TestMatrix.getScore() < BestMatrix3.getScore()) {   //Third best option

					  BestMatrix3 = TestMatrix;   //Set BestMatrix3 and a set of coords to the test matrix, as this is better than the previous BestMatrix3
					  corrStartRow3 = startRow;   //Coords to be used when drawing rectangle
					  corrEndRow3 = endRow;
					  corrStartCol3 = startCol;
					  corrEndCol3 = endCol;

				  }

			}   //end if ans == 1 (SSD)
			   else if (ans == 2) {										//If NC
				  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;

				  }
				  else if (TestMatrix.getScore() > BestMatrix2.getScore()) { //Second best option

					  BestMatrix2 = TestMatrix;   //Set BestMatrix2 and a set of coords to the test matrix, as this is better than the previous BestMatrix2
					  corrStartRow2 = startRow;   //Coords to be used when drawing rectangle
					  corrEndRow2 = endRow;
					  corrStartCol2 = startCol;
					  corrEndCol2 = endCol;

				  }
				  else if (TestMatrix.getScore() > BestMatrix3.getScore()) {  //Third best option

					  BestMatrix3 = TestMatrix;    //Set BestMatrix3 and a set of coords to the test matrix, as this is better than the previous BestMatrix3
					  corrStartRow3 = startRow;    //Coords to be used when drawing rectangle
					  corrEndRow3 = endRow;
					  corrStartCol3 = startCol;
					  corrEndCol3 = endCol;

				  }
			  }  //End if ans == 2(NC)
			  
		}   //End for loop of columns
		endCol = 36;  //Move to next row
		startCol = 0;
		
	}  //End for loop of rows


Any suggestions would be fantastic, i'm a little dumbfounded. Oh, and if you're confused about variable names, the assignment was to make a program that can find wally in a scene :p

Thanks a lot,
Danny
Last edited on
dannyhodge (4)
Oh, and the matrix class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
#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


I'm pretty sure the problem is in the getBlock line in the for loop, but i'm not sure why
Chervil (7320)
I don't see anywhere in the code of the first post code that there is any memory allocation or deletion.

Though this may be the code which triggers the problem, the code responsible seems to be elsewhere.

edit:

Only just noticed the second post - not looked at that yet.
Last edited on
Chervil (7320)
The destructor is empty - it should have matching delete [] corresponding to each new [].

The copy constructor can simply assign simple values such as integers, these are ok
1
2
3
 
    M          = e.M;
    N          = e.N;
    score    = e.score;


But the others are pointers. You need to allocate memory of the required size using new, and use a loop to copy in the corresponding data.

Or of course, just use std::vector instead of doing all the memory handling yourself.

See also
https://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)
Last edited on
dannyhodge (4)
So I gave Vectors a go, but now my program is unbearably slow. Please bear in mind that I'm looping through thousands of values at a time (which was still pretty rapid when using Arrays). Any ideas what I did wrong? This is one of my functions with the implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
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
Last edited on
Chervil (7320)
Yes, it did occur to me that the original code, though not perfect, might be pretty fast where it was simply copying pointers. The question though was whether it was appropriate to do that.

There may be some optimisations possible in the vector code.

For example, your getMatrixVals() function above, might be written like this:
1
2
3
4
 
std::vector<double> Matrix::getMatrixVals() 
{   
    return data;
}


Or possibly, if you can take advantage of it, write it like this:
1
2
3
4
 
void Matrix::getMatrixVals(std::vector<double>& result)
{
    result = data;
}

That last version should be faster if the vector passed by reference as the parameter result is declared outside of any loop - if that is feasible.

There might be other parts of the code which could be modified too.

There is also something I'm not really familiar with, which is the fairly recent C++11 feature to move rather than copy - where that would make sense. (It may not apply).

dannyhodge (4)
Yeah I noticed that too, not sure what I was thinking there.

Okay, this is interesting. I've removed every single loop to test performance, and it still takes a hell of a long time to run these functions (the for loop in main takes 15 seconds to run one row, and that should be going up in increments of 1 until it hits 768, so you do that math).

So what could be making this take that long? This stuff is running from the line:
Matrix TestMatrix = SceneMatrix.getBlock(startRow, endRow, startCol, endCol);

That is 100% the line making everything slow, because of what's going on in my matrix class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
#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, std::vector<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
	std::vector<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
	std::vector<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
//	Matrix& operator= (const Matrix& m);

private:                                //Can't be accessed outside of Matrix class
	int M, N;                           //Amount of rows and columns in the matrix
	std::vector<double> data;
	std::vector<double> newData;
	std::vector<int> posInScene;//The data read into the matrix
                  //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
                 
                            
};

Matrix::Matrix(int sizeR, int sizeC, std::vector<double> input_data) {  //The Class Constructer (runs whenever a new Matrix object is created)

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

	 
	 data.resize(M*N);
	

} 


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


}                    //End of class destructor


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;

	
	newData.resize(M*N);


	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.resize(M*N);


	score = e.score;


} //End copy constructer

std::vector<double> Matrix::getMatrixVals() {   //Function which returns the values in the data vector

	return data;               
}  //End of the getmatrixvals function


Chervil (7320)
I'm looking at a few parts of the code and I'm not sure I quite get it - but it may not be the code, it's probably that I need a break. I'll try to get back to this later (tomorrow, most likely).
Hydranix (21)
Your biggest problem is the way you're passing parameters to your functions. There are other fatal problems, but this one is going to cause your stack to each it's limit when you have nested for loops like you do.

Your constructor should be:
Matrix::Matrix(int sizeR, int sizeC, const std::vector<double>& input_data)

or

Matrix::Matrix(int sizeR, int sizeC, std::vector<double>* input_data)

In the second case, you will be dealing with a pointer, which is more complex, and care must be taken not to dereference a null pointer, so i recommend for ease of use, the first example.

Using a const std::vector<double>& will protect the vector from modification within the function it's passed to.

By using a reference of the vector, you won't be copying all of the data in each function call (in your posted code you're not even using the data in the first place anyway).


Next thing. This will copy the data when returned, which may or may not be what you intend, especially if these matrices ever become very large (think hundreds or thousands of row/cols which would take minutes to hours to complete the nested for loops).

std::vector<double> Matrix::getMatrixVals()

You might consider this instead, but it is ultimately up to what exactly you intend to do.

const std::vector<double>& Matrix::getMatrixVals() const



Now the next issue.

When you resize your data vector, you initialize it with garbage, and never actually assign any real data to it. Then you proceed to read the indeterminate data in the vector by copying it as parameters to subsequent function calls. This is undefined behavior which should immediately fail an assignment.

instead of calling

data.resize(M*N);

just use:

1
2
 
data.reserve(input_data.size());
data.assign(input_data.begin(), input_data.end());


That will assign the data to the data vector and with the call to reserve() should do it as quickly as possible, though the reserve() is probably already done internally by the STL.


This line here is whats actually slowing down your for loops due to the reasons I explained above:

Matrix NewMatrix(endRow - startRow, endCol - startCol, newData);

By making a few changes inspired by my examples above, you should have less issues with the slow for loops. There are other things wrong with your code, but if i tried to cover them all in one post it would end up a huge mess as I'm not a very good teacher.
Last edited on
Topic archived. No new replies allowed.