std::bad_alloc for 2D arrays

[mohsaied]

Hi all,

I have a large 2D array in a loop, in each iteration of the loop i want to expand that array so I do the following:

1- copy the array onto a new temp array
2- delete original array
3- create new, larger array
4- copy back the values from the temp
5- populate additional values in new array
6- delete temp array

I do this over and over again in a loop. When I monitor memory usage, I find that the arrays are created and memory is allocated for them but they are never deleted. After a few iterations, my program crashed with "std::bad_alloc" since I ran out of memory.

Why isnt the memory being freed when i delete the arrays?

thank you

 //copy the weights matrix
    double **temp = 0;
    //memory allocated for elements of rows.
    temp = new double *[num_blocks];
    //memory allocated for  elements of each column.
    for (int i = 0; i < num_blocks; i++)
        temp[i] = new double[num_blocks];

    //copy old weights
    for(int i = 0; i < num_blocks; i++)
        for(int j = 0; j < num_blocks; j++)
            temp[i][j]=weights[i][j];

    //unallocate memory for old weights
    for (int i = 0; i < num_blocks; i++)
        delete [] (double*)weights[i];
    delete [] (double**)weights;


    //find new number of blocks
    int num_blocks_old = num_blocks;
    num_blocks = all_blocks.size();

    //create new weights matrix
    weights = 0;
    //memory allocated for elements of rows.
    weights = new double *[num_blocks];
    //memory allocated for  elements of each column.
    for (int i = 0; i < num_blocks; i++)
        weights[i] = new double[num_blocks];
    //initialize
    for(int i = 0; i < num_blocks; i++)
        for(int j = 0; j < num_blocks; j++)
            weights[i][j]=0;

    //copy unchanged old weights back to new resized matrix
    for(int i = 0; i < num_blocks_old; i++)
        for(int j = 0; j < num_blocks_old; j++)
            weights[i][j]=temp[i][j];

    //insert weights for pseudo pins in new matrix
    for(int i=0;i<pseudo_weights.size();i++){
        weights[unplaced_blocks[i]->index][first_pseudo_index+i]=pseudo_weights[i];
        weights[first_pseudo_index+i][unplaced_blocks[i]->index]=pseudo_weights[i];
    }

    //unallocate memory for temps
    for (int i = 0; i < num_blocks_old; i++)
        delete [] (double*)temp[i];
    delete [] (double**)temp;
    pseudo_weights.clear();

[kbw]

I guess you have a buffer overrun. Have you tried printing out those indexes in the psuedo weights section?

Also, you can use a single allocation:

double* m = new double[num_blocks*num_blocks];

Then calculate the index yourself.

for (i = 0; i != num_blocks; ++i)
    for (i = 0; i != num_blocks; ++i)
        m[i*num_blocks + j] = 0.0;

[EricDu]

I don't see there is any problem on delete, but I do see there is a potential problem in the following code. At this point, weights' size is num_blocks, but you are using num_blocks_old with it, if num_blocks_old > num_blocks, there will be an out of boundary issue, and causing unpredictable results.

    for(int i = 0; i < num_blocks_old; i++)
        for(int j = 0; j < num_blocks_old; j++)
            weights[i][j]=temp[i][j];

[mohsaied]

I'm pretty sure the problem isn't in the pseudo_weights part, this just populates the rest of the 2D array after copying the old part.

for example my old matrix is

0 0 1 1
0 0 1 1
0 0 1 1
0 0 1 1

then i resize it and copy the old values back and add the pseudo_weights (denoted by p in this illustration)

0 0 1 1 p
0 0 1 1 p
0 0 1 1 p
0 0 1 1 p
p p p p p

in this case I increased the 2D array size by 1.

What I dont understand, is why the "delete" command doesnt do its job in deallocating the memory

[mohsaied]

num_blocks_old is always smaller than num_blocks Eric

[EricDu]

num_blocks_old is always smaller than num_blocks Eric

If so, then it makes sense that the memory is always growing up.

Now the question is what the max value of num_blocks you got. If the max memory is 2G, the max value of num_blocks is about 16384.

[mohsaied]

Now the question is what the max value of num_blocks you got. If the max memory is 2G, the max value of num_blocks is about 16384.

That's a good point, num_blocks actually grows to about 10 000 for some of the testbenches, but my RAM is 3 gigs.

But what still concerns me when i debug the program and monitor memory usage is the following:

The memory usage increases on the creation of a new 2D array but it does NOT drop when I delete the array. I was guessing that it may have something to do with the scope? since they're both inside the loop or something? Bottom line: the delete command doesnt seem to be freeing up memory.

i have another delete command in my program and it seems to work fine. I don't understand why this one doesnt work correctly though.

[EricDu]

Since you are using delete operator correctly, it's wasting your time to focus on those delete statements posted here, the bad_alloc must be caused by other issue.

I am still interesting in the value of num_blocks, can you tell me what the value is when bad_alloc occurred?

[mohsaied]

I reimplemented that whole part using a single vector which just stores the non-zero pseudo weights which are supposed to be added to the new matrix.

Eric, I guess I was just allocating more memory than I was deleting. And num_blocks was growing to about 10000 when my program crashed

Thanks for your help