push_back() a vector into a 3D vector causes memory leak

[blindProgrammer]

I will try to explain the issue as best as I can. First I will present the code:

for (int i=0; i<200000; i++){

    //3 variables dealing with pathways
    vector<int> MCpathPops;
    vector<vector<int> > MCpaths;
    vector<int> pathway=getPathway();

    //3 variables dealing with ionisation times
    int count=0;
    vector<vector<vector<double> > > MCionTimes;
    vector<double> ionTimes = getIonTimes(); //Gets ionisation times, passed by reference


    vector<vector<int> >::iterator iter=find(MCpaths.begin(), MCpaths.end(), pathway); 
//Looks in MCpaths, if pathway is in MCpaths, an iterator is returned pointing to the first element of the pathway. 
//If pathway is not in MCpaths it returns an iterator to the end of MCpaths. 

    if(iter != MCpaths.end()) { //If pahtway is in MCpahts

        MCpathPops[distance(MCpaths.begin(), iter)]+=1;
        MCionTimes[distance(MCpaths.begin(), iter)].push_back(ionTimes);

    }
    else{ //If pathway is not in MCpaths

        MCpaths.push_back(pathway);
        MCpathPops.push_back(1);

        vector<vector<double> > empty; //TODO: Change
        MCionTimes.push_back(empty);
        MCionTimes[count].push_back(ionTimes);
        count ++;

    }
    ionTimes.clear();
}

The question is the following:
There are somewhere between 10-20 pathways which are stored in the MCpaths. The MCpathsPops, keeps track of how many times each pathway appeared (a few thousand times each).
Now I want to store the ionisation times of each pathway (200,000 in total) in MCionTimes. However, this leads to a memory leak and the program crashing at around 20,000 repetitions. I don't understand why that is. Why is it that when I push_back() the ionTimes variable, it causes a memory leak?

Note, the ionTimes variable, might be either size 0,1,2,3 or 4.
eg1. ionTimes= []
eg2. ionTimes=[0.5]
eg3. ionTimes=[-2.1,3.7] and so on

Note2, I have also tested the code using the following change in the if loop:

...
...
if(iter != MCpaths.end()) { //if pathway in MCpaths
    MCpathPops[distance(MCpaths.begin(), iter)]+=1;
    vector<double> en;
    en.push_back(1);
    en.push_back(1);
    en.push_back(1);
    en.push_back(1);
    MCionTimes[distance(MCpaths.begin(), iter)].push_back(en);
}
...
...

where every time I pass a vector with 4 entries in the MCionTimes and I don't encounter the memory leak. It only appears when I am pushing back a vector acquired from the function getIonTimes().

Note3, I also tried passing the ionTimes by value from the getIonTimes() function. The result is still the same


The error I get is the following:
Segmentation fault (core dumped)

Any ideas on how to fix this issue? Please help!

[jonnin]

memory leaks != core dumps.
most memory leaks drain the OS out of memory, and the OS starts to complain that it is low/out of memory, which then leads to instability in either the OS itself or running programs, or if you have enough swap space, just a lot of slowness.

mostly likely you are accessing memory you do not own, eg [index] where index > vector.size()

is this the offending line?
distance(MCpaths.begin(), iter)
change that line to this:
MCionTimes.at(distance(MCpaths.begin(), iter)).push_back(en);
with a try/catch block appropriate to .at around it, or just print the index you computed alongside the mciontimes.size and see if it is out of range, or look at the same in the debugger. All 3 ideas get you to the same answer (is this the problem or not).

-> .at is slow. It is best to fix the issue and not rely on it.

[blindProgrammer]

Thank you for the fast reply.

I have tried printing the index and the index is fine, it is not out of range. That also explains why when I change the if statement to:

...
if(iter != MCpaths.end()) { //if pathway in MCpaths
MCpathPops[distance(MCpaths.begin(), iter)]+=1;
vector<double> en;
en.push_back(1);
en.push_back(1);
en.push_back(1);
en.push_back(1);
MCionTimes[distance(MCpaths.begin(), iter)].push_back(en);
}
...

I don't encounter any errors. The error is encountered when I push_back the vector IonTimes specifically. Note, I have also printed IonTimes and the values returned are correct.

[seeplus]

AFAIS, you effectively have:

vector<vector<vector<double> > > MCionTimes;

vector<double> ionTimes = getIonTimes();

MCionTimes[distance(MCpaths.begin(), iter)].push_back(ionTimes);

MCionTimes[count].push_back(ionTimes);

Initially MCionTimes has no elements (size() is 0).

However MCionTimes is then indexed as if it had at least the required number of elements for the index.

I don't see anywhere where MCionTimes has elements added so that the index will work?

Note that even if count is 0, if MCionTimes is empty you still can't use an index (even 0). An index of 0 means the 'first' element but there doesn't seem to be any elements.

[jonnin]

push back can and frequently does invalidate all old iterators and pointers into the data.
its possible iter has gone bad due to the push back of mc paths.
the only other real failure you can get is bad alloc (no memory left to allocate) which seems very unlikely.

[blindProgrammer]

Hi seeplus

I thought of this as well and tested it.
In the ifs and else statements I scan if the vector<int>pathway is in the vector<vector<int> > MCpaths. If it is not I add it, and I also add the first entry in the MCionTimes:

vector<vector<double> > empty; //TODO: Change
MCionTimes.push_back(empty);
MCionTimes[count].push_back(ionTimes);
count ++;

So every time I encounter a new pathway I increase the size of MCionTimes. Then, if the same pathway is encountered again, I enter the if statement and apply:

MCionTimes[distance(MCpaths.begin(), iter)].push_back(ionTimes);
where distance(MCpaths.begin(), iter) = 0

I checked this and the index turns out to always be correct. The issue arises when I push back the ionTimes. If I push a different vector it works fine, but when I push_back the ionTimes I get a core dump

[seeplus]

[Please don't change original code. If code has changed, post the new code as a new thread. Posts now don't correlate to the current code.]

[MikeyBoy]

Line 2 in your latest snippet creates one, and only one, element in the vector MCionTimes. So its size is now 1. At line 3, if count is anything other than 0, then MCionTimes[count] will be beyond the end of the vector, so trying to call push_back() on it is causing a memory violation.

Do you know upfront how many elements MCionTimes is going to need? If so, you should set the size on creation.

[MikeyBoy]

If code has changed, post the new code as a new thread.

Posting multiple threads for what is, essentially, the same topic, is confusing and can lead to people wasting their time.

Much better to post the updated code as a new post in the same thread.

But in any case, @tony360, please do NOT edit your original post to replace the code. That makes the thread incomprehensible for people trying to read it from the start.

[seeplus]

Are you compiling as 32bit or 64 bit?

If I push a different vector it works fine, but when I push_back the ionTimes I get a core dump

Even for the first time? How many elements are there in ionTimes?

After ionTimes is pushed, it's not used again is it?

If not, try this:

MCionTimes[count].emplace_back(std::move(ionTimes));

[seeplus]

If code has changed, post the new code as a new thread.

Posting multiple threads for what is, essentially, the same topic, is confusing and can lead to people wasting their time.

Sorry. My bad. I meant post the new code as a new post rather than updating an existing one.

[MikeyBoy]

@seeplus No worries - easily done :)

[dhayden]

Change your []'s to at()s to see if you're going out of bounds.

Can you run the debugger on the core file to see where it's getting the fault?

[blindProgrammer]

@seeplus Apologies for editing the code, I only changed the comment. It's my first time posting here and Im not familiar with the rules. I will answer your questions here. Then shall I repost the code?

Are you compiling as 32bit or 64 bit?

If I push a different vector it works fine, but when I push_back the ionTimes I get a core dump


Even for the first time? How many elements are there in ionTimes?

After ionTimes is pushed, it's not used again is it?

If not, try this:
MCionTimes[count].emplace_back(std::move(ionTimes));

I am not familiar if it is 32 or 64 bit and the computer cluster is down at the moment. I will update you once it is back up.
No the first time it's fine. It only crashes once I add too many values of ionTimes on MCionTimes.
After I use the ionTimes, I clear it. Then I reassign it another value and store it again on MCionTimes. I will try the MCionTimes[count].emplace_back(std::move(ionTimes)); and see what happens.

Line 2 in your latest snippet creates one, and only one, element in the vector MCionTimes. So its size is now 1. At line 3, if count is anything other than 0, then MCionTimes[count] will be beyond the end of the vector, so trying to call push_back() on it is causing a memory violation.

Do you know upfront how many elements MCionTimes is going to need? If so, you should set the size on creation.

The count starts as 0 and increases by 1 only at the line 4 of my latest snippet. This does not appear to be an issue every time I tested the code the count is within the limits of MCionTimes.size().
I don't know the size of the MCionTimes, but I know that it's not bigger than 30 for example. I will try that out, but I don't think it will resolve this issue. I will let you know once I try it what it returns

Change your []'s to at()s to see if you're going out of bounds.

Can you run the debugger on the core file to see where it's getting the fault?

I am pretty sure I am not going out of bounds, that doesn't seem to be the issue. I compiled the code including -fsanitize=address to see if it would return something different and the code ended due to a mistake before even reaching the part of the code I have here. The error I got is the following:

ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x000000426db3 sp 0x7ffff16110d0 bp 0x000000000008 T0)

[seeplus]

It only crashes once I add too many values of ionTimes on MCionTimes.

It looks like you're exceeding process addressable memory. Note that for a push-back/emplace-back that requires re-allocation of memory, then often more than double the existing memory will be required. New memory greater than the existing has to obtained, the old memory contents have to copied to the new memory and then and only then can the old memory be released.

If you're compiling as 32 bit, then compiling as 64 bit may help. However, if you have an idea as the final sizes of each of the 3 vectors involved, then reserving capacity may be the requirement. See http://www.cplusplus.com/reference/vector/vector/reserve/ Normally a 32 bit Windows program can only use 2Gb of memory.

It's possible that you are just trying to store too many elements.

If vector<double> has a elements
vector<vector<double> has b elements
vector<vector<vector<double> has c elements,

then the required memory is a * b * c * 8. Which when memory re-allocation takes place will be more than 2 * (a * b * c * 8) needed. Which is why when dealing with large vectors, memory allocation with .reserve() is so important to avoid this additional memory overhead requirement.


Another possibility is to do away with the icontimes variable altogether. Possibly something like:

MCionTimes[count].emplace_back(getIonTimes());

(and similar in the other places where icontimes are used)
which doesn't require intermediate memory to store the contents of icontimes.

The comment for getIconTimes() says passed by reference - but a copy is still made into icontimes irrespective.

[blindProgrammer]

@seeplus
I tried using the emplace_back instead of push_back, as well as removing the ionTimes completely and putting the emplace_back(getIonTimes()) directly. It doesn't work.

If you're compiling as 32 bit, then compiling as 64 bit may help. However, if you have an idea as the final sizes of each of the 3 vectors involved, then reserving capacity may be the requirement.

This sounds promising, I did some research but couldn't find exactly how to do this using reserve() function. I know that there will be at least 500,000 doubles stored, but I don't know how many x, y or z components it will be. For example it might be 20x1000x3. Or 15x1500x2. It is also the case that, MCionTimes[0] = 60,000, MC[1] = 30,000, MC[2] = 10,000 and so on.

Any help on how to reserve space in this case? On how to reserve a total of 500,000 entries, regardless of where in the 3d vector they will be placed

[helios]

To me this sounds like your heap might be corrupted from somewhere else. Could you post the entire program?

[thmm]

500,000 doubles

Normally that's hardly anything even on older hardware.
What amount of RAM do you have?

[jonnin]

any PC this side of 1995 can manage that.
if you don't know the shape, you can size a 1-d vector and reshape it yourself via direct indexing as - if 3-d.
or, ... if you are unsure if its a bug vs out of memory, try a smaller problem? does it work on 5000 doubles?

[seeplus]

For test code to try to identify the issue, consider:

#include <vector>
using namespace std;

constexpr size_t LOPCNT {2000};
constexpr size_t NOPATH {200};
constexpr size_t NOION {200};

vector<int> getPathway()
{
	vector<int> pw(NOPATH, 10);

	return pw;
}

vector<double> getIonTimes()
{
	vector<double> it(NOION, 11.11);

	return it;
}

int main()
{
	for (size_t i = 0; i < LOPCNT; ++i) {
		//3 variables dealing with pathways
		vector<int> MCpathPops;
		vector<vector<int> > MCpaths;
		vector<int> pathway = getPathway();

		//3 variables dealing with ionisation times
		int count = 0;
		vector<vector<vector<double> > > MCionTimes;
		vector<double> ionTimes = getIonTimes(); //Gets ionisation times, passed by reference

		vector<vector<int> >::iterator iter = find(MCpaths.begin(), MCpaths.end(), pathway);

		//Looks in MCpaths, if pathway is in MCpaths, an iterator is returned pointing to the first element of the pathway.
		//If pathway is not in MCpaths it returns an iterator to the end of MCpaths.

		//if (iter != MCpaths.end()) { //If pahtway is in MCpahts
		if (false) {	// force else part
			MCpathPops[distance(MCpaths.begin(), iter)] += 1;
			MCionTimes[distance(MCpaths.begin(), iter)].emplace_back(move(ionTimes));
		} else { //If pathway is not in MCpaths
			MCpaths.push_back(pathway);
			MCpathPops.push_back(1);

			vector<vector<double> > empty; //TODO: Change

			MCionTimes.push_back(empty);
			MCionTimes[count].emplace_back(move(ionTimes));
			count++;
		}

		//ionTimes.clear();
	}
}

Try this. It should compile/run OK. Then try increasing the const numbers towards what would be expected. If you get the program to run OK with these const vales as expected, then there's something else going on somewhere.