Memory leak in BooleanPolynomialRing

[nbruin]

From https://ask.sagemath.org/question/35623/memory-leak-when-doing-anf-of-boolean-functions/ :

sage: import gc
....: BPR=sage.rings.polynomial.pbori.BooleanPolynomialRing
....: print "PBR objects:",len([a for a in gc.get_objects() if type(a) is BPR])
....: for i in range(1,51):
....:   B=BooleanPolynomialRing(i,"x")
....: del B
....: _=gc.collect()
....: print "PBR objects:",len([a for a in gc.get_objects() if type(a) is BPR])
PBR objects: 0
PBR objects: 50

These objects leak.

CC: @simon-king-jena @jpflori @pfasante

Component: memleak

Keywords: BooleanFunction, days94

Branch/Commit: u/asante/memory_leak_in_booleanpolynomialring @ 16350a4

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

[nbruin]

comment:1

The problem is that upon creation:

    B=BooleanPolynomialRing(3,"x")

the code

    self._monom_monoid = BooleanMonomialMonoid(self)

is executed. A BooleanMonomialMonoid is UniqueRepresentation, so B goes as a key into a global WeakValueDictionary, with value the monoid M. So B will not be garbage collected while M exists (the strong reference in the global dict will only be erased on the weakvalue callback upon M's deallocation)

But B stores a reference to M in B._nomom_monoid, so M will not be deallocated until B is deallocated. Hence, the memory leak.

Possible strategies:

• Remove UniqueRepresentation from BooleanMonomialMonoid. I don't think there are any drawback from this solution.
• remove the strong reference B._nomom_monoid and instead rely on the UniqueRepresention property to reconstruct the thing every time. I suspect this will slow things down.
• change the construction parameters of BooleanMonomialMonoid to be just strings etc. and not refer to B at all. This is easy to get wrong.

By the way, the code from the asksage question referred to unovers the following additional bug, which made the memory leak noticeable.

sage.rings.polynomial.pbori.BooleanPolynomialRing is not UniqueRepresentation and instead relies on sage.rings.polynomial.polynomial_ring_constructor.BooleanPolynomialRing_constructor to get uniqueness.

In
sage.crypto.boolean_function.BooleanFunction.algebraic_normal_form
the class is called directly, so we end up with many equal-but-not-identical rings (which is not a problem in its own right)

[nbruin]

comment:2

As it turns out, the UniqueRepresentation was introduced to solve a pickling problem:

#9138 comment:46

It seems that removing the UniqueRepresentation only makes the pickling problems reappear, so if we can find a different solution for the pickling problem we might be good to go.

CC-ing the author of #9138, Simon. Perhaps he remembers an alternative.

[tscrim]

comment:3

So if we remove the UniqueRepresentation behavior from the BooleanMonomialMonoid, we would probably have to manually implement some form of pickling.

Actually, from a quick glance through the code, I don't see a point to having BooleanMonomialMonoid, we are not really using that it is a parent. We essentially just need the element class and we can mimic what we do for usual polynomials, have monomials() return elements in the polynomial ring. It's more work to fix, but I think the net result will be much cleaner and simpler code. It shouldn't result in a slowdown unless you are using monomials or iterating over polynomials, and even then, it shouldn't have a noticeable effect...

[nbruin]

comment:5

Dupe of #14549 ?

Perhaps we should just merge the branch there and leave this ticket.

[pfasante]

comment:7

+1 for merging that #14549 branch and leaving this ticket for the "real" fix.

[pfasante]

comment:8

So just to make this clear:

The favorable solution is what tcsrim above writes:
Remove BooleanMonomialMonoid and replace it with the default behavior of other Polynomial classes?

[pfasante]

Branch: u/asante/memory_leak_in_booleanpolynomialring

[pfasante]

Author: Friedrich Wiemer

[pfasante]

New commits:

f98d64f

start removing BooleanMonomialMonoid

[pfasante]

Commit: f98d64f

[pfasante]

Changed keywords from none to BooleanFunction, days94

[mathzeta]

comment:11

Small stylistic corrections in convert_to_pE:

1. "definig" should be "defining".
2. `p = cE.get_pc()` should be ``p = cE.get_pc()``
3. I think that English prefers "vice versa" over "viceversa", unlike Italian or Spanish.

In lift_to_polynomial() and lift_to_polynomial_rational_reconstruction() "poly" seems weird. Maybe just "Compute a lift to a polynomial ring R using rational reconstruction."
Also "recontruction" should be "reconstruction", and `self` should be ``self`` in few places.

In both gcd() methods the default value for the algorithm keyword should come first:

    - ``pari`` - use pari routines.
    - ``modular`` - (default) modular algorithm using NTL.

In Polynomial_absolute_number_field_dense at

raise ValueError("unknown algorithm %s" % (algorithm))

The string format should be (algorithm, ).

[pfasante]

comment:12

Replying to @mathzeta:

Small stylistic corrections in convert_to_pE:

[...]

The string format should be (algorithm, ).

Err.. does this ended up in a wrong ticket? I cannot find anything of the above mentioned in src/sage/rings/polynomial/pbori.pyx.

[sagetrac-git]

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

16350a4

Revert "start removing BooleanMonomialMonoid"

[sagetrac-git]

Changed commit from f98d64f to 16350a4

[pfasante]

comment:14

After discussing with Travis again, we decided that it's best not to remove BooleanMonomialMonoid, as it looks like its often used implicitly in the code.

Instead we decided to do the following:

• BooleanPolynomialRing_constructor should create the BooleanMonomialMonoid and pass a reference of this object to BooleanPolynomialRing.__init__ (replacing the n and names arguments).
• BooleanPolynomialRing stores this reference, instead of creating the BooleanMonomialMonoid itself.
• Delete the reference to BooleanPolynomialRing from BooleanMonomialMonoid and thus rewrite all lines where this reference is used.
• To clean things up, move the caching done in BooleanPolynomialRing_constructor to BooleanPolynomialRing.__init__.

[pfasante]

comment:15

At the moment, this ticket is a bit above my head.

[pfasante]

Changed author from Friedrich Wiemer to none

[videlec]

comment:17

update milestone 8.3 -> 8.4