issues (memory leak + slowness) with multivariate polynomials

[Nadim Rustom]

Hi,

I have recently encountered some issues using multivariate polynomials in Sage. The most serious is a memory leak, which occurs in the following examples:

The following shows a small memory leak:

R.<X,Y> = ZZ[]


P = (X+Y)^120*Y^100


mem1 = get_memory_usage()
for i in range(100):
    Q = P(X,Y)
mem2 = get_memory_usage()


print mem2 - mem1

whereas the following gives a much bigger memory leak:

R.<X,Y> = ZZ[]


P = (X+Y)^120*Y^100


mem1 = get_memory_usage()
for i in range(100):
    Q = P(X,Y)
mem2 = get_memory_usage()


print mem2 - mem1

I tried this on Sage 7.4, Sage 8.5, and on the Sage 8.6 CoCalc server, all with similar results. 

Additionally, I noticed that operations with multivariate polynomials are way faster on Sage 7.4 than on Sage 8.*. Is there any work around for this problem? I tried to search in the open tickets, the closest thing I could find is this:

https://trac.sagemath.org/ticket/13447

Could this be what is causing these issues?

Thanks in advance.

Best,

Nadim.

[Nadim Rustom]

Sorry, I copied the same example twice. The second one (with large leak) should be

R.<X,Y> = ZZ[]


P = (X+Y)^120*Y^100


mem1 = get_memory_usage()
for i in range(100):

    Q = P(X+Y,Y)

mem2 = get_memory_usage()


print mem2 - mem1

[Simon King]

Hi Nadim,

On 2019-02-12, Nadim Rustom <restom...@gmail.com> wrote:
> The following shows a small memory leak:
> R.<X,Y> = ZZ[]
>
>
> P = (X+Y)^120*Y^100
>
>
> mem1 = get_memory_usage()
> for i in range(100):
> Q = P(X,Y)
> mem2 = get_memory_usage()
>
>
> print mem2 - mem1
>
>
> whereas the following gives a much bigger memory leak:
>
> R.<X,Y> = ZZ[]
>
>
> P = (X+Y)^120*Y^100
>
>
> mem1 = get_memory_usage()
> for i in range(100):
> Q = P(X,Y)
> mem2 = get_memory_usage()

The two examples are identical. Copy-and-paste error?

In any case, I can confirm that it leaks (and I am surprised that it
does), even if python's cyclic garbage collection is invoked explicitly.

> Additionally, I noticed that operations with multivariate polynomials are
> way faster on Sage 7.4 than on Sage 8.*. Is there any work around for this
> problem? I tried to search in the open tickets, the closest thing I could
> find is this:
>
> https://trac.sagemath.org/ticket/13447
>
> Could this be what is causing these issues?

Certainly not, since #13447 is not merged yet.

Leaks could be in at least two places here:
(1) An unsolicited reference chain that prevents a Sage polynomial
from being garbage collected.
(2) The underlying libsingular polynomial object is not freed when the
Sage polynomial becomes collected.

#13447 tries to sanitize the refcounting of libsingular objects. So,
if anything, #13477 could have the potential to fix that memory leak.
And in addition, the examples given on the ticket show that it results
in a speed-up for creation and deletion of polynomials.

Before opening a new ticket for this issue, I'd like to test if #13477
helps with this issue.

Best regards,
Simon

[Dima Pasechnik]

it fixes the leak in the 1st example, but not in the 2nd, according to my test.
>
> Best regards,
> Simon
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Nadim Rustom]

Dear Simon,

Thank you for your reply. Indeed I copied the example twice... The second one just has "Q = P(X+Y,Y)" instead of "Q = P(X,Y)". Or even "Q = P(X+Y, X-Y)" results in a larger leak.

Just to clarify, I didn't mean to ask whether #13447 itself is causing the problem, I was just wondering if these problems were known and whether #13447 was meant to fix the memory leak and speed problem. Thanks for your efforts.

Best,

Nadim.

[Simon King]

Dear Nadim,

On 2019-02-12, Nadim Rustom <restom...@gmail.com> wrote:
> Just to clarify, I didn't mean to ask whether #13447 itself is causing the
> problem, I was just wondering if these problems were known and whether
> #13447 was meant to fix the memory leak and speed problem. Thanks for your
> efforts.

No problem.

Indeed #13447 is a rather old ticket that has originally been intended
to get rid of a permanent cache for polynomial rings (the attempt to
change the permanent cache into a weak value dictionary previously resulted
in segfaults).

The old way to reference the underlying libsingular ring was quite inefficient
(namely: Create a python object that is in one-to-one correspondence to the
memory address of the libsingular ring and use that object as key in a
dictionary that counts the references to that ring; so, for each change
of refcount, an additional python object was created and deleted).

Therefore, as a side effect of #13447, polynomial creation and deletion
becomes faster. As Dima mentioned in his post, your first example got fixed
as another side-effect, but your second didn't. So, I am opening a ticket
now.

Best regards,
Simon

[Simon King]

Hi Dima,

On 2019-02-12, Dima Pasechnik <dim...@gmail.com> wrote:
> it fixes the leak in the 1st example, but not in the 2nd, according to my test.

First I thought so, too. But it seems that the leak has only been
/partially/ fixed.

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

In py3 with vanilla sage, the above gives
0 0.25
98 0.12890625
128 0.12890625
157 0.12890625
187 0.12890625
216 0.12890625
246 0.12890625
275 0.12890625
305 0.12890625
329 2.0
331 0.12890625
...

In py2 with #13447, the above gives
(147, 0.03125)
(176, 0.12890625)
(206, 0.12890625)
(235, 0.12890625)
(265, 0.12890625)
(294, 0.12890625)
(324, 0.12890625)
(329, 2.0)
(350, 0.12890625)
(379, 0.12890625)

Strange.

I created https://trac.sagemath.org/ticket/27261 for it.

Best regards,
Simon

[Markus Wageringel]

If I compute a Gröbner basis using libSingular, it is much slower than using the Singular interface. Could this be related to the memory leaks or is it a different issue?

sage: I = sage.rings.ideal.Katsura(PolynomialRing(QQ, 'x', 9))
sage: %time gb1 = I.groebner_basis(algorithm='singular')
CPU times: user 1.34 s, sys: 47.5 ms, total: 1.38 s
Wall time: 13 s
sage: I = sage.rings.ideal.Katsura(PolynomialRing(QQ, 'x', 9))
sage: %time gb2 = I.groebner_basis(algorithm='libsingular')
CPU times: user 49.2 s, sys: 122 ms, total: 49.4 s
Wall time: 49.4 s
sage: gb1 == gb2
True

This defaults to the Singular function `groebner`, but choosing others like `std` or `slimgb` gives similar timings.

Over finite fields, the above issue does not seem to occur – the libSingular computation is slightly faster than Singular, as expected. However, there seems to be a different issue with the Singular interface: repeating the same computation causes a significant slowdown. This does not happen using libSingular.

sage: I = sage.rings.ideal.Katsura(PolynomialRing(GF(2^31-1), 'x', 10))
sage: %time gb1 = I.groebner_basis(algorithm='singular')
CPU times: user 1.86 s, sys: 110 ms, total: 1.97 s
Wall time: 18.4 s
sage: I = sage.rings.ideal.Katsura(PolynomialRing(GF(2^31-1), 'x', 10))
sage: %time gb2 = I.groebner_basis(algorithm='singular')
CPU times: user 1.89 s, sys: 117 ms, total: 2 s
Wall time: 1min 13s
sage: gb1 == gb2
True

This was tested using Sage 8.7 on a MBP 8,1 with OS X 10.13.6. I observed similar results on other machines as well.

[Bill Hart]

I would guess that `libsingular' is the C++ kernel of Singular which does not implement all strategies for GB's over Q. There are additional strategies implemented both in Singular library code and in the Singular interpreter. Presumably the `singular' interface is using the interpreter, if not a Singular library, which makes use of more advanced strategies. In particular there is a library for a modular approach.

[Markus Wageringel]

If I understand the documentation correctly, both cases should call the same Singular function (`groebner` in this case), with the only difference that one is called through the C interface and the other via the Pexpect interface. When I enable the protocol by passing `prot=True`, I get the exact same output, except that one prints faster than the other, which suggests that in both cases the same computation is run by Singular.

Actually, I was planning to add an option to Sage for calling the Singular function `modStd` for the modular approach you mention, when I found this speed difference. None of the current options in Sage seem to allow to make use of modular computations, except when using Giac.

[Dima Pasechnik]

libsingular interface is a mess, cf e.g.

https://trac.sagemath.org/ticket/27508

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/9c034d11-15e0-4ae1-a689-751e039285be%40googlegroups.com.

[Simon King]

Hi!

On 2019-06-16, Dima Pasechnik <dim...@gmail.com> wrote:
> libsingular interface is a mess, cf e.g.
> https://trac.sagemath.org/ticket/27508

Singular uses a peculiar memory manager that is optimized for Gröbner
basis computations. If that memory manager is replaced by ordinary
malloc (which makes sense for debugging) then everything becomes a lot
slower. Does libsingular use the same memory manager than Singular?

Best regards,
Simon

[Dima Pasechnik]

IMHO it does. IMHO the problem is that libsingular interface calls
low-level functions in libsingular
to do polynomial reductions etc, and it misses important optimisations
which are done in Singular proper.


>
> Best regards,
> Simon

>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/qe7hcm%24mvj%241%40blaine.gmane.org.

[Bill Hart]

Both Singular and libsingular.so use omalloc, which is some kind of bump allocator (currently being given multithreading support BTW). It's much faster than xmalloc for that application (libsingular and Singular use it for allocating the objects in the linked list implementations of sparse distributed polynomials which are required for fast polynomial x monomial arithmetic critical to GB's). But Dima is correct, libsingular also misses important optimisations in Singular proper, even aside from the modular issue.

On Monday, 17 June 2019 10:51:05 UTC+2, Dima Pasechnik wrote:

On Mon, Jun 17, 2019 at 9:01 AM Simon King <simo...@uni-jena.de> wrote:
>
> Hi!
>
> On 2019-06-16, Dima Pasechnik <dim...@gmail.com> wrote:
> > libsingular interface is a mess, cf e.g.
> > https://trac.sagemath.org/ticket/27508
>
> Singular uses a peculiar memory manager that is optimized for Gröbner
> basis computations. If that memory manager is replaced by ordinary
> malloc (which makes sense for debugging) then everything becomes a lot
> slower. Does libsingular use the same memory manager than Singular?

IMHO it does. IMHO the problem is that libsingular interface calls
low-level functions in libsingular
to do polynomial reductions etc, and it misses important optimisations
which are done in Singular proper.


>
> Best regards,
> Simon
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to sage-...@googlegroups.com.