Memory leak in ideal arithmetic

[ppurka]

From google spreadsheet which no one reads X-(

sage: R = PolynomialRing(QQ, 'x', 2)                                 
sage: count = 0
sage: while R.ideal(1) == R.ideal(1):                         
....:     count += 1
....:     if not count%100:
....:         print get_memory_usage()
....:     if not count%1000:
....:         break
....:         
// ** redefining i_par **
// ** redefining # **
// ** redefining P **
1331.88671875
1334.5546875
1337.21875
1340.0078125
1342.66796875
1345.3359375
1347.99609375
1350.65625
1353.32421875
1355.984375

CC: @simon-king-jena @sagetrac-PolyBoRi @malb

Component: algebra

Issue created by migration from https://trac.sagemath.org/ticket/15498

[nbruin]

comment:1

Memory use is still increasing with 5.13.xx, but I don't see a particular object count go up in the way one would expect with a straight memory leak. This could just be fragmentation or some other difficult-to-control issue. The code I tried was:

sage: import gc
sage: from collections import Counter
sage: R=QQ['x']
sage: R.ideal(1)==R.ideal(1)
True
sage: gc.collect()
514
sage: pre = gc.get_objects()
sage: for i in range(100000): _ = R.ideal(1) == R.ideal(1)
sage: gc.collect()
0
sage: post = gc.get_objects()
sage: pre_id=set( id(p) for p in pre )
sage: new=[p for p in post if id(p) not in pre_id]
sage: C=Counter(type(p) for p in new)
sage: len(new)
51
sage: len(pre)-len(post)+len(new)
6
sage: C
Counter({<type 'list'>: 12, <type 'tuple'>: 8, <type 'dict'>: 7, <type 'frame'>: 6, <type 'instancemethod'>: 4, <type 'weakref'>: 3, <class '_ast.Name'>: 2, <class '_ast.Interactive'>: 1, <type 'dictionary-itemiterator'>: 1, <class '_ast.Assign'>: 1, <type 'listiterator'>: 1, <class '_ast.Module'>: 1, <class '_ast.Attribute'>: 1, <type 'builtin_function_or_method'>: 1, <type 'enumerate'>: 1, <class '_ast.Call'>: 1})

Hopefully the memory use flattens out after a while. It may well be that there was a serious leak for this example before that is now fixed. It may also be that we really are leaking, but not in python memory. Perhaps libsingular?

[nbruin]

comment:2

Sadly, this is most definitely a memory leak and, as shown above, not one in python space. The most likely suspect is LibSingular, especially because we already know that we're not interfacing with LibSingular reference counting properly. This might be a particularly easy example to trace through, so it may be worth doing, because it might show the way to proper LibSingular memory management. Just to confirm:

sage: R = PolynomialRing(QQ, 'x', 2)                                 
sage: count = 0
sage: p = get_memory_usage()
sage: while R.ideal(1) == R.ideal(1):                         
....:         count += 1
....:         if (count%1000 == 0):
....:                 print get_memory_usage(p)
....:                 p = get_memory_usage()
....:                 
27.21875
26.61328125
26.76953125
26.62890625
26.62109375
......

i.e., each batch of 1000 iterations grows memory use very consistently.

[simon-king-jena]

comment:3

Adding more expert as Cc.

[simon-king-jena]

comment:4

I can confirm that this time it is not a problem with cyclic garbage collection, as the number of objects tracked by the gc module does not increase:

sage: R = PolynomialRing(QQ, 'x', 2) 
sage: count = 0
sage: p = get_memory_usage()
sage: import gc
sage: _ = gc.collect()
sage: l = len(gc.get_objects())
sage: while R.ideal(1) == R.ideal(1):
....:     count += 1
....:     if (count%1000 == 0):
....:         _ = gc.collect()
....:         print get_memory_usage(p), len(gc.get_objects())-l
....:         p = get_memory_usage()
....:         
26.8984375 183
26.15234375 183
26.01171875 183
25.890625 183
26.15234375 183
26.0078125 183
25.890625 183
26.15234375 183
26.0078125 183
25.890625 183
26.15234375 183
26.0078125 183
26.015625 183
...

So, it could actually be that the Sage code triggers a memory leak in Singular.

[simon-king-jena]

comment:5

Note the following variation:

sage: while R.ideal(1):
....:     count += 1
....:     if (count%1000 == 0):
....:         _ = gc.collect()
....:         print get_memory_usage(p), len(gc.get_objects())-l
....:         p = get_memory_usage()
....:         
10.03515625 378
0.0 378
0.0 378
0.0 373
0.0 373
0.0 373
0.0 373
0.0 373
0.0 373
...

So, we need to compare ideals to see the leak. It is not enough to just create the ideals and then just test if they are nonzero.

Edit: By the way, I just noticed:

sage: R.ideal(1)!=1
False
sage: R.ideal(1)==1
False
sage: R.ideal(1)>1
False
sage: R.ideal(1)<1
False
sage: R.ideal(1)<=1
True
sage: R.ideal(1)>=1
True

[simon-king-jena]

comment:6

PS: R.ideal(1)>=1 or R.ideal(1)>1 or R.ideal(1)!=1 leak as well, but R.ideal(1)==1 doesn't.

[simon-king-jena]

comment:7

R.ideal(1)>1 leaks, but R.ideal(1)<1 doesn't...

[nbruin]

comment:8

Replying to @simon-king-jena:

So, it could actually be that the Sage code triggers a memory leak in Singular.

More circumstantial evidence. I left it running and found:

...
26.61328125
26.609375

Singular error: no more memory
System 7138364k:7138364k Appl 7066362k/2105k Malloc 7054131k/0k Valloc 14336k/2105k Pages 3121/463 Regions 7:7

halt 14

(I was also intending to do the checks you've already done)

[malb]

comment:9

grml, trac ate my comment. I checked and it boils down to (at least also) computation Gröbner bases:

sage: while R.ideal([x0]).groebner_basis() == [x0]:
      count += 1
      if (count%1000 == 0):
            print get_memory_usage()

and

sage: while R.ideal([R.gen(0)]).groebner_basis() == [R.gen(0)]:
      count += 1
      if (count%1000 == 0):
            print get_memory_usage()

[simon-king-jena]

comment:13

ping

[simon-king-jena]

comment:14

The leak is still there:

sage: R.<x,y> = QQ[]
sage: count = 0
sage: while R.ideal([x]).groebner_basis() == [x]:
....:     count += 1
....:     if (count%1000 == 0):
....:         print get_memory_usage()
....:         
1040.85546875
1054.1875
1067.51171875
1080.83203125
1094.15625
1107.48046875
1120.8046875
...

and even

sage: while 1:
....:     bla = R.ideal([1]).groebner_basis()
....:     count += 1
....:     if (count%1000 == 0):
....:         print get_memory_usage()
....:         
1272.20703125
1285.53125
1298.859375
1312.1796875
1325.50390625
1338.828125
...

Hard to believe that this should be a leak in Singular. But apparently it is even in our more basic libsingular wrapper:

sage: from sage.libs.singular.function import singular_function
sage: groebner = singular_function('groebner')
sage: I = R.ideal(1)
sage: while 1:                  
    bla = groebner(I)
    count += 1
    if (count%1000 == 0):
        print get_memory_usage()
....:         
1352.421875
1365.74609375
1379.06640625
1394.38671875
1407.70703125
1421.02734375
...

Later today I'll try pure singular.

[simon-king-jena]

comment:15

I tried this in Singular:

> ring R = 0, (x,y), dp;
> ideal I = 1;
> for (int count=0; 1; count++)
. { print((memory(1),memory(2)), "%;");
.   I = ideal(groebner(I)[1]);
. }

The memory consumption is constant, but I suppose that's because Singular knows that if an ideal is generated by a single element then this element is a standard basis:

> ideal I = x;
// ** redefining I **
> attrib(I, "isSB");
1

So, let's try with a different case:

> ideal I = x,y;
> for (int count=0; 1; count++)
. { if (count%1000==0) {print((memory(1),memory(2)), "%;");}
.   I = ideal(groebner(I)[1]) + ideal(groebner(I)[2]));
.   if (attrib(I, "isSB")) {print("not good");}  //just to be sure it isn't known to be standard
. }
2232320 2268160

2232320 2268160

2232320 2268160

2232320 2268160

2232320 2268160

2232320 2268160

2232320 2268160

2232320 2268160

So, it seems that the leak is in Sage and not in Singular, which I think is not a surprise.