Sanjay Josh Sanjay Josh - 3 months ago 13
C Question

Definitely lost memory leak on calling void function (recursively)

I was trying to do Strassen's as well as the naive form of matrix multiplication for floating point arrays in C++.

While I am getting the answers rtight , the program kills itself on higher order of the matrix .This was obviously because the there was a memory leak.But I am unable to understand what it means or refers to as I had freed all dynamically allocated pointers

/*The first file */
#include "gen.h"
float v[4][4]={{9,8,3,1},{8,7,1,0},{2,1,3,4},{2,3,1,0}};
void print(float** arr,int n)
{

for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}

cout<<endl;
}
void del(float** arr,int n)
{
for(int i=0;i<n;i++)
delete []arr[i];
delete []arr;
}
float** generate(float** arr,const int n)
{
arr=new float*[n];
for(int i=0;i<n;i++)
{
arr[i]=new float[n];
}
//srand(time(NULL));

int last=5;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
arr[i][j]=fl((fl(rand())/fl(RAND_MAX))*10);
}
}
return arr;
}


The main file is this :(Code only for strassens)

#include "gen.h"
#include <thread>
using namespace std;
void Strassen(float** A,float** B,int sz,float **ans)
{
float ***p=new float**[7];
for(int i=0;i<7;i++)
{
p[i]=new float*[sz/2];
for(int j=0;j<sz/2;j++)
p[i][j]=new float[sz/2];
}
if(sz==1)
{

ans[0][0]=A[0][0]*B[0][0];
return;
//return ans;
}

float ***ALL=new float**[14];
for(int i=0;i<14;i++)
{
ALL[i]=new float*[(sz/2)];
for(int j=0;j<(sz/2);j++)
ALL[i][j]=new float[(sz/2)];
}



//All assigns
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[0][i][j]=A[i][j];
}
}

for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[1][i][j]=B[i][j+(sz/2)]-B[i+(sz/2)][j+(sz/2)];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[2][i][j]=A[i][j]+A[i][j+(sz/2)];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[3][i][j]=B[i+(sz/2)][j+(sz/2)];
}
}

for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[4][i][j]=A[i+(sz/2)][j]+A[i+(sz/2)][j+(sz/2)];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[5][i][j]=B[i][j];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[6][i][j]=A[i+(sz/2)][j+(sz/2)];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[7][i][j]=B[i+(sz/2)][j]-B[i][j];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[8][i][j]=A[i][j]+A[i+(sz/2)][j+(sz/2)];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[9][i][j]=B[i][j]+B[i+(sz/2)][j+(sz/2)];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[10][i][j]=A[i][j+(sz/2)]-A[i+(sz/2)][j+(sz/2)];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[11][i][j]=B[i+(sz/2)][j]+B[i+(sz/2)][j+(sz/2)];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[12][i][j]=A[i][j]-A[i+(sz/2)][j];
}
}
for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ALL[13][i][j]=B[i][j]+B[i][j+(sz/2)];
}
}


Strassen(ALL[0],ALL[1],(sz/2),p[0]);

Strassen(ALL[2],ALL[3],(sz/2),p[1]);

Strassen(ALL[4],ALL[5],(sz/2),p[2]);

Strassen(ALL[6],ALL[7],(sz/2),p[3]);

Strassen(ALL[8],ALL[9],(sz/2),p[4]);

Strassen(ALL[10],ALL[11],(sz/2),p[5]);

Strassen(ALL[12],ALL[13],(sz/2),p[6]);

for(int i=0;i<(sz/2);i++)
{
for(int j=0;j<(sz/2);j++)
{
ans[i][j]=p[4][i][j]+p[3][i][j]-p[1][i][j]+p[5][i][j];
ans[i][j+(sz/2)]=p[0][i][j]+p[1][i][j];
ans[i+(sz/2)][j]=p[2][i][j]+p[3][i][j];
ans[i+(sz/2)][j+(sz/2)]=p[0][i][j]+p[4][i][j]-p[2][i][j]-p[6][i][j];
}

}




for (int i = 0; i < 14; ++i)
{
del(ALL[i],(sz/2));
}
delete []ALL;
for(int i=0;i<7;i++)
{
del(p[i],(sz/2));
}

}
int main()
{

//seed the randomizer
srand(time(NULL));

float** m1=NULL;
float** m2=NULL;
int sz=2;


m1=generate(m1,sz);
m2=generate(m2,sz);

float **ans3=new float*[sz];
for(int i=0;i<sz;i++)
ans3[i]=new float[sz];

clock_t stt=clock();
Strassen(m1,m2,sz,ans3);
print(ans3,sz);
clock_t end=clock();
cout<<(end-stt)/double(CLOCKS_PER_SEC)*1000 << endl;

del(m1,sz);
del(m2,sz);
del(ans3,sz);
return 0;

}


This gives the right answer for small sizes like order=2,4,8
But it kills itself for 256 or so .
When I ran valgrind :This was the output .It seems like there's a new operator at every call of Strassen()

==5312== HEAP SUMMARY:
==5312== in use at exit: 72,772 bytes in 11 blocks
==5312== total heap usage: 17 allocs, 6 frees, 72,808 bytes allocated
==5312==
==5312== 0 bytes in 7 blocks are indirectly lost in loss record 1 of 5
==5312== at 0x4C2C84F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5312== by 0x4017F5: Strassen(float**, float**, int, float**) (in /home/sanjay/Documents/Re/assign1/mainp)
==5312== by 0x403012: main (in /home/sanjay/Documents/Re/assign1/mainp)
==5312==
==5312== 4 bytes in 1 blocks are indirectly lost in loss record 2 of 5
==5312== at 0x4C2C84F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5312== by 0x402F6A: main (in /home/sanjay/Documents/Re/assign1/mainp)
==5312==
==5312== 12 (8 direct, 4 indirect) bytes in 1 blocks are definitely lost in loss record 3 of 5
==5312== at 0x4C2C84F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5312== by 0x402F14: main (in /home/sanjay/Documents/Re/assign1/mainp)
==5312==
==5312== 56 bytes in 1 blocks are definitely lost in loss record 4 of 5
==5312== at 0x4C2C84F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5312== by 0x401796: Strassen(float**, float**, int, float**) (in /home/sanjay/Documents/Re/assign1/mainp)
==5312== by 0x403012: main (in /home/sanjay/Documents/Re/assign1/mainp)
==5312==
==5312== 72,704 bytes in 1 blocks are still reachable in loss record 5 of 5
==5312== at 0x4C2BBCF: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5312== by 0x4EC21FF: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21)
==5312== by 0x40105C9: call_init.part.0 (dl-init.c:72)
==5312== by 0x40106DA: call_init (dl-init.c:30)
==5312== by 0x40106DA: _dl_init (dl-init.c:120)
==5312== by 0x4000D09: ??? (in /lib/x86_64-linux-gnu/ld-2.21.so)
==5312==
==5312== LEAK SUMMARY:
==5312== definitely lost: 64 bytes in 2 blocks
==5312== indirectly lost: 4 bytes in 8 blocks
==5312== possibly lost: 0 bytes in 0 blocks
==5312== still reachable: 72,704 bytes in 1 blocks
==5312== suppressed: 0 bytes in 0 blocks
==5312==


Can't figure out why ??

Answer

Your if (sz==1) check should be the first thing in the function. You leak the allocation of p when that return happens.