David Bremner on Sun, 3 Dec 2000 10:58:00 -0400 (AST)


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

excessive gp heap usage?


I have a gp script whose heap usage seems to grow uncontrollably. 
I am very new to gp, so I am hoping someone can see right away 
what I am doing wrong.  I am running under FreeBSD; both 2.0.20 (beta)
and 2.1 exhibit the same behaviour.  I looked at all the references
to heap I could find in the manual, but nothing jumped out at me.

If you want to see the problem, read in the attached script, and 
run search(6); actually even search(5) leaves about 70000 objects in
the heap.

Thanks for any suggestions.

global(M,nodes,Sol,fullfacet,topfacet,botfacet);

init(d)=
{
M=matrix(2*d,d);

nodes=0;

Sol=listcreate(10);

M[d+1,2]=-1;
for(i=1,d, [ M[d+i,1]=1, M[i,1]=-1, M[1,i]=-1 ]);
for(i=2,d, [ M[i,i]=1, M[d+i,i]=-1 ]);

fullfacet=1;
topfacet=vector(d,j,compmask(component(M,j),1));
botfacet=vector(d,j,compmask(component(M,j),-1));
}

search(d)=
{
  init(d);
  complete(M,1,1,fullfacet,topfacet,botfacet);
}
  
compmask(v,val)=
{
 local(mask);
 mask=0;
 for(i=1,matsize(v)[1],mask=bitor(mask,(v[i]==val)*2^(i-1)));
 return(mask);
}



checkrank(Mp,j,rowmask,tfacet,bfacet)=
{
  local(T,B);

  T=mattranspose(vecextract(mattranspose(Mp),bitand(rowmask,tfacet[j])));

  B=mattranspose(vecextract(mattranspose(Mp),bitand(rowmask,bfacet[j])));

  return( ( matrank(T)==matsize(T)[1] && matrank(B)==matsize(B)[1] ));
}

checkopposite(Mp,rowmask)=
{
  local(F);

  F=mattranspose(vecextract(mattranspose(Mp),rowmask));

  return( matrank(F) == matsize(F)[1] );
}

check(Mp,rowmask,tfacet,bfacet)=
{
  local(jj);

  ok=checkopposite(Mp,rowmask);
 
  if (!ok, return(0));

  for (jj=1,matsize(Mp)[2], 
	if (!checkrank(Mp,jj,rowmask,tfacet,bfacet), return(0)));
  
  return(1);
}

complete(Mp,i,j,rowmask,tfacet,bfacet)=
{
  local(rowfinished);

  rowfinished=0;

  nodes++;

  if (nodes % 1000 == 0,
   print(nodes,";",i,";",j,";",rowmask,tfacet,bfacet,getheap()));

 
  \\ Boundary conditions for recursion

  if (j==matsize(Mp)[2], rowmask=bitor(rowmask, 2^(i-1)); rowfinished=1);

  if (j>matsize(Mp)[2], return(complete(Mp,i+1,1,rowmask,tfacet,bfacet) ));
  if (i>matsize(Mp)[1],  listput(Sol,Mp); return(1) );

  if(Mp[i,j]!=0, return(complete(Mp,i,j+1,rowmask,tfacet,bfacet)));


  Mp[i,j]=1;
  
  tfacet[j]=bitor(tfacet[j],2^(i-1));
  
  if ((newrow==0) || check(Mp,rowmask,tfacet,bfacet), 
		complete(Mp,i,j+1,rowmask,tfacet,bfacet));

  tfacet[j]=bitxor(tfacet[j],2^(i-1));


  Mp[i,j]=-1;

  bfacet[j]=bitor(bfacet[j],2^(i-1));

  if ((newrow==0) || check(Mp,rowmask,tfacet,bfacet), 
		complete(Mp,i,j+1,rowmask,tfacet,bfacet));

  bfacet[j]=bitxor(bfacet[j],2^(i-1));

  Mp[i,j]=0;

  return(0);

}