Opened 3 years ago

Last modified 15 months ago

#21892 needs_work defect

Memory leak in BooleanPolynomialRing

Reported by: nbruin Owned by:
Priority: major Milestone: sage-8.4
Component: memleak Keywords: memory leak, BooleanFunction, days94
Cc: SimonKing, jpflori, asante Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/asante/memory_leak_in_booleanpolynomialring (Commits) Commit: 16350a4013c5fbf1c19f2aa9ec17a3320cab5b4f
Dependencies: Stopgaps:

Description

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.

Change History (17)

comment:1 Changed 3 years ago by nbruin

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)

comment:2 Changed 3 years ago by nbruin

  • Cc SimonKing added
  • Component changed from PLEASE CHANGE to memleak
  • Type changed from PLEASE CHANGE to defect

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

https://trac.sagemath.org/ticket/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.

comment:3 Changed 3 years ago by tscrim

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...

comment:4 Changed 2 years ago by jpflori

  • Cc jpflori added

comment:5 Changed 2 years ago by nbruin

  • Milestone changed from sage-7.5 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

Dupe of #14549 ?

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

Last edited 2 years ago by nbruin (previous) (diff)

comment:6 Changed 2 years ago by nbruin

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-8.0
  • Status changed from needs_review to needs_info

comment:7 Changed 2 years ago by asante

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

Last edited 2 years ago by asante (previous) (diff)

comment:8 Changed 20 months ago by asante

  • Status changed from needs_info to needs_work

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?

comment:9 Changed 16 months ago by asante

  • Branch set to u/asante/memory_leak_in_booleanpolynomialring

comment:10 Changed 16 months ago by asante

  • Authors set to Friedrich Wiemer
  • Commit set to f98d64fcd81838ef9fa9cdcc97e4b8c8c6505053
  • Keywords memory leak BooleanFunction days94 added
  • Milestone changed from sage-8.0 to sage-8.3
  • Owner changed from (none) to asante

New commits:

f98d64fstart removing BooleanMonomialMonoid

comment:11 follow-up: Changed 16 months ago by mathzeta2

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, ).

comment:12 in reply to: ↑ 11 Changed 16 months ago by asante

Replying to mathzeta2:

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.

comment:13 follow-up: Changed 16 months ago by git

  • Commit changed from f98d64fcd81838ef9fa9cdcc97e4b8c8c6505053 to 16350a4013c5fbf1c19f2aa9ec17a3320cab5b4f

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

16350a4Revert "start removing BooleanMonomialMonoid"

comment:14 in reply to: ↑ 13 Changed 16 months ago by asante

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__.

comment:15 Changed 15 months ago by asante

  • Owner changed from asante to (none)

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

comment:16 Changed 15 months ago by asante

  • Authors Friedrich Wiemer deleted
  • Cc asante added

comment:17 Changed 15 months ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

Note: See TracTickets for help on using tickets.