Opened 9 years ago
Closed 4 years ago
#14549 closed defect (fixed)
Memory leak in algebraic_immunity of BooleanFunction class
Reported by:  okazymyrov  Owned by:  asante 

Priority:  minor  Milestone:  sage8.0 
Component:  cryptography  Keywords:  algebraic_immunity, BooleanFunction, memory leak 
Cc:  Merged in:  
Authors:  Friedrich Wiemer  Reviewers:  Martin Albrecht 
Report Upstream:  N/A  Work issues:  
Branch:  b350237 (Commits, GitHub, GitLab)  Commit:  b350237676f95b1cc666dd0347982b7c588beaa7 
Dependencies:  Stopgaps: 
Description (last modified by )
On my Mac OS X 10.8.3 the code
from sage.crypto.boolean_function import BooleanFunction s=[BooleanFunction(random_vector(GF(2),16).list()).algebraic_immunity() for g in xrange(100)] s=[BooleanFunction(random_vector(GF(2),16).list()).algebraic_immunity() for g in xrange(100)]
takes around 5GB of RAM on each "s=..." part. You can repeat the procedure for new 5GB.
Without algebraic_immunity function, the problem disappears.
The actual leak happens in BooleanPolynomialRing?, see the below discussion. For this instance, the leak can be somewhat prevented, by using the constructor factory for BooleanPolynomialRing?.
Change History (15)
comment:1 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:2 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:3 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:4 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:5 Changed 5 years ago by
comment:6 Changed 5 years ago by
The leak actually already exists on python level:
import gc from collections import Counter gc.collect() pre={id(c) for c in gc.get_objects()} from sage.rings.polynomial.pbori import BooleanPolynomialRing for i in range(100): P=BooleanPolynomialRing(8, 'x') del P gc.collect() post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre) sorted(post.iteritems(),key=lambda t: t[1])
shows that the sage pythonlevel polynomial rings remain in memory. Looking at the backreferences graph:
objgraph.show_backrefs((a for a in gc.get_objects() if type(a) is sage.rings.polynomial.pbori.BooleanPolynomialRing).next(),filename="g.png",max_depth=6)
You can see there is a circular reference between
sage.rings.polynomial.pbori.BooleanMonomialMonoid
and
sage.rings.polynomial.pbori.BooleanPolynomialRing
. Furthermore, the polynomial ring is a construction parameter for the monoid. This puts a strong reference to the polynomial ring in the CachedRepresentation
cache, so the cycle is kept alive.
The simple solution is to not make BooleanMonomialMonoid
to be UniqueRepresentation?. It probably doesn't need to be. If that's not an option, then BooleanPolynomialRing
isn't allowed to store any references to the BooleanMonomialMonoid
(after all, it can look it up in the CachedRepresentation
cache ...)
This is a classic memory leak that keeps happening over and over.
(it could still be that pbori leaks underneath as well, but the construction above can already explain exploding memory use)
comment:7 Changed 5 years ago by
I tried to simple remove the inheritance of UniqueRepresentation?:
diff git a/src/sage/rings/polynomial/pbori.pyx b/src/sage/rings/polynomial/pbori.pyx index 812f3b9..b6b761a 100644  a/src/sage/rings/polynomial/pbori.pyx +++ b/src/sage/rings/polynomial/pbori.pyx @@ 1835,7 +1835,7 @@ def get_var_mapping(ring, other): return var_mapping class BooleanMonomialMonoid(UniqueRepresentation,Monoid_class): +class BooleanMonomialMonoid(Monoid_class): """ Construct a boolean monomial monoid given a boolean polynomial ring.
but this does not seem to solve the problem for me (ie. it still leaks).
Interestingly, there seems to be no leak, when not importing BooleanPolynomialRing? from pbori before. I guess it then calls the constructor from sage/rings/polynomial/polynomial_ring_constructor.py
Calling this constructor in annihilator also seems to solve the memory leak in the boolean_functions module.
comment:8 Changed 5 years ago by
That sounds like a reasonable hack for the immediate problem. It looks like pbori.BooleanPolynomialRing
isn't UniqueRepresentation? by itself, so calling the factory function is definitely the way to go.
Your tests suggest there needs to be more work if we actually want to solve the underlying leak (there are more polynomial rings that leak: anything that has to do with libsingular has eternal life too). With using the appropriate factory function, you will see that
for i in range(10000): R=BooleanPolynomialRing(8,"x%s"%i)
still leaks.
comment:9 Changed 5 years ago by
 Branch set to u/asante/Memory_leak_in_algebraic_immunity_of_BooleanFunction_class
 Milestone changed from sage6.4 to sage8.0
 Owner changed from mvngu to asante
comment:10 Changed 5 years ago by
 Commit set to b350237676f95b1cc666dd0347982b7c588beaa7
Branch pushed to git repo; I updated commit sha1. New commits:
b350237  hack: solving the immediate memory leak here

comment:11 Changed 5 years ago by
 Status changed from new to needs_review
comment:12 Changed 5 years ago by
 Description modified (diff)
 Keywords memory leak added
comment:13 Changed 5 years ago by
There is some related discussion on #21892. Apparently UniqueRepresentation
is there because of a pickling problem and possibly we can do away with BooleanPolynomialRing?.
One solution is to close this ticket by merging the branch here and leave #21892 open for resolving the underlying problem.
comment:14 Changed 4 years ago by
 Reviewers set to Martin Albrecht
 Status changed from needs_review to positive_review
Looks good to me.
comment:15 Changed 4 years ago by
 Branch changed from u/asante/Memory_leak_in_algebraic_immunity_of_BooleanFunction_class to b350237676f95b1cc666dd0347982b7c588beaa7
 Resolution set to fixed
 Status changed from positive_review to closed
I took a look at this issue, it is still present in sage8.0. But it seems as this is not a problem in the algebraic_immunity function, but, inherited from the call to annihilator, a problem with pbori's BooleanPolynomialRing? objects. The memory leak can be reproduced by
and repeating the last line.
I skimmed over the PolyBoRi? wrapper code, but I have no idea about cython and how this wrapping works in sage, so I'm a bit lost here :) Maybe someone else has a idea, what to do here.
Should this ticket be somehow changed? Closed as the problem is somewhere else, or how to proceed?