Memory leaks in libsingular polynomial evaluation and substitution

[simon-king-jena]

The following two examples leak memory (in sagemath from 8.9 to 9.3.rc5)

sage: R = PolynomialRing(ZZ, 'x', 50)
sage: d = {str(g): g for g in R.gens()}
sage: p = sum(d.values())
sage: import gc
sage: mem0 = get_memory_usage()
sage: for i in range(20):
....:     for _ in range(50):
....:         _ = p.subs(**d)
....:     _ = gc.collect()
....:     mem1 = get_memory_usage()
....:     if mem1 > mem0:
....:         print(i, mem1-mem0)
....:         mem0 = mem1

and

sage: R.<x, y> = ZZ[]
sage: p = (x + y)**100
sage: mem0 = get_memory_usage()
sage: for i in range(20):
....:     _ = p(x + y, y)
....:     _ = gc.collect()
....:     mem1 = get_memory_usage()
....:     if mem1 > mem0:
....:         print(i, mem1-mem0)

This was reported on sage-devel and ask.sagemath.org.

We fix .subs (the first example above) by modifying the appropriate singular call. We identified two possibly related memory leaks in singular

• singular issue #1089
• singular issue #1090

In the mean time, we use the non-satisfactory solution of going via naive substitution in Python. To do so, we moved the generic implementation on the base class MPolynomial.

See also #13447 also related to memory handling in singular.

Upstream: Reported upstream. No feedback yet.

CC: @nbruin @malb

Component: memleak

Keywords: libsingular polynomial memleak

Author: Vincent Delecroix, ​Dima Pasechnik

Branch/Commit: u/vdelecroix/27261 @ edf8847

Reviewer: Dima Pasechnik

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

[simon-king-jena]

comment:1

For testing, I changed the code so that the id() of any newly created MPolynomial_libsingular instance is stored in some set, and is removed from the set as soon as it becomes garbage collected.

Result: In the above examples, the MPolynomial_libsingular instances are correctly garbage collected.

Conclusion: The memleak occurs in Sage's usage of libsingular. Apparently the underlying data of a polynomial are not correctly freed when it is deallocated.

[simon-king-jena]

comment:2

Or, another possibility: Some temporary libsingular data created during the computation of Q is not freed.

To detect this, I will try to make the example more fine-grained: Test if the leak occurs if the only arithmetic operation involved is _add_, _mul_ or __pow__, respectively. (X+Y)<sup>120*Y</sup>100 mixes these three operations.

[simon-king-jena]

comment:3

Interestingly, creating a copy of P from scratch does not leak:

sage: import gc
sage: R.<X,Y> = ZZ[]
sage: P = (X+Y)^120*Y^100
sage: mem0 = get_memory_usage()
sage: for i in range(500):
....:     Q = (X+Y)^120*Y^100
....:     del Q
....:     _ = gc.collect()
....:     mem1 = get_memory_usage()
....:     if mem1>mem0:
....:         print(i, mem1-mem0)
....:         mem0 = mem1
....:         
(0, 0.1484375)
sage: 

So, it seems that calling the polynomial (i.e., P(X,Y)) is what is leaking!

[simon-king-jena]

comment:4

Note that there previously was a leak in polynomial evaluation, as by comment in sage.libs.singular.polynomial.singular_polynomial_call - see #16958. So, perhaps it didn't get completely fixed?

[simon-king-jena]

comment:5

singular_polynomial_call copies the input data before doing the actual call. This, I think, is a waste of time. I tested that taking the copy is not causing the leak, but while we are at it, it could as well be improved, too.

[simon-king-jena]

comment:6

Also, singular_polynomial_call has an argument poly *(*get_element)(object) that is (at least in the Sage library) always assigned with the function MPolynomial_libsingular_get_element, which does nothing more than return the ._poly of an MPolynomial_libsingular.

So, basically the get_element argument is void. Should it be removed?

[embray]

comment:8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

comment:9

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

[videlec]

comment:10

Stumble upon a similar problem using .subs()

sage: R.<X,Y> = ZZ[] 
....: import gc 
....: mem0 = get_memory_usage() 
....: for i in range(1000): 
....:     for _ in range(100): 
....:         _ = (X + Y).subs(X=X, Y=Y) 
....:     _ = gc.collect() 
....:     mem1 = get_memory_usage() 
....:     if mem1>mem0: 
....:         print(i, mem1-mem0) 
....:         mem0 = mem1                                                                                                                                                                      
78 0.1328125
100 0.1328125
121 0.12890625
142 0.12890625
164 0.1328125
172 2.0
185 0.12890625
206 0.12890625
228 0.1328125
...

See also https://ask.sagemath.org/question/29444/high-memory-usage-when-substituting-variables/

[videlec]

comment:11

Since __call__ calls subs() I gues the latter is the culprit.

[videlec]

Commit: ee9a54a

[videlec]

New commits:

ee9a54a

27261: fix memory leak in polynomial substitution

[videlec]

Changed dependencies from #13447 to none

[videlec]

Branch: u/vdelecroix/27261

[sagetrac-git]

Changed commit from ee9a54a to 00b85c8

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

00b85c8

27261: doctest subs leak

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

bd4d41f

27261: doctest subs and `__call__` leak

[sagetrac-git]

Changed commit from 394d173 to 58ba726

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

58ba726

27261: more robust leak test

[videlec]

comment:58

Replying to @dimpase:

I've opened Singular/Singular#1090

Apparently, partially fixed in b983a8a.

[mwageringel]

comment:59

This ask-sage question reports that there is also a performance problem with polynomial evaluation. Could this be related to the issue of this ticket? The example from the linked question is about 10 times slower than the naive Python substitution.

[videlec]

comment:60

Replying to @mwageringel:

This ask-sage question reports that there is also a performance problem with polynomial evaluation. Could this be related to the issue of this ticket? The example from the linked question is about 10 times slower than the naive Python substitution.

This ticket is not about performance issue. But as I mentioned in the ask question switching to naive Python evaluation as done in my branch actually speeds up the evaluation.

[videlec]

comment:61

ping?

[dimpase]

comment:62

testing...

[dimpase]

comment:63

lgtm

[dimpase]

Reviewer: Dima Pasechnik

[videlec]

comment:64

thx

[dimpase]

comment:65

one test broken on macOS:

File "src/sage/rings/polynomial/multi_polynomial_libsingular.pyx", line 153, in sage.rings.polynomial.multi_polynomial_libsingular
Failed example:
    for i in range(30):
        n = leak_subs(20)
        print("Leaked {} bytes".format(n))
        if n == 0:
            zeros += 1
            if zeros >= 6:
                print("done")
                break
        else:
            zeros = 0
Expected:
    Leaked ...
    ...
    Leaked 0 bytes
    done
Got:
    Leaked 184549376 bytes
    Leaked 12582912 bytes
    Leaked 4194304 bytes
    Leaked 0 bytes
    Leaked 0 bytes
    Leaked 8388608 bytes
    Leaked 0 bytes
    Leaked 37748736 bytes
    Leaked 0 bytes
    Leaked 4194304 bytes
    Leaked 0 bytes
    Leaked 0 bytes
    Leaked 4194304 bytes
    Leaked 0 bytes
    Leaked 0 bytes
    Leaked 4194304 bytes
    Leaked 0 bytes
    Leaked 0 bytes
    Leaked 37748736 bytes
    Leaked 4194304 bytes
    Leaked 0 bytes
    Leaked 0 bytes
    Leaked 4194304 bytes
    Leaked 0 bytes
    Leaked 0 bytes
    Leaked 37748736 bytes
    Leaked 4194304 bytes
    Leaked 0 bytes
    Leaked 0 bytes
    Leaked 4194304 bytes
**********************************************************************
1 item had failures:
   1 of  55 in sage.rings.polynomial.multi_polynomial_libsingular

(tested together with #30801, but I guess it doesn't matter.

[videlec]

comment:66

The sagemath-singular interface is worse than what I thought. Switching to a generic subs function also leak!

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ddc9a6b	27261: use generic subs
edf8847	27261: move tests in an independent file

[sagetrac-git]

Changed commit from 58ba726 to edf8847

[dimpase]

comment:68

how about adding latest upstream fixes as patches?

[dimpase]

still leaks with Sage 10.1.beta6 (Singular 4.3.2)
As get_memory_usage is gone, I'm running

sage: R = PolynomialRing(ZZ, 'x', 50)
sage: d = {str(g): g for g in R.gens()}
sage: p = sum(d.values())
sage: import gcsage: while (1):
....:     for _ in range(50):
....:         _ = p.subs(**d)
....:     _ = gc.collect()

and observing memory consumption growing in another ternimal running top

[maxale]

If someone wants to monitor memory leak directly in Sage, it can be done via psutil module. Here is a modified example:

import os
import gc
import psutil
import time

def _mem(pid=os.getpid()):
    gc.collect()
    process = psutil.Process(pid)
    return process.memory_full_info()

def test_leak():
    R = PolynomialRing(ZZ, 'x', 50)
    d = {str(g): g for g in R.gens()}
    p = sum(d.values())
    mytime = time.time()
    while True:
        _ = p.subs(**d)
        if time.time() - mytime > 10:   # every 10 seconds
            print(_mem())
            mytime = time.time()

Here test_leak() prints memory usage (after garbage collection) every 10 seconds, which goes like this:

pfullmem(rss=808443904, vms=2267947008, shared=79335424, text=2822144, lib=0, data=790425600, dirty=0, uss=788611072, pss=794329088, swap=0)

pfullmem(rss=1369354240, vms=2828382208, shared=79335424, text=2822144, lib=0, data=1350860800, dirty=0, uss=1349472256, pss=1355190272, swap=0)

pfullmem(rss=1940168704, vms=3398918144, shared=79335424, text=2822144, lib=0, data=1921396736, dirty=0, uss=1920376832, pss=1926094848, swap=0)