SEGSEV received in STL code t_splay()

[Soko]

Hello,

I am receiving a segsev from the STL. Using gdb, here is the stack trace at the time of segsev:

Program received signal SIGSEGV, Segmentation fault.
0xfed45d07 in t_splay () from /lib/libc.so.1
(gdb) backtrace
#0 0xfed45d07 in t_splay () from /lib/libc.so.1
#1 0xfed45bd4 in t_delete () from /lib/libc.so.1
#2 0xfed4590e in realfree () from /lib/libc.so.1
#3 0xfed45f17 in cleanfree () from /lib/libc.so.1
#4 0xfed45433 in _malloc_unlocked () from /lib/libc.so.1
#5 0xfed4535c in malloc () from /lib/libc.so.1
#6 0xfef5cd25 in operator new () from /usr/lib/libstdc++.so.6
#7 0x08052b16 in make_next_generation (G=@0x8047acc) at partition.cpp:322
#8 0x08052888 in main () at partition.cpp:289

Here is the offending code:

        Generation *G1 = new Generation(G->get_Gen_Num());

                Generation::Generation(int gen1)
                {
                        gen_Num = gen1;
                        best_Chromosome = -1; //Defines does not exist yet
                        for(int i = 0; i < GEN_SIZE; i++)
                        {
                                Chromosome * C = new Chromosome();
                                gen[i] = C;
                                if (i < ELITISM)
                                        best[i] = C;
                        }

                }

And here is the rest of the class information in case that is needed:

        private:
                int gen_Num; //Keeps track of the generation number
                int best_Chromosome; //This will keep track of the terminating condition.
                Chromosome *best[ELITISM]; //Stores the best X amount, where x is the elitism value
                /*
                 *The terminating condition will be number of generations of no improvement to the most fit chromosome.
                 *Assuming there is no improvement through X number of generations (inversely proportional to the population size,
                 *but proportional to the NUM_NUMBERS variable), the problem will stop itself.
                 */
                Chromosome* gen[GEN_SIZE];

What is confusing about this to me is that this runs fine until the 42 Generation is completed, and it is on to creating the 43rd generation. It always happens there, no other time. So I am curious as to why it would only happen then, and what is causing this. Any help/ideas would be appreciated.

One thing I do know is that it is not my server I am running on causing it to do this, I have run into that problem, which cuts it off at around 4GB (each process), and this one gets cut off at around 250MB.

I am working on this on the side, as I have recently discovered Genetic Algorithms and decided to play around with it for a while.

Thanks!

[ne555]

Chromosome * C = new Chromosome(); ¿why? Check out for memory leaks, double deletes, etc.

[Soko]

Each chromosome represents a possible solution for the problem. I.e. I allocate some space for X number of chromosomes per generation.

I have been checking for those, and I do have some somewhere, but I am not sure where it is right now. I also do not think that would cause the problem (but again, not sure).

                //Destructor
                Generation::~Generation()
                {
                        for(int i = 0; i < GEN_SIZE; i++)
                                gen[i]->~Chromosome();

                        delete [] best;
                        delete [] gen;
                }

void make_next_generation(Generation *&G)
{
        Generation *G1 = new Generation(G->get_Gen_Num());

        for(int i = 0; i < GEN_SIZE - ELITISM; i++)//generate the number of offspring needed
        {
                Chromosome *C = make_Offspring(G);
                C->mutate();
                G1->set_Gen(i, C);
        }
        //This for loop carries over the chromosomes specified by the elitism value
        for(int i = GEN_SIZE - ELITISM; i < GEN_SIZE; i++)
                G1->set_Gen(i, G->get_Best(i - GEN_SIZE + ELITISM));

        Generation *temp = G;
        G = G1;
        G->increment_Gen_Num();
        temp->~Generation();
}

The first is the destructor for my generation. The second is entire function that will call making the next generation. the destructor is called on each generation.

When it seg faults for my memory leak issue, I get:

terminate called after throwing an instance of 'std::bad_alloc'
what(): St9bad_alloc


So I don't think this is occuring from a memory leak issue.

One second glance my destructor does call a double delete on certain chromosomes, but this issue was fixed, and the problem still occurs (fixed in the code posted above).

Not sure what specifically to next check in on. I am looking into the memory leak issue and when I figure that out, I will repost if that keeps happening. Until then, any other ideas? I am still stumped :(

Thanks

[Galik]

You should not delete[] best and gen

    delete [] best; // don't delete it because you didn't create it using new
    delete [] gen; // ditto 

I am not sure what you are trying to do here:

        Generation *temp = G;
        G = G1; // This does not copy your Generation object, only the pointer to it
        G->increment_Gen_Num();
        temp->~Generation(); // you should not be calling the destructor directly, use delete temp; 

EDIT:
Again you should not be calling the destructor directly:

                        for(int i = 0; i < GEN_SIZE; i++)
                                // gen[i]->~Chromosome(); // not like this
                                delete gen[i]; // use this 

[ne555]

¿Why do you use dynamic allocation in the first place? You aren't using polymorphism...

void make_next_generation(Generation &G)
{
        Generation G1(G.get_Gen_Num()); //use objects instead

        for(int i = 0; i < GEN_SIZE - ELITISM; i++)//generate the number of offspring needed
        {
                Chromosome C = make_Offspring(G);
                C.mutate();
                G1.set_Gen(i, C);
        }
        //This for loop carries over the chromosomes specified by the elitism value
        for(int i = GEN_SIZE - ELITISM; i < GEN_SIZE; i++)
                G1.set_Gen(i, G.get_Best(i - GEN_SIZE + ELITISM));

        G = G1;
        G.increment_Gen_Num();
}

Also the destructor is called automatically when an object goes out of scope or you delete the pointer (allocated with new). You must not explicit call it.

                Generation::~Generation()
                {
                        for(int i = 0; i < GEN_SIZE; i++)
                                gen[i]->~Chromosome();

                        delete [] best;
                        delete [] gen;
                }

//Generation::Generation(int gen1)
//Chromosome * C = new Chromosome();
//gen[i] = C; 

gen[i] points to dynamic allocated memory. You are not releasing that memory ( delete gen[i]; )

I guess that gen is a Chromosome** Don't do that.
If an static array is no good enough use an stl container (vector, deque, list, etc) instead. That way you don't have to worried about the memory management.

I guess that you want to store references in the best array. You could do

vector<Chromosome> gen;
vector<int> best; //store the index 

[Soko]

@Galik - Unless I am mistaken, arrays are allocated, and calling the destructor on them (delete [] ARRAYNAME) will unallocate memory used by them? I guess I am not too familiar with arrays, but was trying to use it as a shortcut from vectors, probably not my smartest idea ever.

In that code snippet, I pass in a reference parameter to G, so what I am doing is I am making the next generation (G1), then after it is fully created, I am setting G to that generation to pass back to main, then calling the destructor on the old G.

What is the difference in calling the destructor through delete and through ~?


@ne555 - I am using dynamic allocation of memory because I need to create many Chromosomes (as that is a predefined variable, set generally to 1000, 10000, or more). For generations, I suppose I don't need to use dynamic allocation, that could be changed, as there are ever only two generations needed at once.

It should be, but my chromosomes never go out of scope. I could modify my program to involve generations not being dynamically allocated, which would mean I wouldn't have to call the destructor there, but would still have to call the destructor on my chromosomes, which is where, I am guessing, the memory leak is occurring.

I think I could redo my code to be better without so many pointers, as pointers are not needed. I will be modifying my code in the next few days to make it work better this way. Thanks for the tips, hopefully that will solve my two problems I have.

[Zhuge]

Soko wrote:

but was trying to use it as a shortcut from vectors

Vectors are really a shortcut from (dynamically allocated) arrays, if you want to think of it that way.

Soko wrote:

What is the difference in calling the destructor through delete and through ~?

delete also frees the memory. So if you explicitly call the destructor, it's being called twice, which you do not want.

Yeah, try to rework it without so many pointers. It really looks like you can just use vectors to avoid them entirely, as I don't see any polymorphism anywhere.

[Galik]

Soko wrote:

Unless I am mistaken, arrays are allocated, and calling the destructor on them (delete [] ARRAYNAME) will unallocate memory used by them? I guess I am not too familiar with arrays, but was trying to use it as a shortcut from vectors, probably not my smartest idea ever.

It depends how you create your array. The rule is if you created it using new[] then you must destroy it using delete[].

So:

// Normal array
int array1[10]; // do not delete this

// Dynamic array
int* array2 = new int[10]; // created using new[]

delete[] array2; // must use delete[] 

There is no reason to use arrays as a "shortcut" from vectors. vectors are probably no less efficient than arrays but they are much safer and easier to use.

Soko wrote:

In that code snippet, I pass in a reference parameter to G, so what I am doing is I am making the next generation (G1), then after it is fully created, I am setting G to that generation to pass back to main, then calling the destructor on the old G.

The problem is that G is not a Generation object. It is simply a pointer to the Generation object. So when you do G = G1 you are not copying your Generation object, you are copying the pointer to it.

A pointer is simply a memory address.

So after you do G = G1, both G and G1 point to the very same generation object.

If you want to copy the object itself you need to dereference the pointer using *
*G = *G1

Soko wrote:

What is the difference in calling the destructor through delete and through ~?

Calling the destructor directly does not free the memory allocated to the object. You should call delete and that will call the destructor for you before freeing the memory.

EDIT:

I would consider taking ne555's advice and try to write the program without using pointers and dynamically allocated objects. Also consider using std::vectors rather than arrays.

[Soko]

I now remember why I was using pointers. Pointers are a lot easier to transfer than the actual object itself.

For example, my program (with same settings) using pointers ran in about 25 seconds.

My program not using pointers has been running for 5 minutes and is about 1/20th done.

It requires a lot of copying of data. That is why I was using pointers: Create it once and not worry about copying the data (just the address). So I was having some trouble with garbage collection.

Thought I would throw my two cents in...

Edit:

        G1 = G;

This involves:

                Generation& Generation::operator=(Generation &rhs)
                {
                        gen_Num = rhs.get_Gen_Num();
                        best_Chromosome = rhs.get_best_Chromosome();
                        for(int i = 0; i < ELITISM; i++)
                        {
                                best.at(i) = rhs.get_Best_1(i);
                        }
                        for(int i = 0; i < GEN_SIZE; i++)
                        {
                                Chromosome C = rhs.get_Gen(i);
                                gen.at(i) = C;
                        }

                        return *this;
                }

Line 9 involves:

                Chromosome& Chromosome::operator=(Chromosome &rhs)
                {
                        fitness = rhs.get_Fitness();
                        for(int i = 0; i < NUM_NUMBERS; i++) //Set at 10000
                                isIn.at(i) = rhs.get_Bool(i);

                        return *this;
                }

So this is 1,000 * 10,000 operations per copy of generation, or 10,000,000. This isn't too bad, but then if I want to increase the numbers to handle larger problems:
100,000 for GEN_SIZE, 10,000,000 for NUM_NUMBERS, making 100,000,000,000 calculations per copy, and going through 300 generations... it gets intensive, instead of just the initial set up of each.



Although I did switch to arrays, so hopefully that will help some areas. But I think I want dynamically allocated objects to make the program faster, instead of transferring everything and copying it, I can just copy the address, thus allowing the object to remain the same.

However, to do this, I need a safe and easy way to de-allocate the memory once I am done with the objects.

[Galik]

Okay, I see what you are doing there now. Well hopefully changing your code so as not to delete[] those arrays that you didn't new[] has helped your error situation?

[Soko]

Thus far I haven't run into the errors of memory allocation or the other one. But it takes a long time to process now (as mentioned above), and I haven't yet reached where it had crashed in the previous version. I will take time this weekend to change it back over (partially) to how I was doing it.

I will try to include a few less pointers, but essentially need the majority of them to Chromosomes, as I think that is where the majority of the time is going.

I will mark this fixed in a few days if I don't run into the error again after I change it to get the speed back.

Thanks for the help thus far :)

[ne555]

I don't get it. The operation with objects or with pointers are conceptually different.
Generation& Generation::operator=(const Generation &rhs)

Regarding make_next_generation(). Assuming that you need another generation object, you could avoid the overhead of G = G1; by implementing a swap method (G1 will be discarded at the end of the function)
The swap() method of stl containers are constant as they only change the head pointer.