Help with unhandled exception error (access writing location)

[v_janssens]

I'm running a structural analysis program in VS2010 which iterates through a loop up to 4000 times. The program keeps breaking on me around the 960th loop and gives the following error

Unhandled exception at 0x0040cd1d in Structural Analysis Program.exe: 0xC000005: Access violation writing location 0x00000000.

The error seems to come back to the following function each time

Matrix2D getTranspose(Matrix2D a)
{
	Matrix2D transpose = Matrix2D(a.getNumColumns(), a.getNumRows());

	for(int i=1; i<=a.getNumRows(); i++)
	{
		for(int j=1; j<=a.getNumColumns(); j++)
		{
			transpose.setElement(j, i, a.getElement(i, j));
		}
	}

	return transpose;
}

This is defined as a function in Matrix2D.cpp which also contains the function definitions for the class Matrix2D (the function declarations are contained in Matrix2D.h following the class declaration), where Matrix2D is an array defined by the following constructor.

Matrix2D::Matrix2D(int n_rows, int n_columns)
{
	r = n_rows;
	c = n_columns;

	elements = (double**) malloc((r+1)*sizeof(double));

	for (int i=0; i<=(r-1); i++)
	{
		elements[i] = (double*) malloc((c+1)*sizeof(double));
	}

	for(int i=0; i<=(r-1); i++)
	{
		for(int j=0; j<=(c-1); j++)
		{
			elements [i][j] = 0.0;
		}
	}
}

I hope there's enough information here for somebody to help me. I've very limited experience programming and can't get my head around this.

Thanks in advance.

[daviddoria]

Are you deleting the memory you are allocating with malloc? Depending on how big these matrices are, maybe you are running out of memory? Do you need to keep each of these 4000 matrices? Or just use it and then discard it?

[v_janssens]

I haven't been deleting any of them so that's probably likely. Is there any way I can check if I'm running out of memory?

[v_janssens]

Ok, I think a memory problem is likely but I'm a bit unsure about where I can use delete. For example in the getTranpose() function above should there be a delete? I'm returning the matrix though? I've a large number of pretty big matrices (up to 3000*3000) which describe a building so I can analyse it. But I need these throughout the analysis so can't delete them. I wonder is it the fact I'm calling functions like getTranspose() multiple times in each loop thats eating up the memory!

If you could elaborate or point me in the direction of further information that'd be great.

Thanks

[daviddoria]

I think you should verify that it is indeed an "out of memory" before we look into it too far. I can't give you exact instructions because I'm on linux at the moment, but I believe if you open the task manager there should be some plots/statistics about cpu/memory usage. I'd leave that open while you run the program and if it goes up and up and up and gets to the top and then crashes then you've found the problem :)

[v_janssens]

Bad news, I ran the program with the task manager open and the CPU/memory usage peaks when the program starts up but it drops off slowly as the program runs and there's no obvious peak when the error arises.

I'm now running it on a smaller, slower computer and the error is occuring after about the 450th loop if that's of any use?

[v_janssens]

Tried again with a smaller building and it was easier to see what's going on (it wasn't as close to using all of the memory when it started up). This building (which would use less memory than the previous) allows me to run more loops and the physical memory usage gradually increases in task manager as it runs. It peaks about 90-95% and then drops of a few percent after which the program returns the error...

Maybe it is a memory leak after all? The gradual increase in physical memory use does sound suspicious.

[daviddoria]

Yea if its getting to 95% right before it crashes that is definitely an "out of memory".

[v_janssens]

Any ideas? If it's an out of memory problem I've just supassed any programming knowledge I might have :)

[daviddoria]

You'll have to provide more information. Do you really need to store all 1000 of these 3000x3000 matrices? If so, then you're just out of luck :). Give us an explanation of the algorithm.

[v_janssens]

It's a structural analysis program similar to the packages used regularly by structural engineers (its a finite element program if that rings any bells!!). These packages are capable of studying buildings much bigger than what I'm looking at so I don't know why I'm having memory problems. I'm sure it's a rookie mistake, the fun is to find it.

The program consists of a series of classes, which are all subclasses of each other and I've a feeling that's where I'm running into the problem. Starting with main() as the absolute parent the classes are linked as follows:
main() - structuralanalysis() - drawstructure() - structure() - load() - element() - node() - Matrix2D()
Each class contains maybe 15/20 large matrices (100x4000) and a handful of smaller matrices (maybe 6 6x6 matrices and 6 1x6 matrices) the structure I am running has
1 instance of structuralanalysis
1 instance of drawstructure
1 instance of structure
8 instances of load
18 instances of element
15 instances of node
These matrices are generally being reused with each timestep though so besides the initial memory allocated to them I can't see why they would cause the memory to keep increasing.

If I understand what's going on here correctly there must be some (or many) variable/matrix in the program that is being reallocated memory on each loop. For instance, the getTranspose routine is being called quite reqularly. Could the way I have defined a new Matrix2D to store the transpose be the reason for this? Am I correct in how I have interpretted the gradual increase in memory usage.

Sorry for all the questions and I hope this makes sense. The program is quite simple in c++ terms, but is complicated to explain.

[mike_2000_17]

First, the way that you can test whether you have run out of memory in the program is to check that the pointer you get from malloc is not NULL. This pointer will be NULL if you are out-of-memory. This is also why you get the error of dereferencing a NULL pointer (access violation).

Second, memory issues are hard to solve with limited knowledge and experience, but they are even more problematic when using C-style arrays (and with malloc). You should definitely switch to std::vector storage instead. And for you matrices, store them in one contiguous memory block (not array of arrays, but one big array). With this changes, your constructor of Matrix2D would be as such:

// assuming that elements was declared as: std::vector<double> elements;

Matrix2D::Matrix2D(int n_rows, int n_columns)
{
	r = n_rows;
	c = n_columns;

	elements.resize(r * c);
        
        for(int i=0; i < r; ++i)
	{
		for(int j=0; j < c; ++j)
		{
			elements[i * c + j] = 0.0; //map the indices as so.
		}
	}
}

With the above changes, you won't need to worry about clean-up (deallocating memory), because the std::vector object will take care of that. Similarly, the copy-constructor and assignment operator are also automatic deep-copies and won't leak.

Finally, if your matrices are large, you really need to make sure that copying is minimal (i.e. don't copy matrices around all the time). Your "transpose" function is extremely wasteful (at least if the compiler isn't really good at optimizing, which it is not, because the MSVC compiler is renowned for producing poorly-optimized code). Here is what I mean by wasteful: first, you are passing the matrix by value to the function which means that the caller's matrix will get copied before it is passed; second, you are creating a local matrix to store the transpose which is unecessary; then, that local matrix gets copied to the return value; and finally, the returned matrix is copied into whatever matrix the caller is storing the result in. Of course, the last one or two copies will probably be optimized away by the compiler, but still. A much better approach is to pass the input matrix by reference to the function and also passing by reference a matrix in which to store the transposed matrix. This way you have no copying at all, a much reduced chance of memory leaks, and a much faster execution:

void getTranspose(const Matrix2D& a, Matrix2D& transpose)
{
	transpose.setSize(a.getNumColumns(), a.getNumRows()); //I made that function up, but you get the idea.

        //BTW, it is a very bad idea to mix 0-based indexing that C++ uses with 1-based indexing.. stay consistent with the language's conventions.
	for(int i=1; i<=a.getNumRows(); i++)
	{
		for(int j=1; j<=a.getNumColumns(); j++)
		{
			transpose.setElement(j, i, a.getElement(i, j));
		}
	}
        //no need to return anything because transpose will store the output.
}

[mike_2000_17]

For an FEA software, I highly recommend that you pick an off-the-shelf library for the matrix operations and numerical methods. These are not things that are trivial to code and produce efficient and lean implementations of. Furthermore, you really need a sparse matrix library, because FEA matrices are very often extremely sparse and running full-matrix operations on them is just very very wasteful. But, of course, good sparse matrix libraries are even harder to find.

[v_janssens]

For an FEA software, I highly recommend that you pick an off-the-shelf library for the matrix operations and numerical methods. These are not things that are trivial to code and produce efficient and lean implementations of. Furthermore, you really need a sparse matrix library, because FEA matrices are very often extremely sparse and running full-matrix operations on them is just very very wasteful. But, of course, good sparse matrix libraries are even harder to find.

Thanks Mike_2000_17 for your really detailed reply. I've to do some reading up on your comments but I understand the basis of where your coming from. Fingers crossed this works, I'll keep you posted :)

[v_janssens]

First, the way that you can test whether you have run out of memory in the program is to check that the pointer you get from malloc is not NULL. This pointer will be NULL if you are out-of-memory. This is also why you get the error of dereferencing a NULL pointer (access violation).

Second, memory issues are hard to solve with limited knowledge and experience, but they are even more problematic when using C-style arrays (and with malloc). You should definitely switch to std::vector storage instead. And for you matrices, store them in one contiguous memory block (not array of arrays, but one big array). With this changes, your constructor of Matrix2D would be as such:

// assuming that elements was declared as: std::vector<double> elements;

Matrix2D::Matrix2D(int n_rows, int n_columns)
{
	r = n_rows;
	c = n_columns;

	elements.resize(r * c);
        
        for(int i=0; i < r; ++i)
	{
		for(int j=0; j < c; ++j)
		{
			elements[i * c + j] = 0.0; //map the indices as so.
		}
	}
}

With the above changes, you won't need to worry about clean-up (deallocating memory), because the std::vector object will take care of that. Similarly, the copy-constructor and assignment operator are also automatic deep-copies and won't leak.

Finally, if your matrices are large, you really need to make sure that copying is minimal (i.e. don't copy matrices around all the time). Your "transpose" function is extremely wasteful (at least if the compiler isn't really good at optimizing, which it is not, because the MSVC compiler is renowned for producing poorly-optimized code). Here is what I mean by wasteful: first, you are passing the matrix by value to the function which means that the caller's matrix will get copied before it is passed; second, you are creating a local matrix to store the transpose which is unecessary; then, that local matrix gets copied to the return value; and finally, the returned matrix is copied into whatever matrix the caller is storing the result in. Of course, the last one or two copies will probably be optimized away by the compiler, but still. A much better approach is to pass the input matrix by reference to the function and also passing by reference a matrix in which to store the transposed matrix. This way you have no copying at all, a much reduced chance of memory leaks, and a much faster execution:

void getTranspose(const Matrix2D& a, Matrix2D& transpose)
{
	transpose.setSize(a.getNumColumns(), a.getNumRows()); //I made that function up, but you get the idea.

        //BTW, it is a very bad idea to mix 0-based indexing that C++ uses with 1-based indexing.. stay consistent with the language's conventions.
	for(int i=1; i<=a.getNumRows(); i++)
	{
		for(int j=1; j<=a.getNumColumns(); j++)
		{
			transpose.setElement(j, i, a.getElement(i, j));
		}
	}
        //no need to return anything because transpose will store the output.
}

I'm slowly integrating your comments and so far things are looking hopeful. I haven't run a full analysis yet but the smaller routines seem to be a lot faster.

I was just wondering why you passed const Matrix2D& a as the first variable in your version of getTranspose()? Does the const mean that a cannot be changed by the function?

[mike_2000_17]

>>I was just wondering why you passed const Matrix2D& a as the first variable in your version of getTranspose()? Does the const mean that a cannot be changed by the function?

Yes. This is called const-correctness. If a function does not modify a parameter that is passed by reference or pointer, it should use a const qualifier to force the non-modification within the body of the function (in case you mistakenly modify it) and to publish to the anyone using this function that it will not modify the parameter.

You might encounter a small issue with that. Constness is "infectious" in the sense that once you have a variable (parameter or otherwise) that is const-qualified, you can only call const member functions on it or pass it to a function that takes a const-qualified reference or pointer, or by-value. This implies that the functions like getNumRows, getNumColumns, and getElement should be const as well, as such:

class Matrix2D {
  //....
  public:
    int getNumRows() const;            //notice the const at the end.
    int getNumColumns() const;         //ditto.
    double getElement(int, int) const; //ditto.
  //...
};

//and similarly in the definition:
int Matrix2D::getNumRows() const
{
  return r;
};

int Matrix2D::getNumColumns() const
{
  return c;
};

double Matrix2D::getElement(int i, int j) const
{
  return elements[i * c + j];
};

In the above, the const at the end of the member functions impose the restriction that the data members of the Matrix2D object cannot be modified within the body of those functions. This allows you to call those functions on const-qualified objects or references or pointers.

Generally, it is preferred (for good coding practices) to always use appropriate const-qualifiers and use them throughout (this is called const-correctness). It is generally pretty easy to know which functions will not modify what, so const-correctness is not very difficult to do, and it has the benefit of catching some erroneous code at compile-time (and always prefer compile-time errors to run-time errors!).

[v_janssens]

I've incorporated all your advice Mike_2000 and the problem is solved! I've a new problem now though, the program has gotten REALLY slow. Could this be down to the changes you suggested? or how can I find the source of this?

Thanks again V

[mike_2000_17]

To find a bottleneck in an application, you need to use a profiler. It will tell you how much processing time is needed by each function in your code. I have rarely done profiling, so I can't really recommend any good tools (google is your friend).

Anytime a software involves inverting large matrices, it is almost certainly the most expensive operation in all the code. Make sure that you are using a good matrix inversion method for the particular matrix you have. What method are you using?

[v_janssens]

I'm using a simple gaussian elimination routine I wrote myself but using breakpoints I've checked the different matrix operations and they don't seem to slow things up. I'll get onto google about the profiler.

I wonder could it be resizing the vector variables? The biggest slowdown seems to be when the program is starting up, when most of the matrices are defined. Have you come accross this with vectors before? This is the first time I've used them.

[v_janssens]

Found the problem. I was calling the same function multiple times in a loop which slowing everything down. Thanks for all your help with everything.