Opened 4 years ago
Last modified 2 years ago
#21892 needs_work defect
Memory leak in BooleanPolynomialRing
Reported by:  nbruin  Owned by:  

Priority:  major  Milestone:  sage8.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/memoryleakwhendoinganfofbooleanfunctions/ :
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 4 years ago by
comment:2 Changed 4 years ago by
 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.
CCing the author of #9138, Simon. Perhaps he remembers an alternative.
comment:3 Changed 4 years ago by
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 3 years ago by
 Cc jpflori added
comment:5 Changed 3 years ago by
 Milestone changed from sage7.5 to sageduplicate/invalid/wontfix
 Status changed from new to needs_review
Dupe of #14549 ?
Perhaps we should just merge the branch there and leave this ticket.
comment:6 Changed 3 years ago by
 Milestone changed from sageduplicate/invalid/wontfix to sage8.0
 Status changed from needs_review to needs_info
comment:7 Changed 3 years ago by
+1 for merging that #14549 branch and leaving this ticket for the "real" fix.
comment:8 Changed 3 years ago by
 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 2 years ago by
 Branch set to u/asante/memory_leak_in_booleanpolynomialring
comment:10 Changed 2 years ago by
 Commit set to f98d64fcd81838ef9fa9cdcc97e4b8c8c6505053
 Keywords memory leak BooleanFunction days94 added
 Milestone changed from sage8.0 to sage8.3
 Owner changed from (none) to asante
New commits:
f98d64f  start removing BooleanMonomialMonoid

comment:11 followup: ↓ 12 Changed 2 years ago by
Small stylistic corrections in convert_to_pE:
 "definig" should be "defining".
`p = cE.get_pc()`
should be``p = cE.get_pc()``
 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 2 years ago by
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 followup: ↓ 14 Changed 2 years ago by
 Commit changed from f98d64fcd81838ef9fa9cdcc97e4b8c8c6505053 to 16350a4013c5fbf1c19f2aa9ec17a3320cab5b4f
Branch pushed to git repo; I updated commit sha1. New commits:
16350a4  Revert "start removing BooleanMonomialMonoid"

comment:14 in reply to: ↑ 13 Changed 2 years ago by
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 theBooleanMonomialMonoid
and pass a reference of this object toBooleanPolynomialRing.__init__
(replacing then
andnames
arguments).BooleanPolynomialRing
stores this reference, instead of creating theBooleanMonomialMonoid
itself. Delete the reference to
BooleanPolynomialRing
fromBooleanMonomialMonoid
and thus rewrite all lines where this reference is used.  To clean things up, move the caching done in
BooleanPolynomialRing_constructor
toBooleanPolynomialRing.__init__
.
comment:15 Changed 2 years ago by
 Owner changed from asante to (none)
At the moment, this ticket is a bit above my head.
comment:16 Changed 2 years ago by
 Cc asante added
comment:17 Changed 2 years ago by
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
The problem is that upon creation:
the code
is executed. A
BooleanMonomialMonoid
isUniqueRepresentation
, soB
goes as a key into a globalWeakValueDictionary
, with value the monoidM
. SoB
will not be garbage collected whileM
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 toM
inB._nomom_monoid
, soM
will not be deallocated untilB
is deallocated. Hence, the memory leak.Possible strategies:
UniqueRepresentation
fromBooleanMonomialMonoid
. I don't think there are any drawback from this solution.B._nomom_monoid
and instead rely on theUniqueRepresention
property to reconstruct the thing every time. I suspect this will slow things down.BooleanMonomialMonoid
to be just strings etc. and not refer toB
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 notUniqueRepresentation
and instead relies onsage.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 equalbutnotidentical rings (which is not a problem in its own right)